Maths Olympiad Prep

Track / Stage 6 / 52 of 400 #1532 of 2444

Problem 1532

National Olympiad, first round
Number theory Difficulty 6.0 Prove it Ukrainian National Mathematical Olympiad · Ukraine

After xx matches in a championship a team had exactly n%n\% of wins, where x,nx, n are positive integers. What is the least xx for which it is possible that after x+1x+1-st match the team had exactly (n+1)%(n+1)\% of wins?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

It follows from the conditions of the problem that after xx matches the team had yy wins, such that yx=n100\frac{y}{x} = \frac{n}{100}. Then, the following has to hold: y+1x+1=n+1100\frac{y+1}{x+1} = \frac{n+1}{100}.

The first equation implies 100y=nx100y = nx, and so 100100 has to divide nxnx.
The second equation implies 100y+100=nx+x+n+1100=x+n+1100y + 100 = nx + x + n + 1 \Rightarrow 100 = x + n + 1.
Hence x=100n198x = 100 - n - 1 \le 98. Moreover, n=100x1xn=100xx2xn = 100 - x - 1 \Rightarrow xn = 100x - x^2 - x. Therefore, 100100 has to divide x2+xx^2 + x. Since x2+x=x(x+1)x^2 + x = x(x+1) and the numbers xx and x+1x+1 are relatively prime and less than 100100, one of the numbers has to be divisible by 44, and the other by 2525. Clearly, the smallest such number is x=24x = 24. Thus, n=75n = 75 and y=18y = 18. It is easy to check that
yx=1824=75% and y+1x+1=1925=76% \frac{y}{x} = \frac{18}{24} = 75\% \text{ and } \frac{y+1}{x+1} = \frac{19}{25} = 76\%

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