Maths Olympiad Prep

Library / Romanian Mathematical Olympiad /158 of 275

Romanian Mathematical Olympiad

Number theory Difficulty 5.9 AIME, harder Prove it Romania

Find the sum of the elements of the set
M={n2+m5∣m,n=0,1,2,…,100}. M = \left\{ \frac{n}{2} + \frac{m}{5} \mid m, n = 0, 1, 2, \dots, 100 \right\}.

Solution

Consider the set A={2a+5b∣a,b=1,2,…,100}A = \{2a + 5b \mid a, b = 1, 2, \dots, 100\} and notice that 1∉A1 \notin A and 3∉A3 \notin A.

The largest even number from AA is equal to 700700 and it is obtained for a=b=100a = b = 100. The number 698698 is obtained for a=99,b=100a = 99, b = 100. The largest odd number from AA is equal to 695695 and it is obtained for b=99,a=100b = 99, a = 100, implying that 697∉A697 \notin A and 699∉A699 \notin A.

We claim that all the integers between 44 and 695695 belong to AA.
Let y≤500y \le 500 and let rr be the remainder left by yy upon division by 55. Write y=5c+ry = 5c + r with 0≤c≤1000 \le c \le 100 and 0≤r≤40 \le r \le 4. If rr is even, then y=5c+2ky = 5c + 2k, where r=2kr = 2k. If rr is odd, then y≥5y \ge 5, so c≥1c \ge 1 and y=5(c−1)+2(k+3)y = 5(c - 1) + 2(k + 3), where r=2k+1r = 2k + 1.

For y>500y > 500, write y=500+zy = 500 + z with z≥200z \ge 200. If zz is even, then y=5⋅100+2ky = 5 \cdot 100 + 2k, where z=2kz = 2k. If zz is odd, then y≤695y \le 695, so z≤195z \le 195 and y=5⋅99+2(k+3)y = 5 \cdot 99 + 2(k + 3), where z=2k+1z = 2k + 1. A quick inspection of all the above cases shows that the claim holds.

S=110((1+2+⋯+700)−(1+3+697+699)=350⋅697)=35⋅697. S = \frac{1}{10}((1 + 2 + \dots + 700) - (1 + 3 + 697 + 699) = 350 \cdot 697) = 35 \cdot 697.

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.