Question

На доске 50 на 50 стоят 625 королей,не бьющих друг друга. Какое наименьшее количество королей может стоять по краям доски?

Answer 1

Рассмотрим квадрат 2X2, в нём может стоять не более 1 короля. Рассмотрим квадрат 48X48, в нём 576 квадратов 2X2, следовательно, не более 576 королей. 625 - 576 = 49 (не менее 49 королей на краю). Пример: раскраска квадрата 50X50 в 4 цвета так, чтобы в любом квадрате 2X2 были все 4 цвета, в жёлтые клетки ставим королей.
Ответ: 49.

Answer 2

Давайте рассмотрим ситуацию: наименьшее количество королей по краям доски будет, когда они будут занимать только один ряд или один столбец на каждой из сторон доски.

Если короли стоят только в одном ряду по краю доски, то на одной стороне будет 50 королей (по ширине доски), а на другой стороне не останется места для королей.

Если короли стоят только в одном столбце по краю доски, то на одной стороне будет также 50 королей (по высоте доски), а на другой стороне ситуация аналогична предыдущей, не останется места.

Итак, наименьшее количество королей по краям доски составляет 50 королей на каждой стороне, в общей сложности 100 королей (50 слева и 50 справа или 50 сверху и 50 снизу).