BMO2 1997 - Combinatoria

Question

Encuentra el número de polinomios de grado 5 con distinto coeficientes del conjunto {1, 2, 3, 4, 5, 6, 7, 8} que son divisibles por $x^2-x+1$ .

Intenté multiplicar $x^2-x+1$ por $ax^3+bx^2+cx+d$ para conseguir $ax^5+(b-a)x^4+(a-b+c)x^3+(b-c+d)x^2+(c-d)x+d$ pero me cuesta contar desde aquí.

Answer 1

Es divisible por $x^2-x+1$ si y sólo si desaparece en $\zeta=e^{\pi i/3}$ . Ahora $$a\zeta^5+b\zeta^4+c\zeta^3+d\zeta^2+e\zeta+f=(d-a)\zeta^2+(e-b)\zeta+f-c$$ por lo que debemos tener $d-a=b-e=f-c$ . Así que sólo hay que contar las soluciones de ese sistema con las variables que toman valores distintos de $1,\dots,8$ .

Answer 2

Completando los detalles de la respuesta de @Gerry Myerson:

WLOG asume $d>a$ y $d < b < f$ . Contaremos el número de pares y multiplicaremos por $3! \cdot 2 = 12$ para explicar la simetría. Hacer un trabajo de caso sobre el valor de $d-a$ .

Si $d-a = 1$ entonces hay $10$ valores posibles para $(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) $$

Si $d-a = 2$ entonces hay $6$ valores posibles para $(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) $$

Si $d-a = 3$ entonces hay $4$ valores posibles para $(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) $$

Si $d-a = 4$ entonces hay $4$ valores posibles para $(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) $$

Si $d-a = 5$ hay un valor posible para $(a,d,e,b,c,f)$ :

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

Esto da $25$ total de tuplas. Así que hay $12 \cdot 25 = 300$ diferentes posibilidades.

---

Confirmación de que la respuesta es $300$ utilizando un programa de Python:

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()

Funciona mediante la configuración de los valores de $a, b-a, c-d, d$ del conjunto $\{ 1, \cdots, 8\}$ y luego ver si los valores correspondientes de $a-b+c = (c-d) + d - (b-a)$ y $b-c+d = (b-a) + a - (c-d)$ son distintos y se encuentran en el conjunto $\{ 1, \cdots 8\}$ .

Answer 3

Esto no es técnicamente una respuesta matemática pero no puedo poner más de una línea de código en un comentario.

Quería mostrar una forma diferente de verificar la solución en un ordenador "hasta el final" del enunciado del problema, en lugar de sólo la parte de contar como en la respuesta de @aras. Para ello se utiliza 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))