Permainan katak pada grafik dandelion
Ada kebisingan di kolam lokal. Sekelompok katak ingin mengadakan pesta ulang tahun!
Ada total 22 bantalan teratai di kolam, masing-masing menampung satu katak. Mereka diberi label sebagai angka dari 0 hingga 21. Untuk mempermudah hidup mereka, setiap katak membangun satu jembatan untuk setiap tetangganya. Katak 0 adalah katak paling populer dan memiliki katak dari 1 hingga 7 sebagai tetangganya, sedangkan katak dari 8 hingga 21 hanya memiliki katak sebelumnya sebagai tetangganya.
Katak ke-9 ingin merayakan ulang tahunnya. Bisakah Anda memandu semua katak lain ke bunga bakung?
Anda dapat menginstruksikan semua n katak pada bantalan teratai A yang tidak kosong untuk melompat ke bantalan teratai B yang tidak kosong jika dan hanya jika terdapat jalur antara A dan B yang terdiri dari n jembatan unik.
Ini diilustrasikan pada gambar di bawah.
Dengan kata lain, aturan permainan katak secara resmi diberikan sebagai:
Permainan katak
Permainan ini dimainkan pada grafik yang simpulnya mewakili "bantalan bunga lili" (Bunga lili air).
Di awal permainan, letakkan satu katak di setiap daun teratai.
Tujuan permainan ini adalah untuk memindahkan semua katak ke satu bantalan teratai.
Anda dapat memindahkan persis semua n katak yang ada di lily pad A ke lily pad B lainnya jika dan hanya jika kedua bantalan lily tidak kosong (berisi setidaknya satu katak) dan terdapat jalur dari A ke B yang terdiri dari tepat n tepi unik .
Kemudian, teka-teki dalam gambar tersebut secara resmi diberikan sebagai:
Tujuan dari teka-teki ini adalah untuk menyelesaikan permainan katak pada simpul ke - 9 dari grafik yang diberikan (lihat gambar di atas). Grafik ini terdiri dari simpul akar yang diberi label sebagai simpul ke-0, di mana kita menghubungkan 6 simpul daun yang diberi label sebagai {1, 2, 3, 4, 5, 6} dan satu graf jalur dari 15 simpul yang simpul-simpulnya diberi label sebagai {7, 8 , 9, ..., 21}.
Anda mungkin ingin mencetak grafik dan menggunakan token untuk mewakili katak. Jika tidak, seharusnya tidak menjadi masalah untuk menggunakan pena dan kertas (begitulah cara saya menyelesaikannya pada akhirnya).
PS Untuk pemanasan, dapatkah Anda melihat bahwa permainan katak dapat diselesaikan pada simpul manapun dari grafik jalur ?
Hal ini karena:
Tempatkan grafik jalur P n dengan n simpul pada garis bilangan. Jika Anda memulai di puncak tengah dan melakukan lompatan ke kiri dan kanan secara bergantian (atau sebaliknya, bergantung pada paritas n), Anda dapat melihat bahwa jalur mudah dipecahkan di simpul daun (simpul berderajat 1).
Sekarang, untuk menyelesaikan graf jalur P n dalam simpul v sembarang, cukup bagi menjadi dua subgraf jalur yang berbagi simpul v sebagai daun (dan tidak berbagi simpul lain), dan selesaikan setiap subgraf menggunakan strategi simpul daun.
Teka-teki ini terinspirasi oleh generalisasi saya tentang teka-teki Numberphile , dari garis ke grafik. Grafik yang diberikan dalam teka-teki ini istimewa karena ini adalah contoh tandingan terkecil dari salah satu dugaan lama saya tentang "grafik dandelion" .
Untuk membuat gambar teka-teki (dari grafik yang diberikan), saya menggunakan editor grafik csacademy .
PS Mathpickle punya lebih banyak teka-teki seperti ini! Lihat:
https://mathpickle.com/project/lazy-toad-puzzles-counting-symmetry/
https://mathpickle.com/project/lazy-toads-on-a-star/
Jawaban
Solusi unik?
Grup A:
Pindahkan 5 katak ke 0 dari kelopak 1 sampai 5.
Pindahkan 6 katak dari 0 ke 12 = 7 katak di 12.
Pindahkan 7 katak dari 12 menjadi 19 = 8 katak di 19.
Pindahkan 1 katak dari 20 ke 21 = 2 katak di 21.
Pindahkan 2 katak dari 21 menjadi 19 = 10 katak pada 19.
Pindahkan 10 katak dari 19 menjadi 9 = 11 katak pada 9.
Grup B:
Pindahkan 1 katak dari 13 ke 14 = 2 katak di 14.
Pindahkan 1 katak dari 15 ke 16 = 2 katak di 16.
Pindahkan 2 katak dari 16 ke 14 = 4 katak di 14.
Pindahkan 4 katak dari 14 ke 10 = 5 katak di atas 10.
Pindahkan 5 katak dari 10 menjadi 6 = 6 katak pada 6.
Pindahkan 6 katak dari 6 menjadi 11 = 7 katak pada 11.
Pindahkan 7 katak dari 11 menjadi 18 = 8 katak pada 18.
Pindahkan 1 katak dari 17 menjadi 18 = 9 katak di 18.
Pindahkan 9 katak dari 18 menjadi 9 = 20 katak di 9.
Dan akhirnya:
Pindahkan 1 katak dari 8 menjadi 7 = 2 katak di 7.
Pindahkan 2 katak dari 7 menjadi 9 = PARTY ON 9 !!
Mungkin ada solusi lain, tetapi:
Langkah 1:
Kumpulkan semua kelopak ke 0, melalui 1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 6 → 0
Langkah 2:
Lakukan satu-satunya hal yang Anda bisa dengan 7 katak di 0: lompat mereka ke 13; lalu lompat 8 katak di sana menjadi 21. Anda sekarang memiliki 9 katak di 21: 0, 1, 2, 3, 4, 5, 6, 13, 21.
Langkah 3:
Satu-satunya lompatan yang bisa dilakukan 9 katak ini secara langsung adalah ke 12, tetapi di sana Anda akan terjebak. Faktanya, kami ingin membuat mereka langsung ke 9. Jadi kami membutuhkan 3 katak lagi! Hal terbaik untuk dilakukan adalah mendapatkannya dari bantalan lily yang berdekatan, 18, 19 dan 20, melalui 19 → 20, (19) (20) → 18, (18) (19) (20) → 21. Kami sekarang memiliki 12 katak di 21, dan dapat melompati semuanya menjadi 9.
Langkah 4:
Secara teoritis kita sudah selesai, karena OP menunjukkan bagaimana mendapatkan semua katak di jalur ke salah satu titik ujungnya, jadi kita bisa 7-8 ke 9 dan 10-17 ke 9, tetapi untuk lebih eksplisit: 8 → 7, 78 → 9; dan 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, dan (10) (11) (12) (13) (14) (15) (16) (17) → 9.
Jawaban Salah Asli - Ya ampun, apakah saya bodoh.
Ini satu solusinya, mungkin ada yang lain:
Hal pertama yang harus diperhatikan adalah Anda hanya dapat menggunakan 0 sekali, jadi Anda harus berhati-hati untuk memusatkan beberapa kelopak (1-6) terlebih dahulu, lalu memindahkan semuanya 0. Tetapi berapa banyak yang harus dipusatkan? Hal pertama yang harus dicoba adalah: pindahkan semua 1-6 kelopak ke 0, lalu lompat 7 katak ke 13. Tapi ini dengan cepat hilang: Anda melompati 8 katak menjadi 21, lalu 9 katak menjadi 12, dan Anda terjebak .
Tetapi Anda tidak harus mengambil semua kelopak sekaligus, karena Anda bisa melompati beberapa katak ke kelopak, lalu melompati mereka kembali ke 9. Jadi mari kita coba mengambil semua kelopak kecuali satu ke 0, memberikan seri: 1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 012345 → 12, 012345 (12) → 19. Kita membutuhkan dua katak ekstra untuk kembali ke 19, yang bisa kita ambil melalui 20 → 21 dan (20) (21) → 19, dan seluruh kekacauan 012345 (12) (19) (20) (21) kembali ke 9 .
Langkah selanjutnya:
Pada titik ini Anda memiliki massa katak pada 9, dan katak tunggal pada 6, 7, 8, 10, 11, dan 13-18. Mari bersihkan sisi kelopaknya terlebih dahulu. Kita membutuhkan tiga katak di 6 untuk melompat kembali ke 9, yang bisa kita dapatkan dengan 8 → 7, 78 → 6 dan 678 → 9. Sekarang 10 dan 11 sampai ke 9 dengan 10 → 11, (10) (11) → 9. Akhirnya kita memiliki enam katak dalam satu baris antara 13 dan 18 yang dapat dikumpulkan pada 15 oleh hasil grafik jalur yang diberikan (secara eksplisit: 14 → 13, (13) (14) → 15, 17 → 16, (16) (17) → 18, (16) (17) (18) → 15), dan akhirnya massa ini melompat ke 9, menyelesaikan puzzle.