Olympiad Maths Prep

Track / Stage 6 / 142 of 400 #1142 of 2000

Problem 1142

National olympiad, first round
Number theory Difficulty 6.2 Prove it National Olympiad of Argentina · Argentina

Is there a number which is the sum of 23452345 positive integers that have the same digit sum, and also the sum of 56785678 positive integers that have the same digit sum? If the answer is *yes*, find the least such number. If not, explain why.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Such numbers exist. The least one is 1172511725.
Let NN be the sum of 23452345 positive integers with digit sum RR, and let Rr(mod9)R \equiv r \pmod{9}, r[1,9]r \in [1, 9]. Then N2345r5r(mod9)N \equiv 2345r \equiv 5r \pmod{9} as each summand is congruent to rr modulo 99. Similarly if NN is the sum of 56785678 numbers with digit sum congruent to ss modulo 99, s[1,9]s \in [1, 9], then N5678s8s(mod9)N \equiv 5678s \equiv 8s \pmod{9}. So 5rN8s(mod9)5r \equiv N \equiv 8s \pmod{9}. Letting rr run through 1,2,,91, 2, \ldots, 9 yields the admissible pairs of remainders: (1,4)(1, 4), (2,8)(2, 8), (3,3)(3, 3), (4,7)(4, 7), (5,2)(5, 2), (6,6)(6, 6), (7,1)(7, 1), (8,5)(8, 5), (9,9)(9, 9).

Note that Nmax(2345r,5678s)N \ge \max(2345r, 5678s) for every such pair (r,s)(r, s) because the least number with digit sum congruent to rr or ss modulo 99 is rr or ss respectively. If r=5r = 5, s=2s = 2 the last observation gives Nmax(23455,56782)=11725N \ge \max(2345 \cdot 5, 5678 \cdot 2) = 11725. For each remaining pair (r,s)(r, s) one of the numbers 2345r2345r and 5678s5678s is greater than 1172511725. It follows that the least NN in question, if it exists, is at least 1172511725.
On the other hand N=11725N = 11725 is possible. Indeed 11725=2345511725 = 2345 \cdot 5 is equal to the sum of 23452345 numbers equal to 55. Also 1172511725 is equal to the sum of 56785678 numbers with digit sum 22: 4141 summands 1111 and 56375637 summands 22 (4111+56372=1172541 \cdot 11 + 5637 \cdot 2 = 11725). In all there are 41+5637=567841 + 5637 = 5678 summands with digit sum 22, as needed.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.