33rd BMO 1997 Problem 3 Find the number of polynomials of degree 5 with distinct coefficients from the set {1, 2, ... , 9} which are divisible by x 2 - x + 1. Solution
: 624. This seems to be a laborious exercise in counting. Suppose that the polynomial is (x 2 - x + 1)(ax 3 + bx 2 + cx + d). Multiplying out, we find that the coefficients are: a, b-a, c-(b-a), b-(c-d), c-d, d. Put e = b-a, f = c- d. Then the coefficients are: a, e, d+f-e, a+e-f, f, d. Put k = e-f. Then the coefficients are: a, f+k, d-k, a+k, f, d. Suppose k > 0. Put g = d-k. then the coefficients are (rearranging the order) a, f, g, a+k, f+k, g+k. Similarly, if k < 0, put h = -k, and the coefficients are a, e, d+h, a-h, e+h, d. Putting g = a-h and rearranging the order we get: d, e, g, d+h, e+h, g+h. The two types (k positive and negative) obviously do not overlap and there are evidently equal numbers of each. So we have to find the number of sets a, f, g, a+k, f+k, g+k. By symmetry, the number of sets must be 6 times the number with a < f < g. However, I cannot see an elegant way to count the number with a < f < g. Simply listing them gives 52 possibilities. if k = 1, a = 1, f = 3, then g can be 5, 6, 7, or 8. if k = 1, a = 1, f = 4, then g can be 6, 7 or 8 if k = 1, a = 1, f = 5, then g can be 7 or 8 if k = 1, a = 1, f = 6, then g must be 8 if k = 1, a = 2, f = 4, then g can be 6, 7 or 8 if k = 1, a = 2, f = 5, then g can be 7 or 8 if k = 1, a = 2, f = 6, then g must be 8 if k = 1, a = 3, f = 5, then g can be 7 or 8 if k = 1, a = 3, f = 6, then g must be 8 if k = 2, a = 1, f = 2, then g can be 5, 6 or 7 if k = 2, a = 1, f = 4, then g can be 5 or 7 if k = 2, a = 1, f = 5, then g must be 6 if k = 2, a = 1, f = 6, then g must be 7 if k = 2, a = 2, f = 3, then g can be 6 or 7 if k = 2, a = 2, f = 5, then g must be 6 if k = 2, a = 2, f = 6, then g must be 7 if k = 2, a = 3, f = 4, then g must be 7 if k = 2, a = 3, f = 6, then g must be 7 if k = 3, a = 1, f = 2, then g can be 3 or 6if k = 3, a = 1, f = 3, then g must be 5 if k = 3, a = 1, f = 5, then g must be 6 if k = 3, a = 2, f = 3, then g must be 4 if k = 3, a = 2, f = 4, then g must be 6 if k = 3, a = 3, f = 4, then g must be 5 if k = 3, a = 4, f = 5, then g must be 6 if k = 4, a = 1, f = 2, then g can be 3 or 4 if k = 4, a = 1, f = 3, then g must be 4 if k = 4, a = 2, f = 3, then g can be 4 or 5 if k = 4, a = 2, f = 4, then g must be 5 if k = 5, a = 1, f = 2, then g must be 3 or 4 if k = 5, a = 1, f = 3, then g must be 4 if k = 5, a = 2, f = 3, then g must be 4 if k = 6, a = 1, f = 2, then g must be 3 Comment: can anyone come up with a better solution! 33rd BMO 1997 © John Scholes jscholes@kalva.demon.co.uk 14 Aug 2002