Maths Olympiad Prep

Library / Japan Mathematical Olympiad /60 of 84

Japan Mathematical Olympiad

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

3⋅22021+33 \cdot 2^{2021} + 3

For integers n=0,…,2021n = 0, \dots, 2021, let a≤b≤ca \le b \le c be three numbers on the blackboard after the procedure is done nn times and let pn=c−bp_n = c - b, qn=b−aq_n = b - a. Here n=0n = 0 means the initial status. When the procedure is done once, three numbers a≤b≤ca \le b \le c are replaced with a+b2≤a+c2≤b+c2\frac{a+b}{2} \le \frac{a+c}{2} \le \frac{b+c}{2} hence pn+1=b−a2=qn2p_{n+1} = \frac{b-a}{2} = \frac{q_n}{2}, qn+1=c−b2=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 p2021≥1p_{2021} \ge 1, q2021≥1q_{2021} \ge 1 and p0≥22021p_0 \ge 2^{2021}, q0≥22021q_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+2⋅22021)=3⋅22021+31 + (1 + 2^{2021}) + (1 + 2 \cdot 2^{2021}) = 3 \cdot 2^{2021} + 3.

We show 11, 1+220211 + 2^{2021}, 1+2⋅220211 + 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 3⋅22021+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 3⋅22021+33 \cdot 2^{2021} + 3.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.