BMO2 1997 - Combinatorics

Solution 1:

It's divisible by $x^2-x+1$ if and only if it vanishes at $\zeta=e^{\pi i/3}$. Now $$a\zeta^5+b\zeta^4+c\zeta^3+d\zeta^2+e\zeta+f=(d-a)\zeta^2+(e-b)\zeta+f-c$$ so we must have $d-a=b-e=f-c$. So you just have to count solutions of that system with the variables taking on distinct values from $1,\dots,8$.

Solution 2:

Filling in the details for @Gerry Myerson's answer:

WLOG assume $d>a$ and $d < b < f$. We will count the number of pairs, and multiply by $3! \cdot 2 = 12$ to account for the symmetry. Do casework on the value of $d-a$.

If $d-a = 1$, then there are $10$ possible values for $(a,d,e,b,c,f)$:

$$(1,2,3,4,5,6), (1,2,3,4,6,7),(1,2,3,4,7,8),(1,2,4,5,6,7),(1,2,4,5,7,8)\\ (1,2,5,6,7,8),(2,3,4,5,6,7),(2,3,4,5,7,8),(2,3,5,6,7,8),(3,4,5,6,7,8) $$

If $d-a = 2$, then there are $6$ possible values for $(a,d,e,b,c,f)$:

$$ (1,3,2,4,5,7),(1,3,2,4,6,8),(1,3,4,6,5,7),(1,3,5,7,6,8),(2,4,3,5,6,8),(2,4,5,7,6,8) $$

If $d-a = 3$, then there are $4$ possible values for $(a,d,e,b,c,f)$:

$$ (1,4,2,5,3,6), (1,4,3,6,5,8), (2,5,3,6,4,7), (3,6,4,7,5,8) $$

If $d-a = 4$, then there are $4$ possible values for $(a,d,e,b,c,f)$:

$$ (1,5,2,6,3,7), (1,5,2,6,4,8), (1,5,3,7,4,8), (2,6,3,7,4,8) $$

If $d-a = 5$, there is one possible value for $(a,d,e,b,c,f)$:

$$ (1,6,2,7,3,8)$$

This gives $25$ total tuples. So there are $12 \cdot 25 = 300$ different possibilities.

Confirmation that the answer is $300$ using a Python program:

import itertools

def main():
  good = []
  for l in itertools.permutations(range(1,9),4):
    a = l[0]
    b_a = l[1]#b-a
    c_d = l[2]#c-d
    d = l[3]
    ambpc = c_d + d - b_a#a-b+c
    bmcpd = b_a + a - c_d#b-c+d
    if ambpc > 0 and ambpc < 9 and bmcpd > 0 and bmcpd < 9:
      if ambpc != bmcpd:
        if ambpc not in l and bmcpd not in l:
          good.append([a,b_a,ambpc,bmcpd,c_d,d])
  print(good)
  print(len(good))


if __name__=="__main__":
  main()

It works by settings the values for $a, b-a, c-d, d$ from the set $\{ 1, \cdots, 8\}$, and then seeing if the corresponding values of $a-b+c = (c-d) + d - (b-a)$ and $b-c+d = (b-a) + a - (c-d)$ are distinct and lie in the set $\{ 1, \cdots 8\}$.

Solution 3:

This is not technically a mathematical answer but I can't put more than one line of code in a comment.

I wanted to show a different way to verify the solution on a computer "all the way" up to the statement of the problem, instead of only the counting part like in @aras's answer. This uses Sagemath:

from itertools import permutations

deg = 5
max_coeff = 8

# declare polynomial ring
R.<x> = PolynomialRing(QQ, 'x')

# generate valid combinations of coefficients 
# and create the polynomials that have them as coefficients 
polys = (R(perm) for perm in permutations(range(1,max_coeff+1), deg+1))

# count valid polynomials
print sum(1 for p in polys if (x^2-x+1).divides(p))