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

модуль 1.3 шаг 4

В ящике лежат десять белых и двенадцать черных носков. Какое минимальное количество носков нужно вытащить, чтобы на выходе гарантированно получить пару носков одинакового цвета?

Решение

мысленно представил всевозможные варианты случайных выборок, и получилось что как бы не случилось, но вытащив наугад хотя бы три пары, среди них будут две пары носков одинакового цвета. Сначала представил что вытащил одну пару носков и получилось что возможен вариант когда будет 1 пара белых и 1 пара черных носков среди вытащенных - значит 2 не подходит.

Потом представил какие возможны исходы если число вытащеных носков равно трем:

A) белые, белые , белые - в этом наборе есть 2 пары белых носков

B) черные, черные черные - в этом наборе есть 2 пары черных носков

С) белые, белые, черные - есть

D) черные, черные, белые -есть

Ответ

модуль 1.3 шаг 5

Какое максимальное количество королей можно поместить на шахматную доску (стандартного размера, 8 × 8) так, чтобы эти короли не били друг друга?

Решение

Ответ

модуль 1.3 шаг 6

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

Решение По сути, у нас 20 ящиков - супружеских пар. Нам нужно, чтобы хотя бы в одном из них собрались муж и жена. Если мы будем делать это самым медленным способом, то сначала мы заполним ящики женами (или мужьями), а затем уже придется добавить одного супруга противоположного пола, что и приведет к желаемому исходу. Аналогичная задача: есть 20 синих шариков, 20 красных и 20 коробок. Какой минимум шариков нужно взять вслепую, чтобы хотя бы в одной коробке гарантированно оказались шарики разного цвета при условии, что ни одна из них не пустует?

Ответ

модуль 1.3 шаг 7

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

Решение аналогично предыдущей,

если в году 12 месяцев, то выборка каждого месяца по 2 раза будет 24, с переходом на третий год плюс один нужный месяц 24+1 = 25

Ответ

модуль 1.3 шаг 8

Сколько чисел нужно выбрать из последовательности {1,2,3,…,20}, чтобы среди них гарантированно нашлась хотя бы одна пара чисел, сумма которых была бы равна 21?

Решение

21 = 1 + 20 = 2 + 19 = … = 10 + 11. Всего таких пар 10 штук.

Пусть будет 10 ящиков, соответствующих парам.

Выбираем какое-то число. Например, мы выбрали 7. Тогда положим его в ящик, соответствующий паре (7, 14). Если мы выберем 10 чисел, то либо в каком-то ящике будет 2 числа (т.е нашлась пара), либо во всех ящиках будет по одному числу. Рассмотри худший случай: во всех ящиках по одному числу. Взяв ещё одно число, то оно попадёт в какой-то ящик, в котором уже есть число. Т.е 11 гарантировано, что есть пара в ящике.

Ответ