each cells in a $9\times 9 $ grid is painted either blue or red.two cells are called diagonal neighbors if their intersection is exactly a point.show that some cell has exactly two red neighbors,or exactly two blue neighbors, or both.
Problem
Source:
Tags: analytic geometry, combinatorics proposed, combinatorics
S. E. Puelma Moya
22.03.2011 20:58
mousavi wrote: each cells in a $9\times 9 $ grid is painted either blue or red.two cells are called diagonal neighbors if their intersection is exactly a point.show that some cell has exactly two red neighbors,or exactly two blue neighbors, or both. Solution:
Some abreviations: DN=diagonal neighbors, B=blue cell, R=red cell.
We are going to use coordinates $(i,j)$ for the cell in the intersection of row $i$ and column $j$
Assume that there is no cell with exactly two red DN and/or exactly two blue DN. Each cell in contact with exactly one border of the grid has exactly two DN, then one of them is R and the other is B. This property will be called (P)
Assume WLOG that (2,2) is R. Using (P) for cells (1,3), (1,5), (1,7), (3,9), (5,9), (7,9), (9,7), (9,5), (9,3), (7,1), (5,1) and (3,1) (in this order), we get tat cells (2,6), (4,8), (8,8), (8,4) and (6,2) are R, and cells (2,4), (2,8), (6,8), (8,6), (8,2) and (4,2) are blue.
Cells (3,3) and (7,3) can't have exactly two red DN, then cells (4,4) and (6,4) are R. Cells (3,7) and (7,7) can't have exactly two blue DN, then cells (4,6) and (6,6) are R. This is a contradiction since cell (5,5) has two DN of each color.