Maths Olympiad Prep

Library / /48 of 49

, 2022

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it Bulgaria

An equilateral triangle TT with side length 20222022 is coloured in white and partitioned into equilateral triangles with side length 11 (called cells) through lines, parallel to the sides of TT. Two cells are called adjacent if they have at least one vertex in common. Ivan colors some of the cells in black. Without seeing which cells are black, Peter selects only once a set SS of cells (containing at least one) and asks Ivan if the number of blacks among the selected ones is even or odd. After receiving an answer, Peter is able to tell if the number of pairs of differently colored adjacent cells in TT is even or odd. Find all possible values of the number of elements of SS if that is always possible no matter the coloring of Ivan.

Solution

For simplicity we write AA instead of Ivan and BB instead of Peter. The crucial idea is in the following

Lemma. In the graph GG all vertices are initially colored white. Let AA colors some of the vertices in black and BB asks AA about the parity of the number of blacks in a set SS from vertices, and with the answer can unambiguously determine the parity of the number of differently colored pairs adjacent/vertices in GG. Then SS must be the set of all vertices of odd degree in GG.

Proof. We will work by modulus 22. We write the number 11 in each black vertex, the number 00 in each white vertex and the sum of the numbers in its vertices on each edge. Each black vertex of odd degree contributes 11 to the sum of the numbers on the edges, each black vertex of even degree contributes 00, and each white vertex also contributes 00. Therefore, the sum of the numbers on the edges in GG has the same parity as that of the number of black vertices of odd degree in GG. Thus, when asked about the set NN of the vertices of odd degree, we are ready. Conversely, for a question with a set other than NN, we cannot unambiguously restore the parity of the number of black vertices in NN and the lemma is proved.

It remains to count the number of cells with an odd number of adjacent cells in TT. Each cell that has no common point with the perimeter of TT has 1212 adjacent cells. The three cells on the perimeter, each of which is adjacent on the side of a corner cell in TT, have 66 adjacent cells. Each cell with a side on the perimeter has 77 adjacent cells, and each cell with a vertex (but not a side) on the perimeter (except the three mentioned above) has 99 adjacent cells. Because each side of TT has at least one common point with 2×202212 \times 2022 - 1 cells, and each two sides have two common cells (as only one is of odd degree), the required number is 3×(2×20225)+3=121203 \times (2 \times 2022 - 5) + 3 = 12120.

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.