Олимпиады · 5–6 классыПринцип Дирихле

Олимпиада, 5–6 класс: принцип Дирихле — «обязательно найдутся»

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

Вариант № 28682

Олимпиада, 5–6 класс: принцип Дирихле — «обязательно найдутся» · Вариант № 28682 · Школьный тур · Имя: ____________________

1
Из чисел $1, 2, \dots, 10$ выбирают несколько. Какое наименьшее число выбранных гарантирует, что среди них найдутся два числа, одно из которых делится на другое?
Ответ: 6
Разобьём числа $1,\dots,10$ по «нечётной части»: $5$ групп вида «нечётное число, умноженное на степени двойки» — в группе любые два числа делятся друг на друга.
Можно выбрать по числу из каждой группы, например числа $6,\dots,10$ : ни одно не делится на другое. Это $5$ чисел.
Но $6$ чисел обязательно дадут два из одной группы — они делятся друг на друга. Ответ $6$ .
2
В школе 77 учеников. Для какого наибольшего числа $k$ можно гарантировать, что хотя бы $k$ из них родились в один и тот же месяц года?
Ответ: 7
Ящиков (возможных значений) — $12$ . Допустим, в каждом не более $k-1$ учеников: тогда всего их не более $12(k-1)$ .
При $n=77$ это невозможно, если $12(k-1)<77$ , то есть при $k-1<\frac{77}{12}$ .
Следовательно, обязательно найдётся ящик не менее чем с $\lceil 77/12\rceil=7$ учениками; больше гарантировать нельзя — можно распределить учеников почти поровну.
3
Из чисел $1, 2, \dots, 14$ выбирают несколько. Какое наименьшее число выбранных гарантирует, что среди них найдутся два числа, одно из которых делится на другое?
Ответ: 8
Разобьём числа $1,\dots,14$ по «нечётной части»: $7$ групп вида «нечётное число, умноженное на степени двойки» — в группе любые два числа делятся друг на друга.
Можно выбрать по числу из каждой группы, например числа $8,\dots,14$ : ни одно не делится на другое. Это $7$ чисел.
Но $8$ чисел обязательно дадут два из одной группы — они делятся друг на друга. Ответ $8$ .
4
Из чисел $1, 2, \dots, 9$ выбирают несколько. Какое наименьшее число выбранных гарантирует, что среди них найдутся два числа, разность которых делится на 3?
Ответ: 4
Разобьём числа по остаткам при делении на $3$ — $3$ «ящиков» (остатки $0,1,\dots,2$ ).
Можно выбрать по одному числу с каждым остатком: $3$ чисел, и разности на $3$ не делятся.
Но среди $4$ чисел какие-то два лежат в одном ящике, а их разность делится на $3$ . Ответ $4$ .
5
В тёмной комнате в коробке лежат 9 красных и 9 синих шаров. Сколько шаров нужно вытащить наугад в темноте, чтобы среди них гарантированно нашлось два одного цвета?
Ответ: 3
Худший случай: каждого цвета вытащено не больше $1$ (или все, если их меньше): 1 + 1 = 2.
Любой следующий уже даст пару одного цвета. Ответ: $2+1=3$ .

Коротко о теме

Если $n$ предметов разложены по $m$ ящикам, то в каком-то ящике не меньше $\lceil n/m\rceil$ предметов.
Чтобы гарантировать $k$ одинаковых из $m$ видов, нужно взять $m(k-1)+1$ предметов.
Наименьшее число, которое гарантирует «пару», на 1 больше наибольшего числа, при котором пары ещё может не быть.
Ящики придумываем так, чтобы два предмета из одного ящика уже давали то, что ищем.
Уровни: «Разминка» — тренировочная задача на одну идею, «Обычный» — задача школьного тура, «Challenge» — уровень регионального этапа (идеи нужно соединять).

Уровни: Тренировочная · Школьный тур · Региональный этап. Все ответы вычислены программой из тех же чисел, что и условие.

Ещё тренажёры

Другие темы: 5 класс