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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Покажем, что длина пути короля не может быть больше Рассмотрим два соседних выхода 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 — хорошие.

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

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

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

Обозначим количества карандашей разных цветов за

Если то получаем противоречие с выводом выше. Значит,

Тогда суммарно в коробке карандашей

Может ли быть ровно 1603 карандаша? Да, например, если было 19 карандашей одного цвета ( и по 16 карандашей всех остальных цветов (

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

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

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

Оценка. Докажем, что, если Вася задаст всего любых вопросов, он может не найти ни одной пары карточек с соседними числами. Предположим противное, что задав некоторые вопросов он смог точно указать на пару карточек с соседними числами. Переведём задачу на язык теории графов. Карточки будем считать вершинами графа а заданные Васей вопросы – рёбрами (синими рёбрами), соединяющими соответствующие пары карточек. К этим рёбрам нужно добавить ещё одно, соответствующее той паре карточек, на которых написана пара соседних, по версии Васи, чисел. Теперь нужно доказать, что вершины могут быть занумерованы в таком порядке, что ни одно ребро не соединяет две вершины с соседними номерами. То есть, нужно дорисовать в графе путь из рёбер, проходящий последовательно по всем вершинам, и не содержащих ни одного из «Васиного» синего ребра. Это будет означать, что Васина догадка не верна. Назовём такой путь красным и будем строить его методом математической индукции по числу вершин графа

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

1) Пусть в есть «крайняя» вершина из которой выходит ровно одно ребро В графе полученном из удалением вершины и ребра число вершин равно а рёбер – не больше выполнено предположение индукции, поэтому в можно построить красный путь длины с началом в вершине и концом в вершине Тогда ребро не соединяет вершину с одной из или проведя красное ребро из в эту вершину, получим красный путь длины в

2) Пусть в нет вершин, из которых выходит ровно одно ребро. В таком случае все синие рёбра инцидентны в сумме вершинам степени не меньше каждая, следовательно, среди них не больше различных. Следовательно, в не меньше двух вершин из которых не выходит ни одного синего ребра. Удалим из вершины и два ребра, выходящие из некоторой четвёртой вершины (но не саму вершину). Полученный граф снова удовлетворяет предположению индукции и в нём можно построить красный путь длины с началом в вершине и концом в вершине Если он не проходит через или проходит, но не проходит через удалённые рёбра, соединим с и с и получим красный путь в длины 99. В оставшихся случаях, обозначим за и вторые концы удалённых рёбер. Если красный путь в проходит через заменим этот фрагмент на Если он проходит только через одно удалённое ребро, скажем, через заменим его на В обоих случаях получится красный путь в

База индукции - случаи графов с 3 и 4 вершинами - очевидна.

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

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

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

Если Марина достанет 17 носков, то среди них будет не больше 8 белых, а значит - хотя бы 9 чёрных. Поэтому в этот момент она точно воскликнет «Наконец-то!».

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

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

(b) Пусть среди выбранных фруктов не найдётся разноцветных яблока и груши. Тогда возможны следующие случаи:

1. Выбраны только яблоки, тогда фруктов штук

2. Выбраны только груши, тогда фруктов штук

3. Среди выбранных фруктов есть и яблоки, и груши, а значит все выбранные фрукты одного цвета. Если выбраны только красные фрукты, то их не больше штук, если только жёлтые, то их не больше а если только зелёные — не больше

Итак, выбрано не больше 35 фруктов. Отсюда наименьшее при котором среди произвольно выбранных фруктов обязательно найдутся разноцветные яблоко и груша, равно 36.

Пусть девочек хотя бы . Так как у разных девочек разное количество друзей-мальчиков, то у девочки с наибольшим количеством друзей-мальчиков таких друзей хотя бы (так как может быть девочка, которая не дружит с мальчиками). Значит, мальчиков хотя бы и всего детей хотя бы ?!

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