Maths Olympiad Prep

Library / /47 of 91

Combinatorics Difficulty 6.0 AIME, harder Prove it India

Let nn be an odd natural number. We consider an nn by nn grid which is made up of n2n^2 unit squares and 2n(n+1)2n(n+1) edges. We colour each of these edges either red or blue. If there are at most n2n^2 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
2n2unit squares(red edges of the square)=red edges(unit squares containing the edge)2n2. 2n^2 \le \sum_{\text{unit squares}} \text{(red edges of the square)} = \sum_{\text{red edges}} \text{(unit squares containing the edge)} \le 2n^2.
This implies that each unit square has exactly two red edges and that there are a total of n2n^2 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 n2/2n^2/2, 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.