Maths Olympiad Prep

Library / /434 of 462

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Ireland

The country of Harpland has three types of coin: green, white and orange.
The unit of currency in Harpland is the shilling. Any coin is worth a positive integer number of shillings, but coins of the same colour may be worth different amounts. A set of coins is stacked in the form of an equilateral triangle of side nn coins, as shown below for the case of n=6n = 6.

Figure 1

The stacking has the following properties:
1. no coin touches another coin of the same colour;
2. the total worth, in shillings, of the coins lying on any line parallel to one of the sides of the triangle is divisible by three.

Prove that the total worth in shillings of the green coins in the triangle is divisible by three.

Solution

Without loss of generality the coins form the pattern shown below.

Figure 2

Let GG, WW and OO denote the total worth in shillings of the green, white and orange coins in the triangle, respectively. The problem reduces to showing that GG, WW and OO are all divisible by three. Now fix some green coin gg' in the triangle, and consider a subset of the lines parallel to the sides of the triangle, such that every third parallel line is included, and all lines passing through gg' are included; this is illustrated below.

Figure 3

Since the total worth of the coins on each line is divisible by 33, so is the sum of these quantities. However these lines contain each white coin exactly once, each orange coin exactly once, and a subset SS of the green coins exactly 33 times. We thus have
W+O+3G0(mod3) W + O + 3G' \equiv 0 \pmod{3}
where GG' denotes the total worth of the green coins lying in the set SS. Therefore
W+O0(mod3). W + O \equiv 0 \pmod{3}.

But summing the worth of the coins in all lines parallel to one side of the triangle, we obtain
G+W+O0(mod3). G + W + O \equiv 0 \pmod{3}.
Subtraction of these two congruences yields
G0(mod3), G \equiv 0 \pmod{3},
and application of the same reasoning proves that WO0(mod3)W \equiv O \equiv 0 \pmod{3}.

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.