Question

Есть коробка с 10 одинаковыми парами обуви. Какое минимальное количество обуви, которую надо вытащить из коробки, что бы среди вытащенной обуви обязательно была бы пара? Пожалуйста, с решением. Это комбинаторика.

Answer 1

11 штук обуви. Ведь есть случай, когда все 10 вытащенных туфель - разные. Но 11-ая станет парой какой-либо из них.

Answer 2

Чтобы убедиться, что среди вытащенной обуви обязательно будет пара, нужно вытащить хотя бы 2 обуви.

Если первая вытащенная обувь не имеет пары, то для того, чтобы обязательно найти пару нужно вытащить еще 9 обувей (оставшиеся 9 пар), итого 10 обувей.

Если первая вытащенная обувь имеет пару, то чтобы обязательно найти еще одну пару, нужно вытащить еще 8 обувей (оставшиеся 8 пар), итого 9 обувей.

Таким образом, минимальное количество обуви, которое нужно вытащить из коробки, чтобы среди вытащенной обуви обязательно была бы пара, равно 2.

Решение основано на принципе Дирихле (Принцип ящиков Дирихле): если n + 1 объектов распределить по n ящикам, то хотя бы в одном ящике будет не менее двух объектов. В данной задаче "объектов" - это обувь, "ящиков" - это пары обуви.