There are 2016 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 2016 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 n. The claim is trivial for n=2 (we can get the desired 2-tuple after a single step (a,b)→(ab,ab)) and n=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)).
To start the induction, we shall prove the claim also for n=6. The algorithm begins with the 6-tuple (a,a,a,a,b,b) – this form can be achieved thanks to the fact that the claim is true for n=2 and n=4 (we can operate on the left 4-tuple and then independently on the right 2-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)
Now, suppose the claim is true for all even n<4k+4 (with k≥1). It suffices to prove the claim also for n=4k+4 and n=4k+6. The procedure for n=4k+4 is obvious: we first equalize the first 2k+2 numbers using the induction hypothesis, and then equalize the last 2k+2 numbers. We get an n-tuple of the form 2k+2(a,…,a,b,…,b) and then perform 2k+2 steps to get (ab,…,ab) (choosing one a and one b in each step).
For n=4k+6, we first use the induction hypothesis for n=2k+2 and n=2k+4 to get 2k+2(a,…,a,b,…,b) Now we perform 2k steps, always choosing one a and one b, to obtain 4k(a,a,ab,…,ab,b,b,b,b) After erasing each a with one ab we get (a2b,a2b,a2b,a2b,4k−2ab,…,ab,b,b,b,b) and after pairing each b with one a2b we have (a2b2,a2b2,a2b2,a2b2,4k−2ab,…,ab,a2b2,a2b2,a2b2,a2b2) Finally, we perform 2k−1 steps and replace 2k−1 times two ab's by two a2b2's, which leads to (a2b2,…,a2b2).
Solution 2
Again, we shall proceed by induction. The claim is trivial for n=2. Suppose the claim is true for n=k and take n=k+2. Using the induction hypothesis, we first construct an n-tuple of the form k(a,…,a,b,b) For every i=3,4,…,k, we perform the operation with the numbers at the positions i and k+1. These k−2 steps change the n-tuple into (a,a,ab,a2b,…,ak−2b,ak−2b,b). After selecting the last two numbers, we get (a,a,ab,a2b,…,ak−2b,ak−2b2,ak−2b2). Now, for every i=1,2,…,2n, we combine the numbers at the positions i and n+1−i, getting the desired (ak−1b2,ak−1b2,…,ak−1b2).
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.