Juego de rana en un gráfico de diente de león

Dec 01 2020

Hay algo de ruido en el estanque local. ¡Un grupo de ranas quiere organizar una fiesta de cumpleaños!

Hay un total de 22 nenúfares en el estanque, cada uno con una sola rana. Están etiquetados con números del 0 al 21. Para facilitarles la vida, cada rana construyó un puente hacia cada uno de sus vecinos. La rana 0 es la rana más popular y tiene ranas del 1 al 7 como vecinas, mientras que las ranas del 8 al 21 solo tienen a la rana anterior como vecina.

La novena rana quiere celebrar su cumpleaños. ¿Puedes guiar a todas las demás ranas a su nenúfar?

Puede instruir a todas las n ranas en un nenúfar A no vacío para que salten a otro nenúfar B no vacío si y solo si existe un camino entre A y B que consta exactamente de n puentes únicos.

Esto se ilustra en la imagen a continuación.




En otras palabras, las reglas del juego de la rana se dan formalmente como:

El juego de la rana

  • El juego se juega en un gráfico cuyos vértices representan "nenúfares" (nenúfares).

  • Al comienzo del juego, coloque una rana en cada nenúfar.

  • El objetivo del juego es mover todas las ranas a una única hoja de nenúfar.

  • Puede mover exactamente todas las n ranas contenidas en la hoja de nenúfar A a alguna otra hoja de nenúfar B si y solo si ambas hojas de nenúfar no están vacías (contienen al menos una rana) y existe un camino de A a B que consta de exactamente n bordes únicos .

Entonces, el rompecabezas de la imagen se da formalmente como:

El objetivo del rompecabezas es resolver el juego de la rana en el noveno vértice del gráfico dado (ver la imagen de arriba). El gráfico consta de un vértice raíz etiquetado como vértice 0, al que conectamos 6 vértices de hojas etiquetados como {1, 2, 3, 4, 5, 6} y un gráfico de ruta de 15 vértices cuyos vértices están etiquetados como {7, 8 , 9, ..., 21}.

Es posible que desee imprimir el gráfico y usar fichas para representar ranas. Si no, no debería ser un problema usar un bolígrafo y un papel (que es como lo resolví eventualmente).



PD: Para calentar, ¿puedes ver que el juego de la rana se puede resolver en cualquier vértice de un gráfico de ruta ?

Esto es porque:

Coloque un gráfico de trayectoria P n con n vértices en una recta numérica. Si comienzas en el vértice central y alternas saltos de izquierda y derecha (o viceversa, dependiendo de la paridad de n), puedes ver que un camino se puede resolver fácilmente en los vértices de las hojas (vértices de grado 1).

Ahora, para resolver un gráfico de trayectoria P n en un vértice arbitrario v, simplemente divídelo en dos subgrafos de trayectoria que compartan el vértice v como una hoja (y no compartan ningún otro vértice), y resuelve cada subgráfico usando la estrategia del vértice de la hoja.



Este rompecabezas se inspiró en mi generalización de un rompecabezas de Numberphile , desde una línea hasta gráficos. La gráfica dada en este acertijo es especial porque es el contraejemplo más pequeño de una de mis viejas conjeturas sobre las "gráficas de diente de león" .

Para crear la imagen del rompecabezas (del gráfico dado), utilicé el editor de gráficos de csacademy .

¡PS Mathpickle tiene más rompecabezas como este! Ver:

  • https://mathpickle.com/project/lazy-toad-puzzles-counting-symmetry/

  • https://mathpickle.com/project/lazy-toads-on-a-star/

Respuestas

5 DanielMathias Dec 01 2020 at 09:18

¿Solución única?

Grupo A:

Mueve 5 ranas a 0 desde los pétalos del 1 al 5.
Mueve 6 ranas del 0 al 12 = 7 ranas en 12.
Mueve 7 ranas de 12 a 19 = 8 ranas en 19.
Mueve 1 rana de 20 a 21 = 2 ranas en 21.
Mueve 2 ranas de 21 a 19 = 10 ranas en 19.
Mueve 10 ranas de 19 a 9 = 11 ranas en 9.

Grupo B:

Mueve 1 rana de 13 a 14 = 2 ranas en 14.
Mueve 1 rana de 15 a 16 = 2 ranas en 16.
Mueve 2 ranas de 16 a 14 = 4 ranas en 14.
Mueve 4 ranas de 14 a 10 = 5 ranas en 10.
Mueve 5 ranas de 10 a 6 = 6 ranas en 6.
Mueve 6 ranas de 6 a 11 = 7 ranas en 11.
Mueve 7 ranas de 11 a 18 = 8 ranas en 18.
Mueve 1 rana de 17 a 18 = 9 ranas en 18.
Mueva 9 ranas de 18 a 9 = 20 ranas en 9.

Y finalmente:

Mueve 1 rana de 8 a 7 = 2 ranas en 7.
Mueve 2 ranas de 7 a 9 = ¡¡FIESTA EN 9 !!

4 JeremyDover Dec 01 2020 at 05:19

Puede haber otras soluciones, pero:

Paso 1:

Reúna todos los pétalos en 0, a través de 1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 6 → 0

Paso 2:

Haz lo único que puedas con las 7 ranas en 0: saltarlas a 13; luego salta las 8 ranas hasta 21. Ahora tienes 9 ranas en 21: 0, 1, 2, 3, 4, 5, 6, 13, 21.

Paso 3:

El único salto que estas 9 ranas pueden hacer directamente es al 12, pero ahí te quedarás atascado. De hecho, queremos llevarlos directamente a 9. ¡Por lo tanto, necesitamos 3 ranas más! Lo mejor que puede hacer es obtenerlos de los nenúfares adyacentes, 18, 19 y 20, a través de 19 → 20, (19) (20) → 18, (18) (19) (20) → 21. Ahora tenemos 12 ranas en 21 y podemos saltarlas todas a 9.

Paso 4:

Teóricamente hemos terminado, ya que el OP muestra cómo obtener todas las ranas en una ruta hacia uno de sus puntos finales, por lo que podemos 7-8 a 9 y 10-17 a 9, pero para ser explícitos: 8 → 7, 78 → 9; y 13 → 14, (13) (14) → 12, (12) (13) (14) → 15, (12) (13) (14) (15) → 11, (11) (12) (13) (14) (15) → 16, (11) (12) (13) (14) (15) (16) → 10, (10) (11) (12) (13) (14) (15) (16 ) → 17, y (10) (11) (12) (13) (14) (15) (16) (17) → 9.

Respuesta incorrecta original: Dios mío, ¿soy tonto?

Aquí hay una solución, puede haber otras:

Lo primero que debe notar es que solo puede usar 0 una vez, por lo que debe tener cuidado de centralizar algunos de los pétalos (1-6) primero y luego moverlos todos fuera de 0. Pero, ¿cuántos centralizar? Lo primero que obviamente debe intentar es todo: mueva todos los 1-6 pétalos a 0, luego salte 7 ranas a 13. Pero esto se desvanece rápidamente: salta 8 ranas a 21, luego 9 ranas a 12, y está atascado .

Pero no tienes que tomar todos los pétalos a la vez, porque puedes saltar algunas ranas a un pétalo y luego volverlas al 9. Así que intentemos llevar todos los pétalos excepto uno al 0, dando el serie: 1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 012345 → 12, 012345 (12) → 19. Necesitamos dos ranas adicionales para volver a 19, que podemos agarrar a través de 20 → 21 y (20) (21) → 19, y todo el lío 012345 (12) (19) (20) (21) vuelve a 9 .

Próximos pasos:

En este punto, tienes una masa de ranas en 9 y ranas individuales en 6, 7, 8, 10, 11 y 13-18. Primero despejemos el lado de los pétalos. Necesitamos tres ranas en 6 para saltar de nuevo a 9, que podemos obtener con 8 → 7, 78 → 6 y 678 → 9. Ahora 10 y 11 llegan a 9 con 10 → 11, (10) (11) → 9. Finalmente, tenemos seis ranas en una fila entre 13 y 18 que se pueden agrupar en 15 por el resultado del gráfico de ruta dado (explícitamente: 14 → 13, (13) (14) → 15, 17 → 16, (16) (17) → 18, (16) (17) (18) → 15), y finalmente esta masa salta a 9, terminando el rompecabezas.