Harker Math Invitational 2024 Team #15
March 9, 2024
Problem 15 from Harker Math Invitational 2024 Team Round
Consider all polynomials \(P\) with each coefficient equal to 0, 1, or 2. How many of these satisfy \(P(2)=2042\)?
Let \(F(n,m)\) be the number of polynomials \(P\) up to degree \(n\) with each coefficient equal to 0, 1, or 2 and satisfying \(P(2)=m\). Note that any remainder of \(P(x)\) divided by \(x^k\) for \(k\) from \(1\) to \(n\) is nonnegative for \(x \ge 0\). Since \(2^{11} = 2048 > 2042\), we just need to compute \(F(10, 2042) = F(10, 2^{11}-6)\).
Let \(a_n = F(n, 2^{n+1} - 6)\). We do the following case analysis:
Case 1: \(P(x) = x^n + Q(x)\) where \(Q(x)\) is a polynomial up to degree \(n-1\) with each coefficient equal to 0, 1, or 2 and satisfying \(Q(2)=2^{n} - 6\).
Case 2: \(P(x) = Q(x)\) where \(Q(x)\) is a polynomial up to degree \(n-1\) with each coefficient equal to 0, 1, or 2 and satisfying \(Q(2)=2^{n+1} - 6\).
Hence \(F(n, 2^{n+1} - 6) = F(n-1, 2^{n} - 6) + F(n-1, 2^{n+1} - 6)\) or \(a_{n} = a_{n-1} + F(n-1, 2^{n+1} - 6)\)
Now we consider the \(F(n-1, 2^{n+1} - 6)\) from the second case. Note that in this case, the largest possible value of Q(2) can be achieved when all coefficients are 2, i.e. \(max(Q(2)) = 2(2^{n-1} + \ldots + 2 + 1) = 2(2^n-1) = 2^{n+1} - 2\). When the highest degree of the polynomial is at least 2, there are only three possibilities to make \(Q(2) = 2^{n+1} - 6\), namely, subtracting \(x^2\), \(2x\), or \(x+2\) from the polynomial with all coefficients being 2. Therefore \(F(n-1, 2^{n+1} - 6) = 3\) for \(n > 2\). Hence \[a_{10} = a_{9} + 3 = a_{8} + 2 \times 3 = \cdots = a_{2} + 8\times3.\]
Finally we have \(a_{2} = F(2, 2^3-6) = F(2, 2)\). There are only two such polynomials, \(f(x)=x\) and \(g(x)=2\). Therefore the total number of such polynomials is \(a_{10} = F(10, 2042) = 2 + 24 = \boxed{26}\).
Source: https://artofproblemsolving.com/community/u423290h3273807p30129116 (by mathophobia)
Note that when 2042 is written in binary, it is 111111111010, doing casework on the last four numbers, we have the coefficients for x^(3,2,1,0) are (0,2),1,2,2 1,0,1,0 1,0,0,2 (0,2),2,1,0 and (0,2),2,0,2 for each of the two cases that end in one, the remaining coefficients must be one (until x^11) and for each of the three cases which end in in (0,2), you can have a coefficient of sequence of 1….102… for where the 0 can be located in x^(3,4,5,6,7,8,9,10) powers (not 11 because then the coefficient of 2 in x^10 would mean P(2)>2042) so there are 8 cases. 2+3*8 = 26.
Note that if the polynomials coefficients were only 0, 1, we are essentially asking for the number of ways to write 2042 in binary, so in that case our final answer is just 1. Consider 2042 in binary: 11111111010. Note that each valid “almost-binary” representation could be mapped to the binary representation of 2042 by converting the consecutive digits 02 to 10, or other similar variants. Thus, to count the number of ways to obtain an “almost-binary” representation, we work backwards and see how many ways there are to convert consecutive 10s to 02s or 20s to 12s. Now we count this by splitting into 2 cases: if the last digit is equal to 2 and if the last digit is equal to 0.
If the last digit is equal to 0, it isn’t hard to see that the second to last digit must remain a 1. From here, note that we could simply choose where the ”0” is amongst the first 9 digits, and then ”bubble” it upwards. Thus, we have 9 choices for this subcase. If last digit is equal to 2, the last 1 is ”canceled”, and thus we are doing the same thing as before, but with 1111111100. We have one choice if we leave this binary representation as is. Otherwise, now we have 2 choices, either change the last 100 into 012 or 020. Either case leaves 0 as the 3rd to last digit, and afterwards we could simply choose where the 0 is amongst the first 8 digits (The ”0” ”bubbles” upwards). So we have a total of 1 + 2 · 8 = 1 + 16 = 17 for this subcase.
In total, we have \(17 + 9 = \boxed{26}\) “almost-binary” representations of 2042.