Question

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

Answer 1

Необходимо достать минимум 5 яблок. 
3 яблока одного сорта и по 1 яблоку других сортов

Answer 2

Для решения этой задачи можно воспользоваться принципом Дирихле, который утверждает, что если $n+1$ объектов распределены по $n$ ящикам, то в одном из ящиков обязательно окажется хотя бы два объекта. Применяя этот принцип к данной задаче, мы можем утверждать, что если мы вытащим 4 яблока любых сортов, то среди них обязательно найдутся 3 яблока одного сорта.

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

Таким образом, мы доказали, что нам достаточно вынуть из корзины 4 яблока любых сортов, чтобы гарантированно обнаружить среди них 3 яблока одного сорта.