Let be an odd natural number. We consider an by grid which is made up of unit squares and edges. We colour each of these edges either red or blue. If there are at most red edges, then show that there exists a unit square at least three of whose edges are blue.
Solution
Suppose on the contrary that each unit square has at least two red edges. Each red edge is part of at most two unit squares. Therefore
This implies that each unit square has exactly two red edges and that there are a total of red edges.
We colour each of the unit squares black and white such that no two unit squares which share a common edge have the same colour (like in a chess board). Note that each red edge is part of exactly one black square and one white square. Since every unit square has exactly two red edges, the number of white squares is therefore , a contradiction since this is not an integer.
This shows that there is a unit square with at most one red edge.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.