Maths Olympiad Prep

Library / /2 of 5

, 2019

Algebra Difficulty 6.1 National olympiad Prove it Baltic Way

Find the smallest positive integer that cannot be written in the form (a2)+(b2)+c\binom{a}{2} + \binom{b}{2} + c with nonnegative integers a,b,ca, b, c satisfying abca \ge b \ge c and a+b2019a + b \le 2019.

Solution

The number is m=(19572)+(632)+1=1,915,900m = \binom{1957}{2} + \binom{63}{2} + 1 = 1,915,900.
Assume that mm has a representation as above. Then a1957a \le 1957 as (19582)>m\binom{1958}{2} > m. On the other hand, by (a2)+(b2)+c(a+12)+(b12)+(b1)\binom{a}{2} + \binom{b}{2} + c \le \binom{a+1}{2} + \binom{b-1}{2} + (b-1) it follows that the largest number that can be represented as above with a1957a \le 1957 is (19572)+(622)+62=m1\binom{1957}{2} + \binom{62}{2} + 62 = m - 1, a contradiction.

It remains to show that all natural numbers smaller than mm have a representation in the form (a2)+(b2)+c\binom{a}{2} + \binom{b}{2} + c with abca \ge b \ge c and a+b2019a+b \le 2019. If some number kk has such a representation and c>0c > 0 or c=0,b2c = 0, b \ge 2, then k1k-1 can be represented as (a2)+(b2)+(c1)\binom{a}{2} + \binom{b}{2} + (c-1) or (a2)+(b12)+(b2)\binom{a}{2} + \binom{b-1}{2} + (b-2), respectively. Hence, we can represent all integers between (a2)\binom{a}{2} and kk in the desired form. Therefore and because we have a representation for m1m-1 already, it suffices to show that the numbers s=(1957s2)1\ell_s = \binom{1957-s}{2} - 1 with s=0,1,,1954s = 0, 1, \dots, 1954 can be represented. Now the claim follows by 0=(19562)+(632)+2\ell_0 = \binom{1956}{2} + \binom{63}{2} + 2 and (1956s2)<s(1956s2)+(b2)\binom{1956-s}{2} < \ell_s \le \binom{1956-s}{2} + \binom{b}{2} with b=min{63,1956s}b = \min\{63, 1956-s\} for s=1,2,,1954s = 1, 2, \dots, 1954.

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.