Jogo sapo em um gráfico de dente de leão
Há algum ruído na lagoa local. Um grupo de sapos quer dar uma festa de aniversário!
Há um total de 22 nenúfares no tanque, cada um abrigando um único sapo. Eles são rotulados como números de 0 a 21. Para facilitar suas vidas, cada sapo construiu uma ponte para cada um de seus vizinhos. A rã 0 é a mais popular e tem rãs de 1 a 7 como vizinhas, enquanto que as rãs de 8 a 21 têm apenas a rã precedente como vizinha.
O nono sapo quer comemorar seu aniversário. Você pode guiar todos os outros sapos para seu lírio?
Você pode instruir todos os n sapos em um nenúfar não vazio A para pular para algum outro nenúfar não vazio B se e somente se houver um caminho entre A e B que consiste em exatamente n pontes exclusivas.
Isso é ilustrado na imagem abaixo.

Em outras palavras, as regras do jogo do sapo são formalmente dadas como:
O jogo sapo
O jogo é jogado em um gráfico cujos vértices representam "nenúfares" (nenúfares).
No início do jogo, coloque um sapo em cada nenúfar.
O objetivo do jogo é mover todos os sapos para um único nenúfar.
Você pode mover exatamente todos os n sapos contidos no nenúfar A para algum outro nenúfar B se e somente se ambos os nenúfares não estiverem vazios (contenham pelo menos um sapo) e houver um caminho de A para B consistindo em exatamente n bordas exclusivas .
Então, o quebra-cabeça na imagem é formalmente dado como:
O objetivo do quebra-cabeça é resolver o jogo do sapo no 9º vértice do gráfico fornecido (veja a imagem acima). O gráfico consiste em um vértice raiz rotulado como 0º vértice, ao qual conectamos 6 vértices folha rotulados como {1, 2, 3, 4, 5, 6} e um gráfico de caminho de 15 vértices cujos vértices são rotulados como {7, 8 , 9, ..., 21}.
Você pode imprimir o gráfico e usar tokens para representar sapos. Do contrário, não deve ser um problema usar uma caneta e um papel (que foi como acabei resolvendo).
PS Para aquecer, você pode ver que o jogo do sapo pode ser resolvido em qualquer vértice de um gráfico de caminho ?
Isto é porque:
Coloque um gráfico de caminho P n com n vértices em uma reta numérica. Se você começar no vértice central e alternar os saltos para a esquerda e para a direita (ou vice-versa, dependendo da paridade de n), poderá ver que um caminho pode ser facilmente resolvido nos vértices da folha (vértices de grau 1).
Agora, para resolver um grafo de caminho P n em um vértice v arbitrário, simplesmente divida-o em dois subgráficos de caminho que compartilham o vértice v como uma folha (e não compartilham nenhum outro vértice) e resolva cada subgrafo usando a estratégia do vértice da folha.
Este quebra-cabeça foi inspirado por minha generalização de um quebra-cabeça Numberphile , de uma linha para gráficos. O gráfico dado neste quebra-cabeça é especial porque é o menor contra-exemplo a uma de minhas antigas conjecturas sobre "gráficos de dente-de-leão" .
Para criar a imagem do quebra-cabeça (do gráfico fornecido), usei o editor de gráficos de csacademy .
PS Mathpickle tem mais quebra-cabeças como este! Ver:
https://mathpickle.com/project/lazy-toad-puzzles-counting-symmetry/
https://mathpickle.com/project/lazy-toads-on-a-star/
Respostas
Solução única?
Grupo A:
Mova 5 sapos para 0 das pétalas 1 a 5.
Mova 6 sapos de 0 a 12 = 7 sapos em 12.
Mova 7 sapos de 12 para 19 = 8 sapos em 19.
Mova 1 sapo de 20 para 21 = 2 sapos em 21.
Mova 2 sapos de 21 para 19 = 10 sapos em 19.
Mova 10 sapos de 19 para 9 = 11 sapos em 9.
Grupo B:
Mova 1 sapo de 13 para 14 = 2 sapos em 14.
Mova 1 sapo de 15 para 16 = 2 sapos em 16.
Mova 2 sapos de 16 para 14 = 4 sapos em 14.
Mova 4 sapos de 14 para 10 = 5 sapos em 10.
Mova 5 sapos de 10 para 6 = 6 sapos em 6.
Mova 6 sapos de 6 para 11 = 7 sapos em 11.
Mova 7 sapos de 11 para 18 = 8 sapos em 18.
Mova 1 sapo de 17 para 18 = 9 sapos em 18.
Mova 9 sapos de 18 para 9 = 20 sapos em 9.
E finalmente:
Mova 1 sapo de 8 para 7 = 2 sapos em 7.
Mova 2 sapos de 7 para 9 = FESTA EM 9 !!
Pode haver outras soluções, mas:
Passo 1:
Reúna todas as pétalas em 0, via 1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 6 → 0
Passo 2:
Faça a única coisa que você pode com os 7 sapos no 0: pule-os para 13; em seguida, pule os 8 sapos para 21. Você agora tem 9 sapos em 21: 0, 1, 2, 3, 4, 5, 6, 13, 21.
Etapa 3:
O único salto que esses 9 sapos podem dar diretamente é para 12, mas aí você ficará preso. Na verdade, queremos levá-los diretamente para 9. Portanto, precisamos de mais 3 sapos! A melhor coisa a fazer é obtê-los dos nenúfares adjacentes, 18, 19 e 20, via 19 → 20, (19) (20) → 18, (18) (19) (20) → 21. Agora temos 12 sapos no 21 e podemos pular todos para 9.
Passo 4:
Teoricamente terminamos, já que o OP mostra como colocar todos os sapos em um caminho para um de seus pontos finais, então podemos 7-8 a 9 e 10-17 a 9, mas para ser explícito: 8 → 7, 78 → 9; e 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 e (10) (11) (12) (13) (14) (15) (16) (17) → 9.
Resposta incorreta original - Caramba, sou burro.
Aqui está uma solução, pode haver outras:
A primeira coisa a notar é que você só pode usar 0 uma vez, então você precisa ter o cuidado de centralizar algumas das pétalas (1-6) primeiro e, em seguida, mover todas para fora de 0. Mas quantas para centralizar? A primeira coisa óbvia a tentar é tudo: mova todas as 1-6 pétalas para 0, depois pule 7 sapos para 13. Mas isso rapidamente se esgota: você pula 8 sapos para 21, então 9 sapos para 12, e você está preso .
Mas você não tem que pegar todas as pétalas de uma vez, porque você pode pular alguns sapos para uma pétala e depois pular de volta para o 9. Então, vamos tentar tirar todas as pétalas, exceto uma para o 0, dando o série: 1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 012345 → 12, 012345 (12) → 19. Precisamos de dois sapos extras para voltar a 19, que podemos pegar via 20 → 21 e (20) (21) → 19, e toda a bagunça 012345 (12) (19) (20) (21) volta a 9 .
Próximos passos:
Neste ponto, você tem uma massa de sapos em 9 e rãs individuais em 6, 7, 8, 10, 11 e 13-18. Vamos limpar primeiro o lado da pétala. Precisamos de três sapos em 6 para voltar ao 9, que podemos obter com 8 → 7, 78 → 6 e 678 → 9. Agora, 10 e 11 chegam a 9 com 10 → 11, (10) (11) → 9. Finalmente, temos seis sapos em uma linha entre 13 e 18 que podem ser concentrados em 15 pelo resultado do gráfico de caminho dado (explicitamente: 14 → 13, (13) (14) → 15, 17 → 16, (16) (17) → 18, (16) (17) (18) → 15) e, finalmente, essa massa salta para 9, terminando o quebra-cabeça.