Question

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

Answer 1

Заметим, что в любом квадрате 2×2 может находиться не более одного короля. Поскольку квадрат размера 2n×2n можно разбить на n^2 квадратов 2×2, то в таком квадрате может находиться не более n^2 королей, не бьющих друг друга.

Если отбросить все клетки доски 50×50, лежащие у края доски, то останется квадрат 48×48, в котором по написанному выше может быть не больше 24^2 не бьющих друг друга королей. Значит, в клетках у края будет не менее 625 - 24^2 = 25^2 - 24^2 = 49 королей. 

Пример расстановки, при которой достигается это значение, изображён на рисунке, К соответствует позиции королей.