Maths Olympiad Prep

Library / /5 of 5

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Romania

A 3×3×33 \times 3 \times 3 cube is divided into 27 unit-cubes. Call a strip any 1×1×31 \times 1 \times 3 rectangular cuboid (block) consisting of three unit-cubes.
A positive integer is written inside each unit-cube such that any number nn, strictly greater than 1, written in a unit-cube, is the sum of the numbers written inside three other unit-cubes, one from each of the three strips in which nn is situated. Prove that, regardless of the choice of the 27 numbers, there will be at least 16 among them that are smaller than or equal to 60.

Solution

If all the 27 numbers are equal to 1, we have nothing to prove. Assume the cube contains some numbers greater than 1 and suppose there is an even number between them. If nn is the smallest even number written inside a cube, then nn should be the sum of three odd numbers, which is impossible due to parity reasons. So all the 27 numbers are odd.
We shall prove that one of the numbers in every strip is equal to 1. Assuming the contrary, there is a strip that doesn't contain 1. If aa is the smallest number in this strip, then aa should be the sum of three numbers less than aa and greater than 1, a contradiction with the minimality of aa. It follows that each strip contains at least an 1, so at least 9 numbers inside the 3×3×33 \times 3 \times 3 cube are equal to 1.

Let a1a2a18a_1 \le a_2 \le \dots \le a_{18} the other numbers inside the big cube. If a1>3a_1 > 3, then one of three numbers whose sum is a1a_1 must be greater than 1 and less than a1a_1, which contradicts the choice made for a1a_1.
Therefore, a1{1,3}a_1 \in \{1,3\}, so a2{1,3,5}a_2 \in \{1,3,5\}. If a23a_2 \le 3, then a31+a1+a27a_3 \le 1+a_1+a_2 \le 7. If a2=5a_2 = 5, then a1a_1 and a2a_2 are on the same strip, so at most one of them may be used to write a3a_3 as a sum of three numbers from the cube. Hence, a31+1+a2=7a_3 \le 1+1+a_2 = 7, so consequently a3{1,3,5,7}a_3 \in \{1,3,5,7\}.

If a3=7a_3 = 7, it must exist a strip containing a2a_2 and a3a_3, so a2a_2 and a3a_3 cannot be simultaneously terms of expressing a4a_4 as a sum of three numbers inside the cube, so a4a3+a1+17+3+1=11a_4 \le a_3+a_1+1 \le 7+3+1 = 11. If a35a_3 \le 5, then a4a3+a2+a15+5+1=11a_4 \le a_3+a_2+a_1 \le 5+5+1 = 11. Therefore, a411a_4 \le 11.
More general, we have ak+3ak+2+ak+1+aka_{k+3} \le a_{k+2} + a_{k+1} + a_k.
If ak+1a_{k+1} and ak+2a_{k+2} are on a same strip, at most one of them may be used to write ak+3a_{k+3} as a sum of three numbers written in the unit-cubes. Since ak+2ak+1+ak+ak1a_{k+2} \le a_{k+1} + a_k + a_{k-1}, it follows that ak+3ak+2+ak+ak1ak+1+2ak+2ak1a_{k+3} \le a_{k+2} + a_k + a_{k-1} \le a_{k+1} + 2a_k + 2a_{k-1}.
If no strip contains ak+1a_{k+1} and ak+2a_{k+2}, since ak+2ak+ak1+ak2a_{k+2} \le a_k + a_{k-1} + a_{k-2}, we obtain ak+3ak+2+ak+1+akak+1+2ak+ak1+ak2ak+1+2ak+2ak1a_{k+3} \le a_{k+2} + a_{k+1} + a_k \le a_{k+1} + 2a_k + a_{k-1} + a_{k-2} \le a_{k+1} + 2a_k + 2a_{k-1}.
Subsequently, ak+3ak+1+2ak+2ak1a_{k+3} \le a_{k+1} + 2a_k + 2a_{k-1}, for each k2k \ge 2. Successively, we infer that a523a_5 \le 23, a635a_6 \le 35 and a759a_7 \le 59, so at least 16 numbers written inside the unit-cubes are either smaller than 60.

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.