Question

Задача на логику (много баллов!): у сони в рюкзаке лежат конфеты, большие и маленькие, 8 разных цветов. она достает не глядя. сколько конфет достанет соня, чтобы наверняка найти 2 одинаковые по цвету и размеру конфеты, если ей постоянно попадается не то, что надо?

Answer 1

Разобьём условно конфеты в рюкзаке Сони на 16 кучек: большие (8 цветов) и маленькие (8 цветов). Если Соня достанет не больше 16-ти конфет, они все могут оказаться из разных кучек. Если Соня достанет 17 конфет, среди них окажутся две конфеты из одной кучки по принципу Дирихле (если из каждой кучки взято не больше одной конфеты, всего взято не больше 16-ти конфет, а 16 < 17).

Ответ: 17 конфет.

Answer 2

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

У нас есть 8 разных цветов конфет, и каждый цвет имеет два размера (большой и маленький). Таким образом, у нас есть 8 различных комбинаций цвет-размер.

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

Худший сценарий будет, если Соня каждый раз будет доставать конфеты с разными цветами и размерами. В этом случае она достанет 7 конфет (потому что после доставания 8-й конфеты, у нее обязательно окажется две конфеты одного цвета и размера).

Таким образом, Соня достанет как минимум 7 конфет, чтобы наверняка найти две одинаковые по цвету и размеру конфеты.