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

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

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

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

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

Пример.

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

Поскольку Витя, отдав 1 или 2 альбома, может распределить марки по 7 или 8 альбомам, количество марок кратно 7 и 8. Наименьшее возможное число марок с учетом того, что нет альбомов с одинаковым количеством марок, равно

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

Оценка.

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

Однако а в красном альбоме не более 30 марок. Противоречие.

Ответ "да"на вопрос обозначим, как а ответ "нет"как

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

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

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

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

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

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

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

Поскольку среди любых 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.

Докажем, что Все числа с доски разбиваются на цепочки чисел вида

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

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

откуда Значит, в одной из цепочек не меньше, чем чисел, то есть не меньше 8 чисел. Разность наибольшего и наименьшего чисел в такой цепочке не меньше

Осталось привести пример, в котором Такой пример дают, например, числа

Действительно, в этом примере и ровно для первых 85 из этих чисел в наборе есть число, на единицу большее.

Если удалить полностью 51 кучку, то, очевидно, не останется много камней. Значит, искомое значение меньше 5100. (Альтернативно, можно удалить из всех кучек по 51 камню.)

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

Покажем, что при …, то есть кучки с номерами от 51 до 100 удовлетворяют требованию.

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

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

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

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

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

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

Оценка

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

Так как , то оно не . Значит, четное или , или . Не умаляя общности, пусть . Тогда число чётное и простое, то есть , но тогда ?! Значит, правильных утверждений не более .

Пример

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

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

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

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

Пример: Покрасим все строки доски с нечётными номерами ( клетки). Любой уголок содержит клетки двух каких-то соседних строк, потому в нём будут закрашенные.

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

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