Maths Olympiad Prep

Library / /41 of 63

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Japan

There are three distinct positive integers written on the blackboard. When real numbers aa, bb, cc are on the blackboard, consider the procedure that replaces those three numbers with b+c2\frac{b+c}{2}, c+a2\frac{c+a}{2}, a+b2\frac{a+b}{2} at the same time. After this procedure is done 20212021 times, all three numbers on the blackboard are positive integers. Determine the minimum value of the sum of initial three positive integers on the blackboard.

Solution

322021+33 \cdot 2^{2021} + 3

For integers n=0,,2021n = 0, \dots, 2021, let abca \le b \le c be three numbers on the blackboard after the procedure is done nn times and let pn=cbp_n = c - b, qn=baq_n = b - a. Here n=0n = 0 means the initial status. When the procedure is done once, three numbers abca \le b \le c are replaced with a+b2a+c2b+c2\frac{a+b}{2} \le \frac{a+c}{2} \le \frac{b+c}{2} hence pn+1=ba2=qn2p_{n+1} = \frac{b-a}{2} = \frac{q_n}{2}, qn+1=cb2=pn2q_{n+1} = \frac{c-b}{2} = \frac{p_n}{2} holds. Therefore p2021=q022021p_{2021} = \frac{q_0}{2^{2021}}, q2021=p022021q_{2021} = \frac{p_0}{2^{2021}}. Initial three numbers are distinct thus neither of p0,q0p_0, q_0 is 00 and then neither of p2021,q2021p_{2021}, q_{2021} is 00. All three numbers after 20212021 procedures are positive integers hence p20211p_{2021} \ge 1, q20211q_{2021} \ge 1 and p022021p_0 \ge 2^{2021}, q022021q_0 \ge 2^{2021}. The minimum number of initial three numbers is greater than or equal to 11 thus the sum of initial three numbers is greater than or equal to 1+(1+22021)+(1+222021)=322021+31 + (1 + 2^{2021}) + (1 + 2 \cdot 2^{2021}) = 3 \cdot 2^{2021} + 3.

We show 11, 1+220211 + 2^{2021}, 1+2220211 + 2 \cdot 2^{2021} satisfy the condition of initial three numbers. Discussion above shows p2021=1p_{2021} = 1, q2021=1q_{2021} = 1. The sum of three numbers is kept unchanged by the procedure thus the sum is 322021+33 \cdot 2^{2021} + 3 after 20212021 procedures. Therefore three numbers after 20212021 procedures are 220212^{2021}, 22021+12^{2021} + 1, 22021+22^{2021} + 2 and these are all integers. Hence the answer is 322021+33 \cdot 2^{2021} + 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 and solution reproduced as published; topic and difficulty added by this site.