Maths Olympiad Prep

Library / National Olympiad of Argentina /8 of 10

National Olympiad of Argentina

Number theory Difficulty 6.2 National Olympiad Prove it 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.

Solution

Such numbers exist. The least one is 1172511725.
Let NN be the sum of 23452345 positive integers with digit sum RR, and let R≡r(mod9)R \equiv r \pmod{9}, r∈[1,9]r \in [1, 9]. Then N≡2345r≡5r(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 N≡5678s≡8s(mod9)N \equiv 5678s \equiv 8s \pmod{9}. So 5r≡N≡8s(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 N≥max⁡(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 N≥max⁡(2345⋅5,5678⋅2)=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=2345⋅511725 = 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 (41⋅11+5637⋅2=1172541 \cdot 11 + 5637 \cdot 2 = 11725). In all there are 41+5637=567841 + 5637 = 5678 summands with digit sum 22, as needed.

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.