Тема Логика

Принцип Дирихле

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела логика

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#104249

В квадрате со стороной $1$ находится $51$ точка. Докажите, что какие-то три из них можно накрыть кругом радиуса $1. 7$

Показать доказательство

Разобьём наш квадрат на 25 квадратов со стороной $0,2.$ По принципу Дирихле в какой-то из них попадёт по крайней мере три точки из 51 брошенной (иначе в каждом квадрате точек не больше двух, всего точек не больше 50, но ведь 51 больше 50). Эти три точки можно накрыть кругом радиусом, равным половине диагонали квадрата $∘ --2----2 √2 1 0,1 +0,1 = 10 < 7,$ поэтому и кругом радиуса $1 7$ тоже накрыть получится.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#76756

У фермера имеется $100$ быков, $100$ баранов, $100$ коров и $100$ овечек, а также карусель на $200$ животных. В карусели стоят коровы и овечки. Напротив каждого выхода из загона в карусели находится другой загон: как не сложно понять, их тоже $200$ и в них стоят быки и бараны. Докажите, что фермер может так повернуть карусель и открыть загоны, чтобы хотя бы $200$ животных из $400$ встретили животное своего вида.

Показать доказательство

Легко видеть, что фиксированное животное из первого загона встретит животное того же вида ровно $100$ раз (то есть при $100$ поворотах карусели из $200$ ). Тогда суммарное количество встреч животных одного типа равно $100⋅200= 20000.$ Тогда по принципу Дирихле при каком-то повороте количество встреч было не меньше, чем $20000∕200= 100,$ то есть при таком повороте не менее $200$ животных встретили животное того же вида.

Ошибка.
Попробуйте повторить позже

Задача 3#79250

Клетчатая фигура уголок состоит из центральной клетки, к которой присоединены горизонтальный и вертикальный прямоугольники $1×10$ (всего в фигуре $21$ клетка). Докажите, что при любой раскраске клеток квадрата $2017 ×2017$ в $120$ цветов из него можно вырезать уголок, содержащий две клетки одинакового цвета.

Показать доказательство

Рассмотрим квадрат $11,$ расположенный “глубоко внутри” квадрата $2017× 2017$ (например, подойдёт квадрат $11×11,$ центральная клетка которого совпадает с центральной клеткой квадрата $2017× 2017).$ Поскольку в рассматриваемом квадрате $121$ клетка, а цветов имеется всего лишь $120,$ он содержит две клетки одинакового цвета. Нетрудно понять, что эти две клетки всегда можно накрыть одним уголком, выступающим за пределы квадрата $11× 11,$ но целиком лежащим в большом квадрате.

$PIC$

Ошибка.
Попробуйте повторить позже

Задача 4#79335

Дано натуральное число $n.$ На доске выписаны все натуральные числа от $900...00$ до $1200...00$ (оба числа оканчиваются на $n$ нулей). У каждого из них выбрали делитель, меньший его самого. Докажите, что хотя бы два из этих делителей совпадают.

Показать доказательство

Положим для краткости $10n−1 = k.$ На доске выписаны натуральные числа от $90k$ до $120k$ . Рассмотрим выписанные числа, взаимно простые с 6. Таких чисел ровно $10k,$ поскольку среди любых шести подряд идущих чисел ровно два числа взаимно просты с $6$ (это числа, дающие остатки $1$ и $5$ при делении на $6$ ). Выпишем делители, которые мы выбрали у этих чисел. Эти делители по крайней мере в $5$ раз меньше исходного числа, значит, все они меньше $24k$ . Кроме того, они взаимно просты с $6,$ значит, их всего не более $8k.$ Таким образом, мы сопоставили каждому из $10k$ чисел делитель, причем всего делителей $8k.$ Следовательно, какие-то два делителя совпадают.

Ошибка.
Попробуйте повторить позже

Задача 5#79736

Натуральные числа от $1$ до $200$ разбили на $50$ множеств. Докажите, что в одном из них найдутся три числа, являющиеся длинами сторон некоторого треугольника.

Показать доказательство

Рассмотрим числа $100,101,...,200.$ Так как их всего $101,$ то по принципу Дирихле какие-то три из них попадут в одно множество. Сумма любых двух из этих трех чисел больше $200,$ и, следовательно, больше третьего числа. Значит, существует треугольник с соответствующими длинами сторон.

Ошибка.
Попробуйте повторить позже

Задача 6#79800

Несколько камней были разложены в $N$ кучек. Затем камни разложили по-другому, в $n < N$ кучек. Докажите, что какой-то камень попал в кучку большего размера, чем та, в которой он лежал изначально.

Показать доказательство

Каждому камню назначим вес обратный к числу камней в кучке, в которой он лежит. Тогда сумма $N$ весов до перекладывания больше суммы весов после перекладывания $n.$ Следовательно, вес хотя бы одного камня уменьшился, что и требовалось доказать.

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#82289

Клетчатый куб $9× 9× 9$ состоит из ячеек, представляющих из себя единичные кубики. 361 ячейка закрашена. Докажите, что в каком-то кубике $2× 2×2$ закрашено хотя бы четыре ячейки.

Источники: ИТМО-2024, 11.4 (см. olymp.itmo.ru)

Показать доказательство

Вырежем из нашего куба куб $8× 8×8$ и разобьём его на 64 куба $2×2 ×2$ .

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

В исходном кубе после этого остались кубики на трёх гранях, имеющих общую вершину. Рассмотрим 64 клетки на одной из этих граней, которые не лежат ни на какой из двух других. Они разбиваются на 16 квадратов $2×2$ , в каждом из которых не более трёх закрашенных ячеек. Итого на трёх гранях получаем не более $3× 16× 3=144$ .

У нас остались не рассмотренными 25 ячеек, образующих три ребра исходного куба, сходящиеся в одной вершине. Среди них закрашены не более 24, так как общая ячейка трёх этих рёбер и три её соседних лежат в одном кубике $2× 2× 2$ , значит, среди этих четырёх ячеек не более трёх закрашенных.

Таким образом, мы получаем максимум $192+144+ 24= 360$ закрашенных ячеек, что противоречит условию задачи. Значит, наше предположение было неверно.

Ошибка.
Попробуйте повторить позже

Задача 8#84365

Внутри правильного шестиугольника со стороной 1 расположено 7 точек. Докажите, что среди них найдутся две точки на расстоянии не больше 1.

Показать доказательство

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

Ошибка.
Попробуйте повторить позже

Задача 9#84366

Можно ли в таблице $n× n$ расставить числа $0$ , $1$ и $− 1$ так, чтобы все суммы чисел по вертикалям, горизонталям и двум главным диагоналям были различны?

Показать ответ и решение

В условии требуется, чтобы значения $2n+ 2$ сумм ( $n$ строк, $n$ столбцов и две диагонали) были различны. Каждая из этих сумм состоит из $n$ слагаемых, принимающих одно из значений $− 1$ , $0$ , $1$ . Поэтому каждая из сумм принимает целочисленное значение в диапазоне от $− n$ до $n$ . Всего возможных значений сумм — $(2n+ 1)$ . Поскольку $2n +1 <2n+ 2$ , какие-то две из сумм обязательно принимают равные значения.

Ответ: Нет

Ошибка.
Попробуйте повторить позже

Задача 10#85748

На одном берегу реки Нелли расположено $7$ сёл, а на — другом $57.$ Между каждыми двумя сёлами, находящимися на разных берегах, курсирует моторка одной из фирм “Сцилла” или “Харибда”. Докажите, что можно выбрать либо по два села на каждом берегу так, что все четыре линии между ними обслуживает фирма “Сцилла”, либо по шесть сёл на каждом берегу так, что все $36$ линий между ними обслуживает фирма “Харибда”.

Показать доказательство

Пусть $7$ сёл расположены на левом берегу, а $57$ — на правом. Пар сёл на левом берегу $7⋅6 =21. 2$ Если на правом берегу есть хотя бы $22$ села, из которых выходит хотя бы по два рейса фирмы «Сцилла», то по принципу Дирихле из них найдутся два села, из которых ведут по два рейса фирмы «Сцилла» в одну и ту же пару. В этом случае будет выполнено первое условие задачи. В противном случае на правом берегу будет хотя бы $57− 21= 36$ сёл, из которых ведут хотя бы шесть рёбер фирмы «Харибда». Так как на левом берегу мы можем выбрать $6$ сёл семью способами, по принципу Дирихле на правом берегу найдутся хотя бы $6$ сёл ( $36 7 > 5),$ из которых ведут по шесть рёбер фирмы «Харибда» в одну и ту же шестёрку сёл левого берега. В этом случае выполнено второе условие задачи.

Ошибка.
Попробуйте повторить позже

Задача 11#88270

Докажите, что из 52 целых чисел всегда найдутся два, разность квадратов которых делится на 100.

Показать доказательство

Если целых чисел больше 50, то по принципу Дирихле найдутся хотя бы два, которые дают одинаковые остатки при делении на 50. Обозначим их $n$ и $n +50k.$

Так как

2 2 2 2 (n +50k) =n +100⋅(nk +250k)1≡00n ,

то квадраты этих чисел дают одинаковые остатки при делении на 100. А значит, разность этих квадратов делится на 100.

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#96173

В ящике лежат шары: $5$ красных, $7$ синих и $1$ зелёный. Сколько шаров надо вынуть, не глядя, чтобы наверняка достать $2$ шара одного цвета?

Показать ответ и решение

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

Ответ:

Минимум $4$ шара

Ошибка.
Попробуйте повторить позже

Задача 13#96174

На шахматную доску $8×8$ поставили $33$ шахматных коня. Докажите, что какие-то два коня бьют друг друга. Напомним, что конь бьёт буквой Г: на $2$ клетки в одном направлении и на $1$ клетку в перпендикулярном.

Показать доказательство

Разобьем доску на $4$ квадрата $4× 4,$ в каком-то из них не меньше $9$ коней(по принципу Дирихле, иначе $8⋅4< 33).$ Разделим клетки этого квадрата на $4$ группы следующим образом:

$PIC$

По принципу Дирихле, в какой-то из этих групп хотя бы $3$ коня(снова, если $2,$ то $2⋅4< 9).$ Два коня из этой группы и будут бить друг друга.

Ошибка.
Попробуйте повторить позже

Задача 14#96176

У восьмерых друзей в сумме $713$ рублей (у каждого — целое число рублей).

(a) Докажите, что кто-то из них может купить пакет сока за $90$ рублей.

(b) Докажите, что какие-то двое из них, скинувшись, могут купить шоколадку за $179$ рублей.

Показать доказательство

(a) Заметим, что $89⋅8+1 =713.$ Тогда по принципу Дирихле, если “ящиками” будут дети, а “кроликами” $89$ рублей, то у кого-нибудь из детей будет хотя бы $89+1 =90$ рублей. Значит, он и сможет купить сок.

(b) Рассмотрим двух друзей, у которых наибольшее количество денег. Если они не могут купить шоколадку, то у них не больше $178$ рублей. Значит у какого-то из них по принципу Дирихле не больше $89.$ Так как его количество денег максимально, то у оставшихся $6$ не больше $89$ рублей. Итого, общее число денег не больше $178+6 ⋅89 <713.$ Противоречие.

(c) Рассмотрим теперь троих друзей с наибольшей суммой денег. Если они не могут купить торт, то у них не больше $267$ рублей. Значит у какого-то из них по принципу Дирихле не больше $89.$ Так как его количество денег максимально, то у оставшихся $5$ не больше $89$ рублей. Итого, общее число денег не больше $267+5 ⋅89< 713.$ Противоречие.

Ошибка.
Попробуйте повторить позже

Задача 15#96177

Каждая клетка таблицы $2015×2015$ покрашена в один из $2014$ цветов. За ход можно взять строку или столбец и, если там есть две клетки одного цвета, перекрасить эту строку или столбец в этот цвет. Всегда ли можно за несколько ходов покрасить всю таблицу в один цвет?

Показать ответ и решение

Возьмём любую строку. Так как цветов $2014,$ а клеток в строке — $2015,$ есть по крайней мере две клетки одного цвета. Значит, мы можем перекрасить всю строку в этот цвет. Воспользуемся этим и покрасим каждую строку в какой-нибудь цвет. Теперь у нас есть $2015$ строк, покрашенные в $2014$ цветов. Значит, по крайней мере две строки покрашены в один цвет (допустим, красный). То есть, в любом столбце есть две красные клетки. Покрасим все столбцы в красный цвет — все клетки доски будут покрашены в один цвет.

Ответ:

Да, всегда

Ошибка.
Попробуйте повторить позже

Задача 16#96178

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

Показать ответ и решение

Можно считать, что таблички стоят в вершинах правильного $n$ -угольника. Всего мы можем сделать $n− 1$ различный поворот, переводящий $n$ -угольник сам в себя, после чего снова получим начальное положение. Следовательно, вместе с начальным мы получим $n$ различных сочетаний табличек и неподвижно сидящих дипломатов. Так как мы будем двигать таблички по кругу, каждый дипломат на каком-нибудь шаге будет сидеть против своей таблички. Заметим, что в начальном положении все они сидели против чужих табличек. Поэтому на оставшиеся $n− 1$ сочетание приходится $n$ правильных положений(так как дипломатов всего $n).$ По принципу Дирихле найдётся поворот, при котором произойдут по крайней мере два правильных положения, что и означает, что можно повернуть стол так, чтобы не менее двух дипломатов сидело бы против своих табличек.

Ответ:

Да, можно

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#96232

Каждый из $65$ школьников написал по три контрольных работы и получил за каждую из них одну из оценок $2,$ $3,$ $4$ или $5.$ Докажите, что найдутся по крайней мере два школьника, получившие одинаковые оценки за каждую из работ.

Показать доказательство

Рассмотрим множество наборов из трёх оценок за соответствующие контрольные работы. Количество таких наборов равно $43 = 64$ (4 возможности за каждую из трёх контрольных работ). Поскольку число учащихся больше 64, то по принципу Дирихле каким-то двум ученикам соответствует один набор оценок.

Ошибка.
Попробуйте повторить позже

Задача 18#96233

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

Показать доказательство

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

Ошибка.
Попробуйте повторить позже

Задача 19#96234

Докажите, что если $21$ человек собрал $200$ орехов, то есть два человека, собравшие поровну орехов.

Показать доказательство

Если у всех разное число орехов, то всего было бы собрано не меньше $0+ 1+ 2+3 +...+ 20= 210$ орехов, что противоречит условию задачи.

Ошибка.
Попробуйте повторить позже

Задача 20#96236

Докажите, что из любых ста натуральных чисел можно выбрать несколько, сумма которых делится на $100.$

Показать доказательство

Рассмотрим последовательность из 100 чисел: $a ,a,...,a . 1 2 100$ Построим частичные суммы:

S1 = a1, S2 = a1+a2, ..., Sn = a1+ a2 +⋅⋅⋅+ an, n =1,2,...,100.

Рассмотрим остатки от деления частичных сумм на 100. Эти остатки могут принимать значения от 0 до 99. Таким образом, у нас есть 100 остатков и 100 частичных сумм.

Если хотя бы один из остатков равен 0, то существует частичная сумма, которая делится на 100, и утверждение доказано.

Если ни один остаток не равен 0, то по принципу Дирихле среди 100 остатков, каждый из которых принимает одно из 99 возможных значений (от 1 до 99), найдутся два одинаковых остатка. Пусть это будут остатки частичных сумм $S i$ и $S j$ для $i< j.$ Тогда:

Sj − Si ≡ 0 ( mod 100 )

что означает, что сумма $ai+1 +ai+2+⋅⋅⋅+aj$ делится на 100.