Maths Olympiad Prep

Library / /151 of 264

Number theory Difficulty 5.9 AIME, harder Prove it Romania

Find the sum of the elements of the set
M={n2+m5m,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+5ba,b=1,2,,100}A = \{2a + 5b \mid a, b = 1, 2, \dots, 100\} and notice that 1A1 \notin A and 3A3 \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 697A697 \notin A and 699A699 \notin A.

We claim that all the integers between 44 and 695695 belong to AA.
Let y500y \le 500 and let rr be the remainder left by yy upon division by 55. Write y=5c+ry = 5c + r with 0c1000 \le c \le 100 and 0r40 \le r \le 4. If rr is even, then y=5c+2ky = 5c + 2k, where r=2kr = 2k. If rr is odd, then y5y \ge 5, so c1c \ge 1 and y=5(c1)+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 z200z \ge 200. If zz is even, then y=5100+2ky = 5 \cdot 100 + 2k, where z=2kz = 2k. If zz is odd, then y695y \le 695, so z195z \le 195 and y=599+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)=350697)=35697. 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,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.