Membalik koin dalam lingkaran

Question

Kami memiliki satu set koin N yang semuanya ditempatkan dalam lingkaran. Mereka semua memiliki "Ekor" sebagai sisi wajah mereka. Koin-koin itu semuanya berbeda dan memiliki angka (1,2,3 ... N) yang tertulis di atasnya.

Dalam setiap gerakan, kami membalik 3 koin berturut-turut. Artinya, pertimbangkan:

HHHTT

Jika saya memutuskan untuk membalik koin 3,4 dan 5 maka saya akan mendapatkan: HHTHH

Sekarang, mungkin ada 2 ^ N permutasi kepala-ekor yang berbeda dari N koin yang berbeda.

1. Buktikan / sangkal bahwa ada serangkaian gerakan terbatas di mana kita dapat mencapai salah satu dari permutasi kepala-ekor (2 ^ N) dari koin-koin N ini, dari permutasi semua ekor awal.

2. Juga, jika mencapai permutasi apa pun memang memungkinkan, lalu berapa jumlah gerakan maksimum yang diperlukan untuk mencapai permutasi apa pun dari permutasi semua ekor awal.

Untuk klarifikasi lebih lanjut, jika N adalah 3, misalnya, maka 2 ^ 3 permutasi berbeda dari 3 koin ini adalah:

TTT

TTH

THT

THH

HHH

HHT

HTH

HTT

Answer 1

Mari kita asumsikan $N \geq 3$atau masalahnya tidak didefinisikan dengan baik.

Bagian 1:

Posisi akhir koin hanya bergantung pada berapa kali koin tersebut dibalik (jumlah flips genap, itu adalah T; angka ganjil, H).

Jadi, gerakan (terdiri dari tiga membalik) bersifat komutatif. Juga, gerakan jelas merupakan gerakan terbalik, jadi tidak ada gunanya melakukan gerakan yang sama dua kali. Jadi, kita perlu memperhatikan diri kita sendiri hanya dengan set posisi bergerak (tidak berurutan) (yang juga ada$2^N$).

Jika tidak semua posisi dapat dicapai, maka dua gerakan yang berbeda harus memberikan hasil yang sama. Tapi itu berarti perbedaan simetris (XOR) antara set langkah ini harus memberikan konfigurasi dengan semua T. Jadi kita dapat menanyakan apakah ada beberapa set langkah tidak kosong yang menghasilkan semua T.

Untuk set langkah apa pun, setiap koin akan dibalik antara 0 dan 3 kali. Juga, jumlah membalik untuk koin yang berdekatan harus berbeda hanya dengan 0 atau 1. (Hanya ada satu gerakan yang membalik$x$ dan tidak $x + 1$dan sebaliknya.) Jadi, untuk mendapatkan semua T, jumlah flips harus semuanya 0 atau semua 2. Semua 0 hanya mungkin dengan set langkah kosong. Bagaimana dengan semua 2?

Jumlah total membalik harus kelipatan 3 karena setiap gerakan membalik tiga koin. Jadi, tidak mungkin mendapatkan semua 2 kecuali$N$ adalah kelipatan dari 3. Jika $N$adalah kelipatan 3 itu mudah. Setiap koin dapat dibalik dengan bergerak di setiap posisi ketiga. Kemudian kita dapat melakukan hal yang sama lagi tetapi digeser 1 untuk membaliknya.

Jadi, setiap posisi akhir bisa dicapai jika dan hanya jika$N$tidak habis dibagi 3.

Bagian 2:

Jika setiap posisi dapat dicapai, maka setiap set gerakan mencapai posisi yang berbeda. Secara khusus, himpunan semua posisi gerakan mencapai posisi akhir tertentu di$N$bergerak, dan tidak ada posisi lain yang membutuhkan lebih dari itu banyak gerakan. Posisi khusus ini sebenarnya adalah semua H karena akan membalik setiap koin 3 kali.

Untuk menghitung dengan cepat set gerakan untuk posisi akhir tertentu, saya sarankan terlebih dahulu menghitung set gerakan yang hanya membalik koin 1. Kemudian kita tahu cara melempar koin apa pun dengan menggeser set langkah ini. Dan kemudian kita dapat menghitung hasil apa pun dengan menggabungkan set pemindahan koin tunggal (dengan perbedaan simetris / XOR).

Answer 2

Pendekatan yang lebih sedikit "matematis":

Jelas bahwa masalah untuk mencapai konfigurasi sewenang-wenang setara dengan serangkaian gerakan yang membalik tepat satu koin.

Sekarang bagaimana menemukannya:

Anda dapat dengan mudah membuat urutan flip yang diperlukan menggunakan urutan 1,2,4,5,7, ... (angka sesuai dengan koin awal, 1 berarti membalik koin 1,2,3). Ini akan membalik koin 2 (N = 3k + 1) atau N (N = 3k + 2). Konstruksinya jelas, mulailah dengan koin 1 yang Anda atur sebagai kepala dengan gerakan pertama, terus balikkan sisanya sehingga hanya ada 1-2 kepala yang menyebar ke "ujung" lingkaran. Setelah kepala tersebut (hampir) bertemu dengan yang pertama, lakukan flip terakhir. Dengan N = 3k + 1 Anda mendapatkan satu kepala di ujung dan akhirnya membalik hanya koin 2, dengan N = 3k + 2 Anda mendapatkan satu kepala 1 sebelum akhir dan membalik hanya koin N. Dengan N = 3k Anda mendapatkan 2 koin di akhir dan mencapai semua ekor. Karena Anda tidak dapat "memeras" koin-koin itu untuk ditinggalkan dengan satu "kepala", tidak mungkin untuk mencapai semua konfigurasi.

Sekarang kasus terburuk:

Untuk mendapatkan semua kepala, Anda memerlukan semua koin untuk dibalik 1 atau 3 kali. Anda jelas tidak bisa membuat semua koin dibalik 1 kali dengan N = 3k + 1 atau 2. Jika koin X dibalik 3 kali, koin X + 1 sudah dibalik 2 kali dan perlu dibalik sekali lagi dll, membuktikan Anda perlu membalik semua koin 3 kali untuk mendapatkan semua kepala dari awal semua ekor.