3 votos

Polinomios en el problema de Pancake

Me he dado cuenta de algo interesante en este tabla. Las columnas se pueden expresar mediante polinomios de grado k. Tomo la primera $k+1$ números de cada columna y utilicé la interpolación de Lagrange. Sorprendentemente, he conseguido que esta extrapolación dé los valores exactos de todos los demás números de la columna. No puedo comprobar esto para $k=7$ . $$k=0: 1$$ $$k=1: n-1$$ $$k=2: n^2-3n+2$$ $$k=3: n^3-5n^2+8n-5$$ $$k=4: n^4-\frac{15}2n^3+\frac{29}2n^2+3n-17$$ $$k=5: n^5-\frac{65}6n^4+\frac{173}6n^3+\frac{148}3n^2-\frac{862}3n+265$$ $$k=6: n^6-\frac{883}{60}n^5+\frac{157}3n^4+\frac{2155}{12}n^3-\frac{4570}3n^2+\frac{42767}{15}n-967$$ $$k=7: \frac{1679}{1680}n^7-\frac{2765}{144}n^6+\frac{21541}{240}n^5+\frac{69163}{144}n^4-\frac{717821}{120}n^3+\frac{1462277}{72}n^2-\frac{10388033}{420}n+5037$$

Si pongo el $n$ a uno en el que se produce el primer valor positivo, lo es: $$k=0: 1$$ $$k=1: n$$ $$k=2: n^2+n$$ $$k=3: n^3+n^2-1$$ $$k=4: n^4+\frac92n^3+n^2-\frac92n+1$$ $$k=5: n^5+\frac{55}6n^4+\frac{31}2n^3-\frac{14}3n^2-2n+1$$ $$k=6: n^6+\frac{917}{60}n^5+\frac{713}{12}n^4+\frac{565}{12}n^3-\frac{5}{12}n^2+\frac{409}{30}n-3$$ $$k=7: \frac{1679}{1680}n^7+\frac{142}{9}n^6+\frac{192}{5}n^5-\frac{3743}{36}n^4-\frac{18917}{240}n^3+\frac{14119}{36}n^2-\frac{50761}{140}n+100$$

Preguntas:

¿Se puede demostrar que las columnas de esa tabla son siempre polinomios?

¿Se pueden predecir los coeficientes de alguna manera? Parece que hay un orden pero no lo encuentro.

1voto

Vincent Puntos 635

Esta es una respuesta muy muy parcial, que sólo trata los casos k = 0, 1, 2, 3. Pero espero que sirva de inspiración para seguir trabajando en los casos restantes.

Piensa en los números como puntos a distancia $k$ a partir de un punto base fijo en el gráfico del panqueque. Pensamos en el punto base como la pila de panqueques que está completamente ordenada de la manera deseada. Los vértices (pilas) que son alcanzables en $k$ pasos desde este punto (pero no en menos pasos) son exactamente las pilas que necesitan $k$ pasos para llegar al punto base, que es lo que cuenta la tabla. (Por supuesto, desde el punto de vista del gráfico de panqueques, la elección del punto base no es importante, ya que el grupo $S_n$ actúa transitivamente sobre los vértices del grafo por isomorfismos del grafo).

Las tres primeras columnas son fáciles. Por supuesto, sólo hay un punto a distancia 0 del punto base: el propio punto base. Además, como todos los vértices del grafo del panqueque tienen grado $(n-1)$ (hay en cada momento $n-1$ posibles giros a realizar) está claro que cada punto tiene $n-1$ vecinos. Esta es la $k=1$ columna.

Del mismo modo: cada uno de estos $n-1$ vecinos tiene $n-2$ vecinos del punto base, por lo que el número de puntos a distancia $k = 2$ debe ser $(n-1)(n-2)$ . Ampliando los paréntesis recuperamos su resultado: $n^2 - 3n + 2$ .

Por desgracia, esta estrategia se rompe para $k = 3$ . Los gráficos de panqueques contienen muchos hexágonos (incrustaciones isomórficas del gráfico de 3 panqueques), lo que significa que si tomamos la predicción ingenua de $(n-1)(n-2)(n-2)$ contamos algunos, y quizás muchos, puntos dos veces o incluso más a menudo hay múltiples hexágonos que contienen tanto el punto base como el punto de interés. Por lo tanto, la respuesta será seguramente menor que $(n-1)(n-2)(n-2)$ Pero, ¿en qué medida?

Bueno, primero vamos a reescribir este límite superior crudo en la forma que se utiliza, por lo que sin paréntesis. Obtenemos $n^3 - 5 n^2 + 8 n - 4$ . Esto es muy interesante, ¡es sólo 1 más de lo que se encuentra! Esto significa que de los $n^3 - 5 n^2 + 8 n - 4$ ¡puntos a distancia 3 sólo hay uno que se cuenta doble!

Sabiendo esto no es difícil ver cuál es: ya mencionamos el subgrupo de las 3 tortas. Consiste en movimientos que sólo mueven los 3 panqueques superiores. Aparentemente:

Cualquier conjunto de k=3 movimientos empezando por la pila completamente ordenada que mueve un panqueque de tamaño 4 o superior, alcanza un estado que no puede ser alcanzado en 3 pasos de ninguna otra manera.

En lugar de escribir "aparentemente" también podríamos simplemente publicar esto como un lema, probarlo y derivar la fórmula para el $k = 3$ caso de ella.

Ahora la prueba de este lema no es tan difícil porque 3 es un número realmente muy pequeño. La verdadera pregunta es:

cuál es la generalización adecuada de este lema a otros valores de $k$ ?

Lo pensaré y volveré sobre ello más tarde.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X