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


			
Рассмотрим некоторую (бесконечную) 
 строку и все строки, идущие через одну клетку от нее. 
 Клетки каждой из этих строк окрасим через одну красным и желтым. 
 Рассмотрим оставшиеся строки. 
 Клетки каждой из этих строк окрасим через одну синим  и зеленым. 
 Таким образом, каждая клетка получила свой цвет и никакие две 
 клетки одного цвета не соприкасаются. 
 Остается заметить, что так как отмечено 2000 клеток, то клеток 
 хотя бы одного из цветов не меньше 2000/4=500 
 (по принципу Дирихле).
			
Вспомогательная раскраска (прочее)