Maths Olympiad Prep

Library / /5 of 6

Combinatorics Difficulty 6.7 National Olympiad Prove it Thailand

There are 20162016 real numbers written on the blackboard. In each step, we choose two numbers, erase them, and replace each of them by their product. Determine whether it is possible to obtain 20162016 equal numbers on the blackboard after a finite number of steps.

(the 15th Czech-Polish-Slovak Mathematics Competition)

Solutions — 2

Solution 1

We shall prove that it is possible to obtain equal numbers after some finite steps by induction with respect to nn. The claim is trivial for n=2n = 2 (we can get the desired 22-tuple after a single step (a,b)(ab,ab)(a, b) \to (ab, ab)) and n=4n = 4 (we can follow the scheme (a,b,c,d)(ab,ab,c,d)(ab,ab,cd,cd)(abcd,ab,abcd,cd)(abcd,abcd,abcd,abcd)(\underline{a}, \underline{b}, c, d) \to (ab, ab, \underline{c}, \underline{d}) \to (\underline{ab}, ab, \underline{cd}, cd) \to (abcd, \underline{ab}, abcd, \underline{cd}) \to (abcd, abcd, abcd, abcd)).

To start the induction, we shall prove the claim also for n=6n = 6. The algorithm begins with the 66-tuple (a,a,a,a,b,b)(a, a, a, a, b, b) – this form can be achieved thanks to the fact that the claim is true for n=2n = 2 and n=4n = 4 (we can operate on the left 44-tuple and then independently on the right 22-tuple). To equalize all six numbers, perform the following steps:
(a,a,a,a,b,b)(a,a,a,ab,ab,b)(a,a,a2b,a2b,ab,b)(a,a,a2b,a3b2,a3b2,b)(a,a,a2b2,a3b2,a3b2,a2b2)(a3b2,a,a3b2,a3b2,a3b2,a2b2)(a3b2,a3b2,a3b2,a3b2,a3b2,a3b2) \begin{align*} (a, a, a, \underline{a}, \underline{b}, b) &\to (a, a, \underline{a}, \underline{ab}, ab, b) \to (a, a, a^2b, \underline{a^2b}, \underline{ab}, b) \to (a, a, \underline{a^2b}, a^3b^2, a^3b^2, \underline{b}) \\ &\to (\underline{a}, a, \underline{a^2b^2}, a^3b^2, a^3b^2, a^2b^2) \to (a^3b^2, \underline{a}, a^3b^2, a^3b^2, a^3b^2, \underline{a^2b^2}) \\ &\to (a^3b^2, a^3b^2, a^3b^2, a^3b^2, a^3b^2, a^3b^2) \end{align*}

Now, suppose the claim is true for all even n<4k+4n < 4k + 4 (with k1k \ge 1). It suffices to prove the claim also for n=4k+4n = 4k + 4 and n=4k+6n = 4k + 6. The procedure for n=4k+4n = 4k + 4 is obvious: we first equalize the first 2k+22k + 2 numbers using the induction hypothesis, and then equalize the last 2k+22k + 2 numbers. We get an nn-tuple of the form
(a,,a,b,,b)2k+2 \underbrace{(a, \dots, a, b, \dots, b)}_{2k+2}
and then perform 2k+22k + 2 steps to get (ab,,ab)(ab, \dots, ab) (choosing one aa and one bb in each step).

For n=4k+6n = 4k+6, we first use the induction hypothesis for n=2k+2n = 2k+2 and n=2k+4n = 2k+4 to get
(a,,a,b,,b)2k+2 \underbrace{(a, \dots, a, b, \dots, b)}_{2k+2}
Now we perform 2k2k steps, always choosing one aa and one bb, to obtain
(a,a,ab,,ab,b,b,b,b)4k \underbrace{(a, a, ab, \dots, ab, b, b, b, b)}_{4k}
After erasing each aa with one abab we get
(a2b,a2b,a2b,a2b,ab,,ab4k2,b,b,b,b) (a^2b, a^2b, a^2b, a^2b, \underbrace{ab, \dots, ab}_{4k-2}, b, b, b, b)
and after pairing each bb with one a2ba^2b we have
(a2b2,a2b2,a2b2,a2b2,ab,,ab4k2,a2b2,a2b2,a2b2,a2b2) (a^2b^2, a^2b^2, a^2b^2, a^2b^2, \underbrace{ab, \dots, ab}_{4k-2}, a^2b^2, a^2b^2, a^2b^2, a^2b^2)
Finally, we perform 2k12k-1 steps and replace 2k12k-1 times two abab's by two a2b2a^2b^2's, which leads to (a2b2,,a2b2)(a^2b^2, \dots, a^2b^2).

Solution 2

Again, we shall proceed by induction. The claim is trivial for n=2n = 2. Suppose the claim is true for n=kn = k and take n=k+2n = k + 2. Using the induction hypothesis, we first construct an nn-tuple of the form
(a,,a,b,b)k \underbrace{(a, \dots, a, b, b)}_{k}
For every i=3,4,,ki = 3, 4, \dots, k, we perform the operation with the numbers at the positions ii and k+1k+1. These k2k-2 steps change the nn-tuple into
(a,a,ab,a2b,,ak2b,ak2b,b). (a, a, ab, a^2b, \dots, a^{k-2}b, a^{k-2}b, b).
After selecting the last two numbers, we get
(a,a,ab,a2b,,ak2b,ak2b2,ak2b2). (a, a, ab, a^2b, \dots, a^{k-2}b, a^{k-2}b^2, a^{k-2}b^2).
Now, for every i=1,2,,n2i = 1, 2, \dots, \frac{n}{2}, we combine the numbers at the positions ii and n+1in+1-i, getting the desired
(ak1b2,ak1b2,,ak1b2). (a^{k-1}b^2, a^{k-1}b^2, \dots, a^{k-1}b^2).

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.