На шахматной доске размера 11×11 стоят 37 королей. Докажите, что найдутся короли, которые бьют друг друга.(решить с помощью Дирихле)

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

Каждый король на шахматной доске угрожает клеткам, расположенным в непосредственной близости к нему — это клетки на горизонтали, вертикали и на диагоналях, а именно: 3 клетки в ряд впереди, 3 клетки в ряд сзади, 3 клетки в ряд по обе стороны и 2 клетки по диагоналям. Всего король контролирует 8 клеток вокруг себя.

Таким образом, если мы представим, что король занимает одну клетку на доске, он контролирует 8 клеток вокруг, что делает невозможным поставить другого короля в эти 9 клеток (включая ту, которую он занимает).

Теперь рассмотрим количество незанятых клеток. Если мы разделим доску на части, мы можем выделить множество "поддосок" (например, 3×3), в каждом из которых может находиться не более 1 короля, так как любой король внутри такой "поддоски" будет угрожать королю, находящемуся в соседних "поддосках".

На доске 11×11 у нас 121 клетка. Разделим доску на 3×3 квадраты. Всего мы можем получить 36 поддосок по 3×3 (108 клеток) и останутся еще 13 клеток, которые не входят в полный квадрат. С учетом того, что каждая из 36 поддосок может иметь всего по одному королю, максимальное количество королей, которое мы можем разместить на доске без угрозы друг другу, составляет 36.

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

Таким образом, мы доказали, что на шахматной доске 11×11 с 37 королями обязательно найдутся короли, которые бьют друг друга.