Question

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

Answer 1

Ответ:

Если найдутся пуговицы 11 разных цветов, тогда всё доказано. Значит, в дальнейшем, можно предполагать, что все пуговицы содержат не более 10 цветов.

Предположим, что ни для одного цвета не найдется 11 пуговиц, то всего не более 10*10 = 100 пуговиц. Однако у нас 101 пуговица, значит наше предположение не верно, и имеется 11 пуговиц одного цвета.

Answer 2

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

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

Теперь мы можем применить принцип Дирихле. У нас есть 101 объект, размещенный в 11 ящиках (цветах). При этом 101 > 11. Следовательно, как минимум один из ящиков (цветов) должен содержать две или более пуговицы того же цвета, что доказывает первую часть утверждения: "среди этих пуговиц найдутся 11 пуговиц одного цвета."

Теперь давайте рассмотрим вторую часть утверждения: "либо 11 пуговиц разных цветов." Если в первой части у нас уже есть 11 пуговиц одного цвета, то оставшиеся 90 пуговиц будут иметь разные цвета, и это подтверждает вторую часть утверждения.

Таким образом, мы доказали, что либо среди этих пуговиц найдутся 11 пуговиц одного цвета, либо 11 пуговиц разных цветов, в соответствии с принципом Дирихле.