Question

В двух коробках лежат башмаки трех цветов: в левой коробке - 16 зелёных, 5 жёлтых и 5 чёрных (все - на левую ногу), в правой коробке - 14 зелёных, 7 жёлтых и 7 чёрных (все
- на правую ногу). Жора может достать несколько башмаков из левой коробки и несколько (возможно, другое количество) из правой. Все башмаки нужно доставать одновременно и не глядя. Какое минимальное число башмаков ему надо вытащить (суммарно из левой и правой коробок), чтобы среди них обязательно нашлась пара башмаков одного цвета на левую и правую ногу?

Answer 1

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

В данной задаче у нас есть 3 цвета башмаков (зеленый, желтый, черный) и две коробки (левая и правая). Мы хотим найти минимальное число башмаков, которое нужно вытащить, чтобы гарантированно найти пару башмаков одного цвета для левой и правой ноги.

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

Ответ: Жоре нужно вытащить минимум 2 башмака (по одному из каждой коробки), чтобы среди них обязательно нашлась пара башмаков одного цвета для левой и правой ноги