Предположим, что все гномы поздоровались. Рассмотрим первого гнома. Он поздоровался с двумя другими гномами, находящимися с ним в одной строке или столбце. Так как у гнома всего 2 соседа, он не может поздороваться со всеми остальными. Значит, найдется хотя бы один гном, который не поздоровался с первым.

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