Question

Девять гномов трижды становились по одному в клетки квадрата3 х 3, и каждый раз гномы, оказавшиеся в соседних по стороне клетках, здоровались друг с другом. Докажите, что найдутся какие-то два гнома, которые так и не поздоровались

Answer 1

Понятно, что в середине квадрата не могло стоять больше 3 гномов, так что, как минимум, 6 гномов не побывали в середине квадрата и стояли за все время только в боковых клетках). Из этих 6 гномов никакой не должен был стоять два раза в углу (тогда бы он поздоровался только с 2+2+3=7 другими гномами, а должен поздороваться с 8 другими гномами). Тогда каждый из этих гномов стоял, как минимум, два раза на границе квадрата (но не на самых угловых клетках). Всего таких клеток за три раза было 4*3=12. Значит, только эти 6 гномов стояли в этих 12 клетках (так как 6*2 будет ровно 12). Из этого следует, что трое гномов, стоявших в средней клетке в остальные два раза стояли в угловых клетках и не здоровались друг с другом (угловые клетки на соприкасаются друг с другом стороной; если же это был один гном, то остается еще 8 гномов на 12 клеток, и условие задачи опять не выполняется).  Ч. т. д.