Olympiad Maths Prep

Track / Stage 7 / 137 of 300 #1537 of 2000

Problem 1537

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.2 Prove it

Say that a positive integer is [i]sweet[/i] if it uses only the digits 0, 1, 2, 4, and 8. For instance, 2014 is sweet. There are sweet integers whose squares are sweet: some examples (not necessarily the smallest) are 1, 2, 11, 12, 20, 100, 202, and 210. There are sweet integers whose cubes are sweet: some examples (not necessarily the smallest) are 1, 2, 10, 20, 200, 202, 281, and 2424. Prove that there exists a sweet positive integer nn whose square and cube are both sweet, such that the sum of all the digits of nn is 2014.

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

1. Define the Polynomial:
Consider the polynomial P(x)=nN2xn P(x) = \sum_{n \in N} 2x^n , where N N is a set of 1007 positive integers. This polynomial is constructed such that each term represents a digit in the number n n .

2. Ensure Unique Sums:
We need to ensure that all sums of 1, 2, or 3 elements in N N are unique. This can be achieved by choosing N N to be the first 1007 powers of 9001. This choice ensures that the sums of any 1, 2, or 3 elements are distinct because the powers of 9001 grow exponentially.

3. Square of the Polynomial:
When we consider P(x)2 P(x)^2 , the terms are either 4x2n 4x^{2n} or 8xn1+n2 8x^{n_1+n_2} . This follows from the expansion using the multinomial theorem. Specifically:
P(x)2=(nN2xn)2=nN4x2n+n1,n2N,n1n28xn1+n2 P(x)^2 = \left( \sum_{n \in N} 2x^n \right)^2 = \sum_{n \in N} 4x^{2n} + \sum_{n_1, n_2 \in N, n_1 \neq n_2} 8x^{n_1+n_2}
Since the sums n1+n2 n_1 + n_2 are unique, the resulting polynomial will have terms with coefficients 4 or 8, which are sweet digits.

4. Cube of the Polynomial:
When we consider P(x)3 P(x)^3 , the terms are either 8x3n 8x^{3n} , 24x2n1+n2 24x^{2n_1+n_2} , or 48xn1+n2+n3 48x^{n_1+n_2+n_3} . This follows from the expansion using the multinomial theorem. Specifically:
P(x)3=(nN2xn)3=nN8x3n+n1,n2N,n1n224x2n1+n2+n1,n2,n3N,n1n2n348xn1+n2+n3 P(x)^3 = \left( \sum_{n \in N} 2x^n \right)^3 = \sum_{n \in N} 8x^{3n} + \sum_{n_1, n_2 \in N, n_1 \neq n_2} 24x^{2n_1+n_2} + \sum_{n_1, n_2, n_3 \in N, n_1 \neq n_2 \neq n_3} 48x^{n_1+n_2+n_3}
Again, since the sums 2n1+n2 2n_1 + n_2 and n1+n2+n3 n_1 + n_2 + n_3 are unique, the resulting polynomial will have terms with coefficients 8, 24, or 48, which are sweet digits.

5. **Choosing x x and Ensuring Sweetness:**
By setting x=100 x = 100 , we avoid overlapping of two-digit products. This ensures that the polynomial P(100) P(100) represents a number whose digits are sweet. The sum of the digits of n n is 2014, as required.

6. Conclusion:
Therefore, the number P(100) P(100) is a sweet number whose square and cube are also sweet.

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.