Оценка + пример

Сначала сделаем оценку, затем приведём пример.

Оценка. Пусть числа …, равны …, в некотором порядке. Сумма всех этих чисел равна

откуда то есть откуда Мы получили, что обязано быть нечётным.

Пример. Расставим числа в порядке

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

Для спросив про пару мы в любом случае узнаем, чему равно Если то, выписав, какие именно ответы могут соответствовать каждой перестановки, легко убедиться, что разным перестановкам не могут соответствовать одни и те же ответы. Значит, Игорь сможет определить всю перестановку.

Докажем, что при существуют две перестановки и такие, что на все вопросы Игоря могут быть даны одинаковые ответы. Пусть для каждого Паша выбрал а также Пусть Паша на все вопросы Игоря про пары в которых хотя бы одно из чисел и не равно (не умаляя общности будет отвечать Для пары ответами будут для пары — для пары — То есть на любой вопрос Игоря для перестановок и может быть дан один и тот же ответ. Значит, они неразличимы.

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

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

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

Противоречие.

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

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Вариация оценки. Пусть ни одной булочки убрать нельзя. Тогда для каждой непустой тарелки есть цепочка из тарелок, содержащая в которой всего ровно булочек. Если такая цепочка граничит с пустой тарелкой, то можно рассмотреть новую цепочку — эту пустую тарелку добавить, а одну тарелку с противоположного края удалить, и в новой цепочке будет не более булочек, а значит, ровно булочек. Двигаясь так по кругу, получим, что любая тарелка (не только непустая) входит в какую-то цепочку, содержащую ровно булочек. Рассмотрим все такие цепочки. Вместе они покрывают все тарелок.

Заметим, что если какая-то тарелка принадлежит сразу трём цепочкам, то одна из этих трёх цепочек содержится в объединении двух других (тут мы используем, что цепочки «не слишком длинные» — три цепочки не могут покрыть весь круг) и такую цепочку можно выкинуть, сохранив условие «цепочки покрывают все тарелки». Действуя так, можно добиться ситуации, когда никакие три цепочки не имеют общей тарелки. Тогда перекрываются между собой только «соседние» цепочки.

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

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

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

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

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

Покажем, как выложить 100 двухрублёвых и 450 пятирублёвых монет по кругу так, чтобы выполнялось условие задачи. Пронумеруем места по кругу по часовой стрелке числами от 1 до 550 и выложим двухрублёвые монеты на места, номера которых кратны 11 (т. е. 11, 22, …), и на места, номера которых дают остаток 5 при делении на 11 (т. е. 5, 16, …); на остальные места выложим пятирублёвые монеты. Тогда между каждой парой соседних двухрублёвых монет находятся 4 или 5 пятирублёвых монет, причём эти количества чередуются.

Рассмотрим некоторый набор подряд идущих монет; покажем, что они не дают сумму в 52 рубля. Если среди них нет двухрублёвых, то сумма делится на 5, а 52 не делится на 5. Если среди них ровно две двухрублёвых, сумма даёт остаток 4 при делении на 5, то есть тоже не равна 52. Если двухрублёвая монета одна, вместе с ней в наборе может быть не более пятирублёвых, то есть сумма не превосходит рублей. Наконец, пусть двухрублёвых монет в наборе хотя бы три, рассмотрим три двухрублёвых монеты, лежащих в наборе подряд. Между ними есть 9 пятирублёвых; суммарное достоинство этих монет уже равно рублю. Значит, набрана сумма либо в 51 рубль, либо хотя бы в рубля. Таким образом, полученная раскладка удовлетворяет условию.

Осталось показать, что при любой раскладке 100 двухрублёвых и не менее 451 пятирублёвых монет обязательно можно выбрать несколько монет подряд с суммарным достоинством 52 рубля. Пронумеруем двухрублёвые монеты числами 1, 2, …, 100 в порядке их расположения по часовой стрелке. Выделим 50 двухрублёвых монет с нечётными номерами. Между выделенными монетами есть 50 промежутков; в одном из них окажется не менее 10 пятирублёвых монет, иначе общее количество пятирублёвых монет не превосходило бы Итак, мы нашли промежуток, в котором есть ровно одна двухрублёвая монета и хотя бы 10 пятирублёвых; тогда можно взять и 10 пятирублёвых монет так, чтобы они лежали подряд. Тогда и наберётся сумма ровно в 52 рубля.

Предположим, что количество воды в любых двух сосудах отличается больше, чем на л. Пусть — количества воды в сосудах; назовём индексом сосуда его номер в этом ряду. Заметим, что и по нашему предположению отсюда получается, что при

Сумма всех индексов равна

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

С другой стороны, если распределить воду по рядам как

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

Положим Покажем сначала, как выложить карточки так, чтобы больше 33 попарно не пересекающихся идеальных наборов не нашлось. Для удобства обозначим буквы в алфавитном порядке через через будем обозначать последовательность из карточек, на каждой из которых написана буква

Наш ряд будет состоять из 33 блоков выложенных друг за другом в этом порядке. Блок выглядит как:

(единственную карточку с буквой в этом блоке назовём особой). Ясно, что уже в -м блоке содержится идеальных наборов, у которых общей является только особая карточка. Докажем теперь, что в каждом идеальном наборе в полученном ряду есть особая карточка. Поскольку особых карточек всего 33, отсюда будет следовать, что из любых 34 идеальных наборов два обязательно пересекутся по какой-то особой карточке, то есть не может быть больше 33.

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

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

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

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

Далее, выбранный набор содержит других карточек, каждая из которых содержится максимум в одном наборе из выкинув все эти наборы, оставим в как минимум наборов, не пересекающихся с уже выбранными. Среди этих наборов максимум содержат полезные карточки с буквами, отличными от выбрав любой набор, не содержащий такой карточки, мы завершим шаг.

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

Оценка. Покажем, что то есть, что любой эксперт может оказаться некомпетентным. Если этот эксперт считает, что все спортсмены возьмут по одной медали, опровергнем его результатом Иначе эксперт считает, что несколько (хотя бы один) спортсменов получат 0 медалей. Тогда распределим все медали между этими спортсменами так, чтобы каждый из них получил хотя бы одну медаль. В таком случае эксперт не угадает ни одного количества медалей.

Пример. Пусть прогноз одного эксперта — а прогнозы остальных — (1, 0, …, 0, 24), (0, 1, …, 0, 24), …, (0, 0, …, 1, 24) (на последнем месте 24, и ещё одна единица).

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

Предположим теперь, что двое экспертов, отличных от первого, оказались некомпетентными. Тогда в двух позициях их прогнозы — 0 и 1 медалей, а значит, в реальном исходе в этих позициях не менее 2 медалей. Кроме того, ещё в 22 позициях прогнозы обоих экспертов — нули, значит, в реальном исходе в этих позициях не менее 1 медали. Тогда общее количество медалей не меньше — противоречие.

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

Оценка. Рассмотрим множества

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

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

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

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

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

получаем требуемое

Чтобы можно было однозначно определить, в какой из коробок лежит приз, требуется возможность получить хотя бы различных ответов на один набор вопросов. Так как ответы ведущего для различных положений приза могут отличаться только числом “да” среди них, то требуется возможность получить в ответ хотя бы различных количеств “да”. Значит, требуется хотя бы вопросов (от до “да”). Пример на вопросов. Пусть -ый вопрос: «Номер коробки, в которой лежит приз, меньше либо равен ?». Тогда если ответов “да” ноль, то приз в сотой коробке, если один, то в -й и т.д.

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

Покажем, что длина пути короля не может быть больше Рассмотрим два соседних выхода A и B короля на границу доски. Если эти граничные поля не соседние, то участок пути короля между ними разбивает доску на две части, в каждой из которых есть целые клетки. Но тогда король не сможет пройти из одной части в другую, что противоречит условию. Значит, поля A и B — соседние и, следовательно, разного цвета. Так как при диагональных ходах цвет поля не меняется, то между каждыми двумя соседними выходами на границу должен быть прямой ход. Поскольку граничных полей то и выходов на границу — тоже и, следовательно, прямолинейных ходов не меньше Следующий рисунок показывает„ что можно обойтись ровно "прямыми"ходами.

Оценка.

Рассмотрим условие на первую коробку. Из него следует, что в первой коробке не синих шариков не больше двух: иначе мы могли бы набрать 3 шарика, среди которых нет синих.

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

Таким образом, всего шариков не более , если не учитывать синие шарики из первой коробки и красные шарики из второй.

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

Пример.

Положим в первую коробку 2 белых шарика и 2 синих, а во вторую 2 красных шарика и 3 белых. Нетрудно убедиться, что все условия выполняются.

Четырёх трёхтонок может не хватить. Действительно, если у нас будет 13 бочек весом т каждая, то больше трёх бочек погрузить не удастся , а значит, в четьре трёхтонки будет погружено 12 бочек и одна останется.

Докажем, что пяти трёхтонок хватит при любом раскладе. Для этого построим алгоритм погрузки. Постепенно, ящик за ящиком начинаем грузить первую машину. Естественно, в некоторый момент времени, окажется, что после погрузки очередного ящика общая масса погруженного станет больше 3 т. Тогда снимаем обратно последний из ящиков - после этого в машине уже будет не более трёх тонн и не менее двух тонн (из-за того, что перед снятием последнего ящика масса груза была более трёх тонн, а снятый ящик весил не более тонны). Точно также поступаем со второй, третей и четвёртой машинами. Получим четыре автомобиля. В каждом из которых не менее 2 т груза, т.е. общая масса груза в них - не менее 8 т. Это значит, что масса оставшегося груза - не более 2 тонн и мы спокойно грузим его в последнюю машину.

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

Также заметим, что всего у доски будет узлов.

Тогда на доске можно разместить не более корабликов.

а) При получаем оценку, что кораблей не более

Так как число кораблей целое, то их максимум .

Пример на кораблей:

b) При , получаем оценку, что кораблей не более

Так как число кораблей целое, то их максимум .

Пример на кораблей:

Посмотрим, какое минимальное количество марок может изначально быть у Вити в красном альбоме.

_________________________________________________________________________________________________________________________________________________________________________________

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

Пример: 28, 35, 36, ..., 42. Суммарное количество марок тут делится на 7 и на 8 ( ), поэтому можно сделать как 8 альбомов по 42 марки, так и 7 по 48 марок.

_________________________________________________________________________________________________________________________________________________________________________________

Итак, тогда общее число марок не меньше , к тому же кратно 7 и 8 , а потому не меньше . Если в этой сумме заменить на , то получим пример к ответу 32.

Предположим теперь, что в синем альбоме 31 марка или меньше. Тогда в красном не более 30 марок. В то же время общее количество марок равно , где . После расформирования красного альбома в остальных нужно сделать ровно по марок. Значит, изначально в каждом альбоме не более марок. В синий альбом придётся добавить не менее марок, а в остальные суммарно не менее чем марку. Однако в сумме это не менее 32 марок, а в красном альбоме лишь 30.

Если учеников три (или меньше), то учитель справится. Действительно, на первые два вопроса возможны 4 варианта ответа: ++, +-, –, -+. Поскольку учеников не больше трёх, то какую-то из этих комбинаций никто не выбрал, её-то учитель и объявляет «правильной». Так же он поступает с каждой следующей парой ответов. В результате у каждого ребёнка не больше половины верных ответов.

Четыре ученика смогут «обыграть» учителя. Для этого им надо разделить вопросы на две группы нечётного размера (например, первые 5 и последние 7 вопросов) и дать такие ответы: ++++++++++++,————, +++++——-,—–+++++++. Тогда найдётся ребёнок, угадавший больше половины ответов как в первой группе, так и во второй.

Оценка. Пусть у нас хотя бы 98 чисел хороших чисел, тогда хорошим числом точно будет либо 1, либо 99. Но заметим, что если — это хорошее число, то есть есть яблок, которые в сумме имеют вес, равный половине от общего веса, тогда оставшиеся яблок также имеют суммарный вес, равный половине общего, поэтому тоже будет хорошим числом. Следовательно, 1 точно будет хорошим числом, значит, будет яблоко, вес которого равен половине от общего. Возьмём произвольное другое хорошее число не равное 1 и 99, рассмотрим яблок, вес который равен половине от общего, и оставшиеся с таким же весом. Раз мы так разбили все яблоки на две группы, тогда в как-то группе будет яблоко, вес которого половина от общего, но тогда эта группа имеет вес больше, чем половина от общего веса, противоречие.

Пример. Приведём пример 100 яблок с весами для которого все числа от 2 до 98 (всего 97 чисел) — хорошие. Пусть где Тогда 2 — это хорошее число, так как

Раз тогда

Будем производить аналогичные замены, пока в левой части не появятся и при чём каждый раз кол-во чисел будет увеличивается на 1. Следовательно, хорошими являются числа Но тогда хорошими будут и числа то есть все числа от 2 до 98 — хорошие.

Оценка. Рассмотрим числа очевидно их нельзя покрасить в два цвета.

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

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

Пример. Возьмём первое заседание, которое посетят все школьники, а остальные разобьём на 11 групп по 9 заседаний, их посетят по одному школьнику. Скажем, что школьник под номером посетил заседания из -ой группы вместе с самым первым. Таким образом, каждый участник посетил 10 заседаний. Тогда каждый школьник познакомился с остальными десятью на самом первом заседании.

Замечание. Немного модернизируя оценку, можно показать более общий результат: для заседаний наименьшее возможное число школьников при данных условиях равно