Kami rangkaian teka-teki terbaru menampilkan skala keseimbangan double-pan yang sederhana, yang secara historis merupakan simbol perdagangan dan pemerintahan, seni dan sains. Timbangan keseimbangan juga populer dalam matematika rekreasi. Teka-teki keseimbangan membutuhkan penalaran logis yang jelas dan cocok untuk generalisasi matematika. Mari kita lihat caranya Quanta pembaca menyeimbangkan kualitas ini dalam teka-teki di bawah ini.
Teka-teki 1
Anda memiliki delapan koin yang tampak identik. Salah satunya palsu dan lebih ringan dari yang lain, yang memiliki bobot identik. Temukan koin jelek dalam dua penimbangan. Temukan rumus umum untuk jumlah maksimum koin yang dapat digunakan untuk menemukan koin palsu x timbangan.
Menangani versi sederhana dari suatu masalah sering kali mengungkapkan kunci pemecahannya. Dalam hal ini, bayangkan Anda hanya memiliki tiga koin, dengan satu lebih ringan dari dua lainnya. Jika Anda menimbang salah satu dari mereka terhadap salah satu dari dua lainnya, mereka akan seimbang atau tidak. Jika tidak, Anda tahu mana yang lebih ringan. Jika mereka melakukan keseimbangan, maka yang ketiga adalah yang ringan. Anda hanya perlu satu penimbangan.
Jadi dalam teka-teki ini, jika Anda dapat mengisolasi sekelompok tiga (atau lebih sedikit) yang berisi koin ringan pada penimbangan pertama, Anda hanya perlu satu penimbangan lagi. Anda dapat melakukan ini dengan menyeimbangkan ketiganya dengan tiga lainnya. Jika kedua grup tidak seimbang, Anda telah menemukan grup yang berisi yang ringan dan dapat melanjutkan seperti di atas untuk penimbangan kedua. Jika mereka seimbang, cukup timbang dua koin yang tersisa satu sama lain, dan Anda akan menemukan yang ringan.
Perhatikan bahwa ini juga berfungsi jika ada tiga di grup yang tidak tertimbang, jadi kita bisa mulai dengan sembilan koin. Mengikuti logika ini, dan dimulai dengan tiga koin, untuk setiap penimbangan tambahan, kita dapat menemukan koin ringan dalam tiga kali jumlah koin yang kita miliki sebelumnya. Rumusnya memberi kami jumlah koin maksimum n in w penimbangan oleh karena itu n = 3w.
Teka-teki 2
Anda memiliki 12 koin yang tampak identik. Yang satu lebih berat atau lebih ringan dari yang lain, yang memiliki bobot identik.
-
Temukan koin jelek dalam tiga penimbangan.
-
Berapa jumlah maksimum koin yang dapat Anda temukan yang buruk dalam empat penimbangan? Jelaskan bagaimana Anda akan menemukan koin palsu.
Solusi untuk teka-teki ini dijelaskan dengan baik oleh Ted, yang juga menunjukkan bahwa Anda benar-benar dapat mendeteksi koin buruk di antara 13 koin dalam tiga penimbangan. Inilah solusi Ted (dengan lekukan untuk memisahkan tiga penimbangan dalam setiap kasus):
Mulailah dengan menimbang 4 koin vs 4 koin.
Kasus 1: Jika tidak seimbang, untuk penimbangan kedua letakkan 2 masing-masing sisi yang lebih berat di kedua sisi timbangan bersama dengan 1 masing-masing sisi yang lebih ringan.
1a: Jika tidak seimbang, koin yang buruk adalah 2 koin yang masih berada di sisi yang berat atau satu koin yang masih berada di sisi yang ringan.
Timbang 2 koin berat yang mungkin, yang buruk adalah yang lebih berat dari keduanya, atau yang ringan tunggal jika seimbang.
1b: Jika penimbangan kedua seimbang, koin yang buruk adalah salah satu dari 2 yang tidak terpakai dari sisi yang lebih ringan dari penimbangan pertama.
Timbang mereka satu sama lain, yang lebih ringan itu buruk.
Kasus 2: Jika seimbang, koin buruk adalah salah satu dari 5 koin yang tersisa. Timbang 3 dari mereka terhadap 3 yang sudah ditimbang (yang diketahui baik).
Kasus 2a: Jika tidak seimbang, Anda tahu koin yang buruk adalah salah satu dari 3 itu dan apakah itu ringan atau berat.
Penimbangan ketiga adalah 2 dari yang berlawanan satu sama lain — jika tidak seimbang, yang mengidentifikasi koin buruk, jika seimbang itu yang terakhir dari ketiganya.
Kasus 2b: Jika penimbangan kedua seimbang, koin yang buruk adalah salah satu dari sisa 2.
Timbang salah satu dari mereka terhadap koin yang dikenal baik. Jika hasil ini tidak seimbang, koin baru ini buruk dan Anda tahu apakah itu berat atau ringan. Jika hasil ini seimbang, koin ke-13 buruk, tetapi tidak diketahui apakah itu berat atau ringan (yang tidak perlu kita ketahui, jadi kita selesai).
Ted juga menunjukkan bahwa jumlah maksimum koin untuk empat penimbangan adalah 40. Rumus untuk teka-teki ini adalah: n = (3w 1)/2.
Untuk teka-teki yang tersisa, rumus umum masih dalam penyelidikan oleh ahli matematika profesional dan merupakan subjek dari makalah yang diterbitkan, beberapa di antaranya telah dikutip oleh Rainer aus dem Musim Semi. Saya akan membatasi diri pada solusi untuk sejumlah kecil koin yang kami pertimbangkan dalam teka-teki dan hanya akan menyebutkan generalisasi yang mengikuti secara alami dari metode yang digunakan dalam kasus ini.
Teka-teki 3
Ini adalah variasi dari teka-teki 1. Anda kembali memiliki delapan koin yang tampak identik, salah satunya lebih ringan dari yang lain. Namun, sekarang Anda memiliki tiga skala. Dua timbangan berfungsi, tetapi timbangan ketiga rusak dan memberikan hasil acak (terkadang benar dan terkadang salah). Anda tidak tahu skala mana yang rusak. Berapa penimbangan yang diperlukan untuk menemukan koin ringan?
Seperti yang kita lihat di masalah 1, ini hanya membutuhkan dua penimbangan dengan keseimbangan yang baik. Kita juga tahu bahwa dua timbangan yang baik akan selalu cocok, jadi jika kita mengulangi setiap penimbangan pada ketiga timbangan, kita akan mendapatkan jawaban dalam enam penimbangan seperti yang disarankan oleh pembaca. Jika kita mencoba melakukannya dalam jumlah penimbangan yang lebih sedikit, itu akan menjadi sedikit rumit. Kita tidak dapat mengidentifikasi skala yang baik hanya dengan menimbang koin yang sama pada dua skala, karena meskipun mereka setuju, salah satu dari keduanya mungkin masih merupakan skala yang buruk. (Ini juga menunjukkan betapa mudahnya informasi yang salah atau informasi acak dapat mengaburkan kebenaran.)
Faktanya, masalah ini dapat diselesaikan dengan sangat cerdik, hanya dalam empat penimbangan! Rainer aus dem Musim Semi memposting solusinya menggunakan notasi bermodel baru yang tampaknya telah dibuat untuk teka-teki ini. Tetapi sebelum Anda pergi ke sana, saya ingin Anda membayangkan skenario yang saya harap akan membuat segalanya lebih intuitif.
Bayangkan Anda seorang detektif yang menyelidiki tabrak lari di sebuah negara kecil yang mobilnya memiliki pelat nomor dua digit hanya dengan menggunakan angka 0, 1 dan 2. Tiga orang, A, B dan C, telah mengamati insiden tersebut. Dua dari mereka selalu menjawab pertanyaan tiga pilihan dengan benar, dan satu memberikan jawaban yang benar-benar acak. Anda tidak tahu siapa penjawab acak itu. Anda harus menanyakan masing-masing dari mereka satu pertanyaan tiga pilihan dan kemudian memilih satu yang pasti mengatakan yang sebenarnya untuk mendapatkan lebih banyak informasi.
Inilah cara Anda melakukannya. Tanyakan A apakah angka pertama adalah 0, 1 atau 2. Katakanlah A mengatakan 2. Tanyakan B apakah angka kedua adalah 0, 1 atau 2. Katakanlah B mengatakan 1. Kemudian minta C untuk membuat pilihan di antara ketiga pernyataan ini:
- Hanya A yang mengatakan yang sebenarnya.
- Hanya B yang mengatakan yang sebenarnya.
- Keduanya mengatakan yang sebenarnya.
Anda dapat memercayai angka yang diperintahkan C dan menanyai orang itu tentang angka lainnya. Untuk mengetahui alasannya, pertimbangkan bahwa jika A berbohong, maka C dapat diandalkan dan akan mengatakan bahwa B mengatakan yang sebenarnya. Digit kedua sebenarnya adalah 1 dan Anda kemudian dapat mempertanyakan B tentang digit pertama. Demikian pula, jika B berbohong, maka C dapat diandalkan lagi dan akan mengatakan bahwa A mengatakan yang sebenarnya. Maka digit pertama sebenarnya adalah 2 dan Anda dapat menanyakan A tentang digit kedua. Akhirnya, jika C berbohong, maka A dan B dapat diandalkan, jadi Anda masih bisa percaya dan memilih siapa pun yang dikatakan C. (Dan jika C mengatakan A dan B mengatakan yang sebenarnya, maka keduanya pasti benar.) Kuncinya di sini adalah bahwa pilihan pertanyaan Anda tidak memungkinkan C berbohong sedemikian rupa sehingga menimbulkan keraguan pada A dan B. Karena setidaknya satu dari A dan B harus dapat diandalkan, Anda selalu dapat memilih salah satu yang disetujui oleh C, meskipun itu hanya jawaban acak. Jika ketiganya setuju, maka Anda sudah memiliki kedua digit plat nomor.
Inilah cara menerjemahkan kisah ini kembali ke teka-teki kita. Skalanya adalah A, B dan C. Anda dapat menerjemahkan dua digit plat nomor ke koin sebagai berikut: 01 adalah koin 1, 02 adalah koin 2, 10 adalah koin 3, 11 adalah koin 4, 12 adalah koin 5, 20 adalah koin 6, 21 adalah koin 7 dan 22 adalah koin 8. Pembaca yang cerdik akan mengenali bahwa ini adalah sistem bilangan basis 3 (atau ternary). Perhatikan juga bahwa ada kemungkinan tambahan angka 00, yang dapat Anda gunakan untuk koin kesembilan yang juga dapat digunakan teknik ini, seperti pada teka-teki 1.
Untuk penimbangan pertama, Anda membagi koin dengan digit pertama (basis 3), sehingga tiga kelompok Anda adalah koin [1, 2], [3, 4, 5] dan [6, 7, 8]. Timbang [3, 4, 5] terhadap [6, 7, 8] pada skala A. Jika A bekerja dengan baik, Anda akan memiliki kelompok digit pertama yang benar seperti pada teka-teki 1. Demikian pula, untuk penimbangan kedua pada skala B kelompok Anda akan menjadi mereka dengan digit kedua yang sama: [1, 4, 7], [2, 5, 8] dan [3, 6]. Jika B bekerja dengan baik, Anda akan memiliki digit kedua yang benar. Untuk penimbangan ketiga, pada skala C, Anda menimbang kelompok yang diidentifikasi A terhadap kelompok yang dilakukan B. Mengikuti contoh kita, untuk 21, grupnya adalah [6, 7, 8] dan [1, 4, 7]. Koin 7 tidak dapat diletakkan di kedua sisi secara bersamaan, jadi kami meninggalkannya dan menimbang [6, 8] dan [1, 4] satu sama lain. Perhatikan bahwa jika A dan B keduanya dapat diandalkan, maka 7 sebenarnya adalah jawaban yang benar, dan tidak masalah sisi mana yang lebih ringan pada C. Jika kebetulan penimbangan pada C seimbang, maka ketiga skala setuju, dan Anda memiliki jawaban Anda (koin 7) hanya dalam tiga penimbangan. Jika A dapat diandalkan dan B tidak, koin yang lebih ringan ada di [6, 8], skala mana yang akan dikonfirmasi oleh C, dan jika B dapat diandalkan dan A tidak, koin yang lebih ringan ada di [1, 4], skala C yang mana juga akan mengkonfirmasi.
Jadi dalam tiga penimbangan kami telah mengidentifikasi koin ringan atau mempersempitnya menjadi dua kelompok, dan kami juga telah mengidentifikasi skala kerja. Penimbangan keempat pada skala A atau skala B (mana pun yang disetujui oleh skala C) akan melakukan sisanya.
Solusi ini menurut saya sangat indah!
Metode ini dapat digeneralisasi untuk menemukan koin ringan di antara 32x koin dalam 3x + 1 penimbangan dengan set timbangan timbangan yang diberikan. Jadi, Anda membutuhkan tujuh penimbangan untuk 81 koin. Untuk jumlah koin yang lebih besar (>~1,000), solusi yang lebih kuat ada.
Teka-teki 4
Anda memiliki 16 koin, delapan di antaranya berat dan beratnya sama. Delapan lainnya ringan dan beratnya sama. Anda tidak tahu koin mana yang berat atau ringan. Koin terlihat identik kecuali yang memiliki tanda khusus. Dengan satu timbangan yang bagus, dapatkah Anda mengetahui apakah koin khusus itu ringan atau berat dalam tiga penimbangan? Berapa jumlah maksimum koin yang dapat Anda mulai dan berhasil menyelesaikan masalah ini dalam empat penimbangan?
Pada pandangan pertama, teka-teki ini tampaknya hampir tidak mungkin dilakukan dalam tiga penimbangan, seperti yang disimpulkan salah satu pembaca kami. Namun demikian, dengan beberapa kepintaran itu bisa dilakukan, dan keduanya Ted dan Rainer aus dem Musim Semi diberikan solusi yang benar. Ted memberikan beberapa prinsip umum yang tak ternilai yang patut diperhatikan.
Pertama, sampai Anda mendapatkan hasil yang tidak seimbang dari penimbangan, Anda tidak akan memiliki cukup informasi untuk menentukan apakah koin khusus itu berat atau ringan. Jadi Anda harus mencoba dan memaksakan hasil yang tidak seimbang.
Kedua, jika Anda mendapatkan hasil yang seimbang (misalnya koin khusus A menyeimbangkan koin B), Anda dapat menggabungkan koin yang seimbang dan menimbangnya dengan dua koin lagi, C dan D. Jika tidak seimbang, Anda memiliki jawabannya; jika tidak, Anda sekarang telah menggandakan jumlah koin yang serupa, yang mungkin membantu Anda mendapatkan jawaban yang tidak seimbang pada penimbangan berikutnya. Anda juga dapat melakukan proses ini secara terbalik dengan jumlah koin yang merupakan pangkat dua (4, 8, dll.) jika Anda memiliki hasil awal yang tidak seimbang seperti yang terlihat pada solusi berikut.
Di bawah ini adalah seluruh prosedur yang dapat mengidentifikasi jenis koin khusus A dalam semua kasus dalam tiga penimbangan. (B, C, dan D adalah tiga koin yang ditempatkan pada sisi yang sama dengan A dengan berat 1 (W1); X dan Y adalah dua koin yang tidak digunakan di W1.)
Teka-teki ini ditemukan oleh ahli matematika Rusia Konstantin Knop, otoritas dunia dalam teka-teki penimbangan koin. Banyak dari makalahnya dalam bahasa Rusia, tetapi Anda dapat menemukan beberapa teka-teki koin (di antara teka-teki menarik lainnya) di blog dari kolaboratornya Tanya Khovanova.
Untuk generalisasi, saya akan menyerahkannya kepada Anda untuk melihat apakah metode yang sama ini berhasil untuk menemukan jenis koin khusus di antara 32 koin, yang 16 koin berat dan 16 koin ringan.
Teka-teki 5
Anda harus n koin yang tampak identik, beberapa di antaranya palsu dan lebih ringan dari yang lain. Yang Anda tahu adalah bahwa setidaknya ada satu koin palsu dan ada lebih banyak koin biasa daripada yang palsu. Tugas Anda adalah mendeteksi semua koin palsu.
Fakta bahwa setidaknya ada satu koin ringan dan ada lebih banyak koin normal daripada koin ringan membuat teka-teki ini tidak terlalu rumit daripada yang pertama kali muncul, setidaknya untuk jumlah kecil. Mari kita lihat jumlah penimbangan untuk satu sampai delapan koin.
Untuk satu dan dua koin, tidak boleh ada koin ringan per kondisi kedua, jadi tidak diperlukan penimbangan.
Tiga koin: Hanya satu koin ringan. Satu penimbangan diperlukan per teka-teki 1.
Empat koin: Hanya satu koin ringan. Diperlukan satu penimbangan tambahan, jadi w = 2.
Lima koin: Satu hingga dua koin ringan. Ini adalah kasus pertama yang menarik. Pertanyaannya adalah: Haruskah kita menimbang satu koin melawan satu, atau dua koin melawan dua?
Jika kita menimbang satu lawan satu, maka kita dapat memiliki:
- Dua penimbangan yang tidak seimbang: Dua koin ditemukan; kita selesai.
- Satu penimbangan seimbang dari dua: Koin yang seimbang harus normal, jadi koin terakhir membutuhkan penimbangan lain, w = 3.
- Dua penimbangan seimbang: Pada penimbangan ketiga, timbang satu koin dari setiap penimbangan sebelumnya terhadap yang lain. Jika seimbang, keempatnya normal, dan koin 5 adalah yang ringan. Kami selesai; w = 3 lagi. Jika mereka tidak seimbang, kami telah menemukan dua koin ringan, dan kami selesai dalam tiga penimbangan.
Jika sebaliknya kita menimbang dua lawan dua, kita masih membutuhkan tiga penimbangan, karena kita harus membedakan antara kemungkinan bahwa koin mungkin berbeda atau serupa di kedua sisi. Penimbangan menggunakan sejumlah kecil koin yang dikelompokkan bersama tampaknya tidak memiliki keunggulan dibandingkan penimbangan dengan koin tunggal.
Hal ini dimaklumi untuk:
Enam koin: Satu hingga dua koin ringan; w = 4.
Tujuh koin: Satu hingga tiga koin ringan; w = 5.
Delapan koin: Satu hingga tiga koin ringan; w = 6. Solusi ini memiliki struktur sederhana:
- Pertama, lakukan empat penimbangan satu koin terhadap koin berikutnya. Semua koin digunakan.
- Kasus terburuk: Keempat penimbangan seimbang (ada dua koin ringan yang saling menyeimbangkan).
- Dua penimbangan berikutnya: Timbang koin dari penimbangan 1 terhadap koin dari penimbangan 2; dengan cara yang sama, timbang koin dari berat 3 melawan koin dari berat 4.
- Salah satu penimbangan ini akan menjadi tidak seimbang, mengidentifikasi dua koin ringan. Kami selesai dalam enam penimbangan.
Maaf, urutan 0, 0, 1, 2, 3, 4, 5, 6 kami tentu tidak cukup menarik untuk disampaikan ke Ensiklopedia Online Barisan Bilangan Bulat!
As Jonas Tøgersen Kjellstadli menunjukkan, solusinya tampaknya w = n 2 untuk bilangan kecil, tetapi kami belum membuktikan bahwa ini tidak akan berubah untuk bilangan yang lebih besar. Di beberapa n, menggunakan beberapa penimbangan koin mungkin mulai menghasilkan lebih baik, atau lebih banyak penimbangan daripada n 2 mungkin diperlukan. Kami hanya dapat menggeneralisasi solusi untuk delapan koin untuk semua kekuatan 2, memberikan n 2 sebagai batas atas untuk jumlah penimbangan untuk semua pangkat 2.
Mark Pearson membahas kesamaan masalah ini dengan kode koreksi kesalahan dan menyarankan menggunakan pendekatan teori informasi berdasarkan jumlah kemungkinan hasil. Dengan menggunakan pendekatan seperti itu, Mike Roberts memposting batas bawah untuk kasus yang lebih umum, yang Rainer aus dem Musim Semi diturunkan pendekatan untuk. Rainer juga memposting batas atas dari makalah yang diterbitkan tetapi mencatat bahwa batasnya tidak tajam untuk n dan karena itu tidak membantu untuk jumlah kecil yang telah kami pertimbangkan di atas. Jadi, untuk tujuh koin, batas yang dikutip memberikan kisaran 4 hingga 16, di mana jawaban kami, 5, berada di antaranya. J. Payet memberikan referensi dan batasan matematika tambahan untuk semua teka-teki.
Terima kasih untuk semua yang telah berpartisipasi. Hadiah Wawasan untuk bulan ini diberikan bersama-sama kepada Ted dan Rainer aus dem Spring. Selamat!
Sampai jumpa di lain waktu untuk yang baru Wawasan.
