Apilamiento de Fichas de Póquer

Estoy estudiando combinatoria, y estoy luchando con la búsqueda de relaciones de recurrencia de los problemas. Por ejemplo, "Encontrar una relación de recurrencia para el número de maneras de apilar n fichas de póquer si cada ficha de póquer es roja, blanca o azul. Las fichas azules pueden ser adyacente, pero ningunas fichas rojas pueden ser adyacentes y ningunas fichas blancas pueden ser adyacentes". La respuesta es:

pero no entiendo cómo conseguir eso. ¿Existe algún tipo de estrategia general?

¿Quiere una sugerencia? Haga clic aquí.

Haga clic aquí para ver la respuesta completa.

Sugerencia 1

Estrategia General: Si existe una relación de recurrencia para contar algo, entonces es probable que exista una estructura recursiva de las cosas que se cuentan, es decir, cada elemento está compuesto de forma recursiva de objetos similares mas pequeños.

Sugerencia 2

Es verdad que existe una estructura recursiva aquí, pero es difícil verla, debido a las condiciones de adyacencia. Una idea: hacer que el problema llega a ser más difícil: contar las pilas de acuerdo al color de la ficha superior. Así que busque fórmulas para:

• r(n), el número de pilas de n fichas con ficha roja en la parte superior
• w(n), el número de pilas de n fichas con ficha blanca en la parte superior
• b(n), el número de pilas de n fichas con ficha azul en la parte superior

Sugerencia 3

Consideramos las pilas con ficha roja en la parte superior. Si hay una ficha roja en la parte superior, entonces la ficha debajo de ella será de color blanco o azul, y también cualquier pila con n-1 fichas con blanco o azul en la parte superior puede añadir una ficha roja encima para crear una pila de n fichas. Eso demuestra que

Ahora, encontrar fórmulas para los demás colores. Por último, pensar en cómo utilizar estas fórmulas para conseguir una fórmula para a(n).

El Resto de la Respuesta

Las fórmulas para el rojo, blanco y azul son

• r(n) = w(n-1) + b(n-1)
• w(n) = r(n-1) + b(n-1)
• b(n) = r(n-1) + w(n-1) + b(n-1)

Tenga en cuenta que las fichas azules son especiales, porque no hay limitaciones en las pilas con el azul en la parte superior. Para obtener una fórmula para a(n) una idea obvia es añadir estas tres fórmulas:

Ahora observamos que b(n) = r(n-1) + w(n-1) + b(n-1) = a(n-1) y por tanto b(n-1) = a(n-2) que nos da la fórmula completa

Menos es Más

Frecuentemente, cuando se quiere obtener algún resultado, hay una generalización o un mejor resultado que es más fácil de conseguir. Pólya llama esta idea "Inventor's Paradox" (paradoja del inventor): "The more ambitious plan may have more chances of success." (El plan más ambicioso puede tener más posibilidades de éxito.) En este problema consideraron el problema "más difícil" de contar cada tipo de pila de acuerdo a la ficha superior. Algunos otros ejemplos de la paradoja del inventor:

• La suma de los primeros n cubos es un cuadrado.
  [Demostrar que es el cuadrado (n(n+1)/2)^2.]
• Si m es un número entero, y a es un número entero primo relativo a m, entonces existe inverso multiplicativo módulo m (es decir, hay un x tal que ax=1 mod m).
  [Demostrar que ax asume todos los valores primos relativos a m cuando varía x en todos los valores primos relativos con m, en particular, el valor 1.]
• (Último Teorema de Fermat para exponente 4) Demostrar que no hay números enteros positivos x, y, z tal que x^4 + y^4 = z^4.
  [Demostrar que no hay soluciones a x^4 + y^4 = z^2.]

Referencias

• George Pólya, Cómo Plantear y Resolver Problemas, Editorial Trillas, México, D.F., 1965. La paradoja del inventor se discute en p.138, y la suma de los primeros n cubos es un ejemplo en pp. 114-116.
• (en inglés) G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th edition, Oxford University Press, 2008. La teorema de la inversa multiplicativa es Theorem 57 en p. 62, y la Teorema Última de Fermat para exponente 4 es Theorem 226 en pp. 247-248.
• (en inglés) Haga clic aquí para ver la pregunta original de Thermos.