Логика → .12 Оценка + пример

Докажем, что меньше 8 не хватит. Предположим, мы поставили 7 или меньше ладей. Тогда хотя бы в одной горизонтали и хотя бы в одной вертикали нет ни одной ладьи (так как и первых и вторых по 8). Посмотрим на клетку, в которой пересекаются свободная горизонталь и свободная вертикаль (если таких несколько, то на любую из них). Эту клетку не бьет ни одна ладья (так как иначе ладья стояла бы в свободной вертикали или горизонтали нашей клетки). Следовательно, 7 или меньше ладей не хватает.

Покажем, как можно расставить 8 ладей так, чтобы они били все клетки. Поставим 8 ладей на первую вертикаль. Тогда любая клетка находится в горизонтали с ладьей, следовательно, находится под боем.

Оценка. Пусть на доску поставлено 11 или более коней. Тогда среди них найдутся 6, стоящих на клетках одного цвета. Эти 6 коней друг друга не бьют, что противоречит условию.

Пример на 10 коней получается так: выделим 5 пар клеток черная-белая, соединенных ходом коня (например, клетки и клетки ), и поставим коней на эти 10 клеток. Тогда среди любых 6 коней найдутся два коня из одной пары, именно они и будут друг друга бить.

Заметим, что всего комбинаций . Поскольку первые введённые две цифры являются только началом первой комбинации, то ввести надо не менее цифр, чтобы перебрать их все.

Остаётся привести пример

Заметим, что если набор из карточек хороший, то набор из оставшихся карточек тоже хороший(назовём его дополнительным набором).

Покажем, что для нельзя так указать наборов, чтобы хотя бы один из них оказался хорошим. Для этого достаточно убедиться в том, что при нельзя указать такие наборов. Поскольку, барон выбирает наборы карточек, не зная, какие числа написаны на этих карточках снизу, мы можем считать, что изначально на карточках не было никаких надписей, а числа на карточках появляются уже после того, как выбор сделан. Наша цель — предъявить такой способ разметки карточек, чтобы ни один из выбранных наборов не оказался хорошим.

Итак, пусть выбрано наборов. Рассмотрим произвольную карточку Меняя некоторые наборы на дополнительные, можно добиться того, что карточка будет присутствовать во всех наборах. Перечислим с учётом кратности все остальные карточки, встречающиеся в этих наборах. Всего будет перечислено карточек. Кроме карточки у нас имеется карточек, значит, какая-то из них встретится не менее раз(так как ), назовём её карточкой Напишем на карточках и число тогда те (или более) наборов, в которых встречаются обе эти карточки, будут плохими. Уберём карточки и останется карточек и (или менее) набора, среди которых должен найтись хотя бы один хороший.

Аналогично зафиксируем одну из оставшихся карточек и переделаем наборы так, чтобы карточка входила во все наборы. Выписав все остальные карточки, встречающиеся в наборах, получим карточки. Поскольку, помимо карточки у нас имеется карточек, какая-то из них — назовём её — встретится раз(так как ). Напишем на карточках и число 7 — в результате все эти наборы станут плохими. Уберём карточки и останется карточек и набора, среди которых опять должен найтись хороший.

Действуя аналогично, получим, что какие-то две карточки встретятся вместе хотя бы в наборах, напишем на них число и выкинем, останется карточек и наборов. Тогда, поскольку какая-то пара карточек встретится в одном наборе хотя бы раз. Написав на этих карточках число и выкинув, мы получим карточек и наборов. Какая-то очередная пара карточек встретится в одном наборе хотя бы раз, напишем на них число 4 и выкинем, в результате получим карточек и набора. Далее какая-то пара карточек встретится в одном наборе хотя бы раз, записываем на них число и выкидываем, останется карточки и набор. Напишем на двух карточках из этого набора число а на двух других — число тогда и этот набор также окажется плохим. Мы доказали, что всегда можно так занумеровать карточки, что все наборов окажутся плохими.

Покажем теперь, что для карточек всегда можно выбрать наборов так, чтобы хотя бы один из них оказался хорошим. В нашем случае и мы сможем выбрать наборов, что решает задачу. Набор из карточек, на которых записаны различных чисел(каждое — в двух экземплярах), будем называть двойным.

Пример 1. Докажем индукцией по что для любого двойного набора из карточек всегда можно предъявить наборов, среди которых есть хороший. База очевидна.

Пусть на столе лежит двойной набор из карточек. Попробуем наудачу выбрать из них две одинаковые карточки, взяв произвольные карточки и Самоуверенно отложим их в сторону. Если мы угадали, то на столе остался двойной набор из карточек, для которого, применив предположение индукции, можно указать наборов, среди которых есть хороший. Теперь для каждого указанного набора рассмотрим наборы

Мы утверждаем, что среди наборов и (а их в сумме получается ровно штук) непременно найдётся хороший(для исходного множества карточек) набор. Если карточки и и в самом деле одинаковые, это очевидно — подойдут даже два набора.

Предположим теперь, что на карточках и написаны разные числа(обозначим их также и ). Тогда в оставшемся множестве из карточек были “непарные” карточки с числами и — мысленно соединим их в новую пару и применим предположение индукции, указав наборов, среди которых есть хороший набор содержащий по одной карточке из каждой пары. На самом деле он содержит ровно одно из чисел новой пары, скажем и по одному представителю всех остальных пар. Но тогда набор в исходном множестве карточек является хорошим!

Пример 2. Построим граф, вершинами которого являются карточки. Каждую пару карточек с одинаковыми числами соединим красным ребром. Проивзольным образом разобьём карточки на пары и соединим карточки в каждой паре синим ребром. Полученный красно-синий граф(на самом деле мультиграф, поскольку между одной парой вершин может быть проведено и красное, и синее ребро) представляет собой несколько циклов чётной длины. Рассмотрим такой набор его вершин, что в каждом цикле вершины выбраны через одну, назовём его чередующимся набором. Тогда в этом наборе будет присутствовать ровно один конец каждого красного ребра и, значит, он будет хорошим. Проблема в том, что мы, т.е. Мюнхгаузен, не знаем как именно проведены красные рёбра. Но заметим, что любой чередующийся набор содержит ровно по одной вершине каждого синего ребра. Поэтому, указав все наборов, содержащих ровно по одной вершине каждого синего ребра, мы заведомо укажем и чередующийся набор. Поскольку набор и его дополнение лишь одновременно могут быть чередующимися, из каждой пары взаимодополняющих наборов достаточно брать только один. Стало быть, достаточно указать лишь наборов.

Заметим, что количество авантюристов, у которых есть сапфиры, равняется суммарному количеству авантюристов, у которых есть изумруды или бриллианты. Тогда из первого условия следует, что у 9 авантюристов есть сапфиры и изумруды, а у 6 — сапфиры и бриллианты. Т.е. у каждого авантюриста, у которого есть изумруды, обязательно есть сапфиры. Тогда, из второго условия, не может быть авантюриста, у которого есть и изумруды, и рубины. Значит, авантюристов как минимум

Столько авантюристов и правда может быть: пусть у нас есть 9 авантюристов, у которых есть сапфиры и изумруды, 6 авантюристов, у которых есть сапфиры, бриллианты и рубины, а также 7 авантюристов, у которых есть только рубины. Можно убедиться, что этот пример подходит под все условия.

Рассмотрим, как изменяется число, при переходе слева направо на одного человека. Если рядом стоящие дети разного пола, то число не изменяется. Если переходим от девочки к девочке, то число увеличивается на а если от мальчика к мальчику, то уменьшается на Таким образом, самое маленькое число в ряду могло увеличиться не более, чем на а значит, различных чисел не более

Приведём пример на различных чисел: поставим последовательно слева направо сначала всех мальчиков, затем всех девочек. Тогда числа в ряду будут:

— всего различных.

Заметим, что 2 тип > 3 тип > 1 тип, где “>” означает “выгодней” в смысле цены за один подарок. Видно, что 25 ящиков второго типа и 4 ящика третьего является самым выгодным примером без первого типа.

Теперь предположим, что найдётся пример с ящиками первого типа, который является более выгодным. Тогда в нём больше ящиков второго типа, чем в нашем, но в этом случае их может быть либо 26, либо 27 – в обоих случаях не получится уложить подарки в целое число ящиков, противоречие.

Оценка. Разобьём квадрат на горизонтальных прямоугольников . Докажем, что в каждом из них Маша может провести не более отрезка, соблюдая условие задачи. Для каждого такого прямоугольника отметим все узлы сетки, лежащие на средней линии (см. рисунок снизу для ).

В каждом прямоугольнике таких точек . Очевидно, любой Машин отрезок задействует не менее одной отмеченной точки. Значит, Маша в каждом таком прямоугольнике сможет провести не более отрезков. Таким образом, во всём квадрате она проведёт не более отрезков. Тогда количество пустых клеток не меньше .

Пример. На рисунке снизу показан пример для (при других чётных примеры аналогичны).

Посчитаем количество пустых клеток

Оценка: Удалим все граничные кубики. Останется куб со стороной разбитый перегородками на кубиков. Теперь пространство разделено перегородками на областей, считая внешнюю. Удаление одной перегородки уменьшает число областей не более, чем на В конце число областей должно стать равным поэтому придется удалить не менее перегородок.

Пример: из каждого неграничного кубика уберём нижнюю грань.

В первый день губернатор приглашает для опроса всех островитян. Получив ответы, он разбивает островитян на группы, объединяя в одну группу островитян, давших один и тот же ответ. Пусть число групп равно Все правдивые островитяне дали правильные ответы, поэтому все они окажутся в одной группе, а все остальные — в других группах. Если, в частности, то все островитяне правдивые. Если же , то на следующий день губернатор приглашает ровно по одному островитянину из каждой группы. Среди приглашённых островитян будет ровно один рыцарь, который даст ответ: «». Этот островитянин, а также все из его группы — рыцари, а все остальные — лжецы.

Одного дня недостаточно. Предположим, после опроса островитян ответили, что среди опрашиваемых лжецов, а — что среди опрашиваемых лжецов. Такие ответы могли быть получены и в случае, когда среди опрашиваемых рыцарей и лжецов, но также и в случае, когда среди опрашиваемых рыцарей и лжецов.

Оценка. Если прожекторов менее четырёх, то какие-то две вершины квадрата освещены одним прожектором. Но из любой точки внутри квадрата сторона видна под углом больше

Пример. Разобьём квадрат на четыре равных квадрата. От центра квадрата отложим на одной из диагоналей отрезок, равный половине стороны квадрата. Проведём два луча с концом в полученной точке, проходящие через середины двух наиболее удалённых от неё сторон. Угол между этими лучами равен поэтому если поставить в данную точку прожектор и направить его по этим двум лучам, то он осветит один из квадратов разбиения. Поставив аналогичным образом на диагоналях ещё три прожектора, сможем осветить и остальные квадраты.

Если отряд не может создать жезл, то существует хотя бы одно заклинание, которое не знает ни один маг из данного отряда. Рассмотрим любые заклинаний. Каждый маг не знает хотя бы одно из них. Поэтому очевидно можно разбить магов на отрядов, в каждом из которых маги не знают одно из рассмотренных шести заклинаний. Почему нельзя разбить на отрядов или меньше? Предположим, что мы всё-таки смогли разбить на отрядов. Точно можно сказать, что в первом маги не знают одно заклинание, во втором - другое, и так дальше до - го. Но по условию существует маг, который знает все эти заклинаний и он находится в каком-то из этих отрядов, пришли к противоречию.

Приведём пример на месяца: Занумеруем учеников

месяц: и

месяц: и

месяц: и

месяц: и

Оценка: Пусть нам потребовалось не более трёх месяцев. Если в какой-то месяц ученик попал в первую группу, присвоим ему если во вторую, присвоим Тогда каждый ученик охарактеризуется последовательностью из нулей и единиц длиной не более чем в символа. Но в таком случае последовательностей не более а учеников а значит у каких-то последовательности совпадут, то есть в разных группах они не побывают.

Пусть всего боксёров и у -го боксёра зубов. По условию Просуммируем все неравенства и получим

что, в свою очередь, равносильно откуда или Очевидно, что не подходит, значит Пример для у одного зубов, у остальных по

Заметим. что не найдётся 3 стоящих подряд девочек в красных кофтах (иначе для средней из них не выполняется условие). Разбив 36 детей на 12 троек, получаем, что в каждой из них не более 2 девочек в красных кофтах, а всего девочек в красных кофтах не больше .

Пример построить легко — в каждой из 12 троек по часовой стрелке располагаются две девочки в красных кофтах, а следом за ними мальчик в синей кофте:

Покажем, что найдутся 3 подряд идущих числа, среди которых есть по крайней мере 2 чётных. Это можно сделать, например, так. Рассмотрим 15 подряд идущих чисел. Они разбиваются на 3 пятёрки подряд идущих чисел, значит, среди них есть по крайней мере 6 чётных. Но эти 15 чисел можно разбить на 5 троек подряд идущих чисел. Значит, по принципу Дирихле в какой-то тройке есть хотя бы 2 чётных числа.

Зафиксируем эти 3 числа. Среди них есть хотя бы 2 чётных. Остальные 100 разобьем на 20 пятёрок подряд идущих. В каждой такой пятёрке будет не менее двух чётных чисел. Таким образом, общее количество чётных чисел не менее . Такая ситуация возможна. Пронумеруем числа по кругу. И чётными можно взять числа с номерами . (Возможны и другие примеры.)

Количество школьников, которые выполнили все заклинания правильно, не больше 75, так как только 75 школьников выполнили правильно второе заклинание. Количество школьников, которые ошиблись в 1-ом, 3-ем, 4-ом или 5 -ом заклинаниях, не более . Если школьник ошибся хотя бы в двух заклинаниях, то он точно ошибся в каком-то заклинании, отличном от второго. Следовательно, количество школьников, которые ошиблись хотя бы в двух заклинаниях не превышает 17. Тогда искомое количество школьников не менее .

Осталось показать, что такое количество школьников бывает. Действительно, пусть первые 25 школьников ошиблись во втором заклинании. Из них пятеро ошиблись в первом, трое — в третьем, пятеро — в четвертом, четверо — в пятом. Так как меньше 25 , то эти 17 школьников могут быть различными.

Оценка. Докажем, что «не работает».

Пусть дан набор из конфет. Назовём сорт критическим, если конфет этого сорта ровно 10 (среди всех данных конфет). Пусть у нас критических сортов, тогда всего конфет не менее Уберём по одной конфете каждого критического сорта и организуем группу из оставшихся конфет. Для этой группы нет сорта, представленного ровно 10 конфетами. Кроме того,

Значит, в рассматриваемой группе не менее 145 конфет, поэтому условие задачи не выполняется.

Пример. Теперь приведём пример ситуации, в которой у Васи может быть 160 конфет. Пусть у него есть ровно по 10 конфет 16 сортов. Пусть выбрана группа, для которой нет сорта, представленного ровно 10 конфетами. Тогда в эту группу не входит хотя бы одна конфета каждого сорта (иначе говоря, ни один сорт не будет взят полностью), т.е. группа содержит не более конфет, значит, условие задачи выполнено.

Назовём тройку натуральных чисел элементы которой принадлежат хорошей, если

Таким образом, нам надо найти наибольшее возможное количество хороших троек.

Выясним, когда тройка хорошая. Перепишем как квадратное уравнение относительно :

Решая его, получаем:

откуда

Иначе говоря, тройка является хорошей тогда и только тогда, когда одно из чисел и равно сумме двух других.

Пусть — все элементы множества Положим Оценим количество хороших троек в которых — наибольшее число, то есть

Заметим, что при любых есть не более одной такой тройки, в которой и (по этим значениям восстанавливается ). Поэтому оцениваемое количество не превосходит числа таких пар то есть

Аналогично, количество хороших троек, в которых наибольшими являются и не превосходит Поэтому общее количество хороших троек не больше, чем

Эта оценка достигается, если положить то есть действительно, тогда при любых найдётся хорошая тройка

Среди всех 25 одноклассников выберем 16 людей с наименьшим числом выданных конфет. Заметим, что среди них есть человек, которому выдали не меньше 7 конфет (иначе, если им всем выдали не больше 6 конфет, то суммарно им выдали не больше конфет, что меньше 100). Тогда и оставшимся одноклассникам выдали не меньше 7 конфет. Тогда всего конфет суммарно выдали хотя бы . Соответственно, Вовочка оставил себе не более конфет.

Заметим также, что Вовочка мог себе оставить ровно 37 конфет, если остальные 163 он выдал одноклассникам так: 13 одноклассникам выдал по 7 конфет, а 12 одноклассникам выдал по 6 конфет. Тогда у любых 16 человек суммарно хотя бы конфет, а всего Вовочка действительно выдал конфеты.