민들레 그래프에 개구리 게임
지역 연못에 약간의 소음이 있습니다. 한 무리의 개구리가 생일 파티를 열고 싶어합니다!
연못에는 총 22 개의 수련이 있으며, 각각 한 마리의 개구리가 있습니다. 그들은 0에서 21까지의 숫자로 표시되어 있습니다. 삶을 편하게하기 위해 각 개구리는 각각의 이웃에게 하나의 다리를 만들었습니다. 개구리 0은 가장 인기있는 개구리이며 1에서 7까지의 개구리를 이웃으로 가지고 있으며 8에서 21까지의 개구리는 앞의 개구리 만 이웃으로 가지고 있습니다.
아홉 번째 개구리는 생일을 축하하고 싶어합니다. 다른 모든 개구리를 릴리 패드로 안내 할 수 있습니까?
비어 있지 않은 릴리 패드 A에있는 모든 n 개 개구리에게 A와 B 사이에 정확히 n 개의 고유 한 브리지로 구성된 경로가있는 경우에만 비어 있지 않은 다른 릴리 패드 B로 점프하도록 지시 할 수 있습니다.
이것은 아래 이미지에 설명되어 있습니다.
즉, 개구리 게임 의 규칙 은 공식적으로 다음과 같이 주어집니다.
개구리 게임
이 게임은 정점이 "백합 패드"(수련)를 나타내는 그래프로 진행됩니다.
게임을 시작할 때 각 릴리 패드에 개구리를 하나씩 놓습니다.
게임의 목표는 모든 개구리를 주어진 하나의 릴리 패드로 이동하는 것입니다.
두 릴리 패드가 비어 있지 않고 (적어도 하나의 개구리 포함) A에서 B까지의 경로가 정확히 n 개의 고유 한 모서리로 구성된 경우에만 릴리 패드 A에 포함 된 n 개의 개구리를 다른 릴리 패드 B로 정확하게 이동할 수 있습니다. .
그런 다음 이미지의 퍼즐은 공식적으로 다음과 같이 주어집니다.
퍼즐의 목표는 주어진 그래프 의 9 번째 꼭지점 에서 개구리 게임 을 푸는 것 입니다 (위 이미지 참조). 그래프는 0 번째 정점으로 레이블이 지정된 루트 정점으로 구성되며, 여기에 {1, 2, 3, 4, 5, 6}로 레이블이 지정된 6 개의 리프 정점과 정점이 {7, 8로 레이블이 지정된 15 개의 정점 으로 구성된 경로 그래프 1 개가 연결 됩니다. , 9, ..., 21}.
그래프를 인쇄하고 토큰을 사용하여 개구리를 나타낼 수 있습니다. 그렇지 않다면 펜과 종이를 사용하는 것이 문제가되지 않을 것입니다 (결국 제가 해결 한 방법입니다).
PS 워밍업을 위해 경로 그래프 의 모든 정점에서 개구리 게임을 풀 수 있음을 알 수 있습니까?
이 때문입니다:
n 개의 꼭지점이 있는 경로 그래프 P n 을 수직선에 배치합니다. 중앙 정점에서 시작하고 왼쪽 및 오른쪽 점프를 번갈아 가며 (또는 그 반대, n의 패리티에 따라) 리프 정점 (차수 1의 정점)에서 경로를 쉽게 해결할 수 있음을 알 수 있습니다.
이제 임의의 정점 v에서 경로 그래프 P n 을 풀 려면 정점 v를 리프로 공유하고 다른 정점을 공유하지 않는 두 개의 경로 하위 그래프로 나누고 리프 정점 전략을 사용하여 각 하위 그래프를 풀면됩니다.
이 퍼즐은 선에서 그래프까지 Numberphile 퍼즐의 일반화에서 영감을 받았습니다 . 이 퍼즐에 주어진 그래프는 "민들레 그래프"에 대한 나의 오래된 추측 중 하나에 대한 가장 작은 반례이기 때문에 특별합니다 .
주어진 그래프의 퍼즐 이미지를 만들기 위해 csacademy의 그래프 편집기를 사용했습니다 .
PS Mathpickle에는 이와 같은 퍼즐이 더 많이 있습니다! 보다:
https://mathpickle.com/project/lazy-toad-puzzles-counting-symmetry/
https://mathpickle.com/project/lazy-toads-on-a-star/
답변
독특한 솔루션?
그룹 A :
꽃잎 1에서 5까지 5 개 개구리를 0으로 이동합니다. 0에서
12 개 = 12 개에 7 개 개구리를
이동 합니다. 12 개에서 19 개에 7 개 개구리 = 19 개에 8 개 개구리를
이동합니다. 21 개에 1 개 개구리를 20 개에서 21 개 = 2 개로 이동합니다.
19 개에 개구리 2 개를 21 개에서 19 개 = 10 개로
이동합니다. 9 개에 개구리 10 개를 19 개에서 9 개 = 11 개로 이동합니다.
그룹 B :
개구리 1 개를 13에서 14 개로
이동 = 14 개에 개구리 2 개. 15 개에서 16 개 = 16 개에 2 개 개구리를
이동합니다 . 16 개에 2 개 개구리를 16 개에서 14 개 = 14 개에 4 개
이동 합니다. 14 개에서 10 개로 4 개 개구리를 이동 합니다. 10.
개구리 5 개를 10에서 6으로
이동 = 6 개에 6 개 개구리를 6 개에서 11 개 = 7 개에 11 개로 이동 11 개에서 18 개로 7
개 = 18 개에 8 개 개구리를
이동 합니다. 17 개에서 18 개 = 9 개로 1 개 개구리 이동 18
개에 개구리. 18 개에서 9 개로 9 개 개구리 이동 = 9 개에 20 개 개구리.
그리고 마지막으로:
개구리 1 개를 8 개에서 7 개로
이동 = 2 개는 7 개로 이동합니다. 2 개 개구리를 7 개에서 9 개로 이동 = PARTY ON 9 !!
다른 해결책이있을 수 있지만 :
1 단계:
1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 6 → 0을 통해 모든 꽃잎을 0으로 모으십시오.
2 단계:
0에서 7 개의 개구리로 할 수있는 유일한 일을하십시오 : 13으로 점프하십시오. 그런 다음 8 개 개구리를 21 개로 점프합니다. 이제 21에 9 개 개구리가 있습니다 : 0, 1, 2, 3, 4, 5, 6, 13, 21.
3 단계 :
이 9 개 개구리가 직접 점프 할 수있는 유일한 점프는 12 개이지만 거기에 갇히게됩니다. 사실, 우리는 그것들을 9로 직접 가져 가고 싶습니다. 따라서 우리는 3 개의 개구리가 더 필요합니다! 가장 좋은 방법은 인접한 릴리 패드 18, 19 및 20에서 19 → 20, (19) (20) → 18, (18) (19) (20) → 21을 통해 가져 오는 것입니다. 이제 21 개에 12 개의 개구리가 있으며 모두 9 개로 점프 할 수 있습니다.
4 단계 :
이론적으로 우리는 OP가 끝점 중 하나에 대한 경로에서 모든 개구리를 얻는 방법을 보여주기 때문에 7-8에서 9 및 10-17에서 9까지 가능하지만 명확하게 : 8 → 7, 78 → 9; 및 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 및 (10) (11) (12) (13) (14) (15) (16) (17) → 9.
원래 오답 -오, 내가 바보 야.
다음은 하나의 솔루션이며 다른 솔루션이있을 수 있습니다.
가장 먼저 주목해야 할 점은 0을 한 번만 사용할 수 있다는 것입니다. 따라서 먼저 꽃잎 (1-6) 중 일부를 중앙 집중화 한 다음 모두 0에서 제거하도록주의해야합니다. 그러나 중앙 집중화 할 수는 몇 개입니까? 가장 먼저 시도해야 할 것은 모든 것입니다. 1 ~ 6 개의 꽃잎을 모두 0으로 이동 한 다음 7 개를 13 개로 이동합니다. 그러나 이것은 빠르게 지저분합니다. 8 개를 21 개로, 9 개를 12 개로 이동하면 갇혀 있습니다. .
하지만 당신은하지 않습니다 이 그럼, 0을 제외한 꽃잎을 모두 복용 제공 해보자는 꽃잎에 약간의 개구리 점프 할 수 있기 때문에, 한 번에 꽃잎을 모두 취할 다음 다시 9로 이동 시리즈 : 1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 012345 → 12, 012345 (12) → 19. 19로 돌아가려면 두 개의 추가 개구리가 필요합니다. 20 → 21 및 (20) (21) → 19를 통해 잡을 수 있으며 전체 012345 (12) (19) (20) (21)은 9로 돌아갑니다. .
다음 단계:
이 시점에서 당신은 9에 개구리 덩어리가 있고 6, 7, 8, 10, 11, 13-18에 단일 개구리가 있습니다. 먼저 꽃잎 쪽을 치우 자. 우리는 8 → 7, 78 → 6, 678 → 9로 구할 수 있습니다. 이제 10과 11은 10 → 11, (10) (11) → 9로 9가됩니다. 마지막으로 주어진 경로 그래프 결과 (명시 적으로 : 14 → 13, (13) (14) → 15, 17 → 16, (16) (17) → 18, (16) (17) (18) → 15) 그리고 마지막으로이 질량이 9로 점프하여 퍼즐을 완성합니다.