Pertempuran Ketujuh Untuk Negara Riddler

Selamat datang di The Riddler. Hampir setiap minggu, saya menawarkan dua masalah yang berkaitan dengan hal-hal yang kita sayangi di sini: matematika, logika, dan probabilitas.

Tapi minggu ini spesial. Waktu telah berlalu, dan entah bagaimana sudah tiga tahun sejak saya (dengan damai) mengambil alih kolom ini dari pendahulu saya, Oliver Roeder.

Sudah sepantasnya kita melanjutkan salah satu tradisi favorit Ollie (dan saya) di sini di The Riddler: Battle for Riddler Nation. Untuk memiliki kesempatan menang dan menjadi penguasa berikutnya, saya harus menerima rencana pertempuran Anda sebelum pukul 23:59 waktu Timur pada hari Senin. Selamat berakhir pekan!

Riddler minggu ini

Beberapa pembaca mungkin akrab dengan Pertempuran pertama, kedua, ketiga, keempat, kelima dan keenam untuk Riddler Nation. Jika Anda ketinggalan, Anda mungkin ingin berkonsultasi dengan ribuan distribusi serangan dari beberapa kontes sebelumnya.

Saya senang untuk mengatakan bahwa minggu ini menandai kompetisi ketujuh — tetapi seperti tahun-tahun sebelumnya, saya mengubah aturan.

Di negeri jauh yang dilanda perang, ada 10 kastil. Ada dua panglima perang: Anda dan musuh bebuyutan Anda. Setiap kastil memiliki nilai strategisnya sendiri untuk calon penakluk. Secara khusus, kastil bernilai 1, 2, 3, …, 9 dan 10 poin kemenangan. Anda dan musuh Anda masing-masing memiliki 100 barisan tentara untuk dibagikan, dengan cara apa pun yang Anda suka, untuk bertarung di salah satu dari 10 kastil. Siapa pun yang mengirim lebih banyak phalanx ke kastil tertentu akan menaklukkan kastil itu dan memenangkan poin kemenangannya. Jika Anda masing-masing mengirim jumlah phalanx yang sama, Anda membagi poin. Anda tidak tahu distribusi kekuatan apa yang telah dipilih musuh Anda sampai pertempuran dimulai. Siapa pun yang memenangkan poin terbanyak memenangkan perang.

Kirimkan rencana untuk mendistribusikan 100 phalanx Anda di antara 10 kastil. Setelah saya menerima semua rencana pertempuran Anda, saya akan memutuskan semua kemungkinan pertarungan satu lawan satu. Pada tahun-tahun sebelumnya, siapa pun yang memenangkan perang paling banyak juga memenangkan battle royale dan dinobatkan sebagai penguasa Riddler Nation. Tapi tidak kali ini!

Setelah semua pertarungan satu lawan satu selesai, Anda akan diunggulkan dalam turnamen eliminasi tunggal untuk menentukan pemenang akhir. Itu berarti strategi yang optimal tidak lagi hanya memangsa strategi yang lebih lemah tetapi juga mengalahkan strategi yang sama kuatnya.

Siapa yang bisa mencuri mahkota dari Bill Neagle dari Springfield, Missouri, pemenang tahun lalu?

Mungkin Anda memiliki kelicikan dan logika untuk menjadi penguasa Riddler Nation berikutnya!

Kirimkan strategi Anda

Solusi untuk Riddler Express minggu lalu

Selamat kepada Liorel dari Grenoble, Prancis, pemenang Riddler Express minggu lalu.

Minggu lalu, ibu peri Anda muncul dan memberi Anda kesempatan untuk bermain game. Dalam permainan ini, dia membagikan 10 kartu tertutup. Sembilan dari kartu itu adalah pemenang, dan satu kartu adalah pecundang. Jika Anda memilih kartu yang menang, Anda mendapat hadiah. Anda kemudian dapat mengambil hadiah Anda dan pergi atau bermain lagi untuk kesempatan memenangkan hadiah kedua. Tetapi jika Anda kalah pada permainan kedua itu, Anda pergi tanpa apa-apa dan permainan berakhir. Setiap kali Anda berhasil, dia mengundang Anda untuk bermain lagi dalam kondisi yang sama (memenangkan hadiah lain atau kehilangan segalanya).

Strategi apa yang memaksimalkan jumlah rata-rata hadiah yang Anda harapkan untuk dimenangkan? Dan berapa rata-rata itu?

Pertama, beberapa pembaca mencatat sedikit ambiguitas dalam masalah. Setiap kali Anda bermain berturut-turut, apakah kartu pemenang sebelumnya dikeluarkan dari dek atau malah dikocok kembali? Dalam pandangan saya, kedua interpretasi itu valid, jadi saya akhirnya menerima dua solusi.

Mari kita mulai dengan kasus di mana kartu pemenang dihapus. Misalkan Anda sudah menang w kali, artinya sekarang ada 10−w kartu yang tersisa di dek, salah satunya adalah kartu yang kalah. Jika Anda bermain lain putaran, Anda berdiri untuk memenangkan satu hadiah lagi dengan probabilitas (10−w1)/(10−w). Tetapi jika Anda memilih kartu yang kalah itu, Anda kehilangan semuanya w hadiah yang telah Anda menangkan dengan probabilitas 1/(10−w).

Sekarang, masuk akal untuk bermain kapan pun kemenangan yang Anda harapkan melebihi kerugian yang Anda harapkan, yaitu, ketika 1·(10−w1)/(10−w) lebih besar dari w·1/(10−w). Mengalikan kedua ruas dengan penyebut yang sama menghasilkan pertidaksamaan 10−w1 > wyang disederhanakan menjadi w <4.5. Dengan kata lain, Anda bermain sampai Anda kalah atau memenangkan lima hadiah, di mana Anda pergi.

Dan berapa banyak hadiah yang bisa Anda harapkan untuk menang dengan strategi optimal ini? Anda lolos dengan hadiah jika Anda berhasil mencapai putaran kelima, yang terjadi dengan probabilitas (9/10)·(8/9)·(7/8)·(6/7)·(5/6), yang disederhanakan ke 1/2. Pada ronde kelima itu, Anda lolos dengan lima hadiah, jadi kemenangan yang diharapkan adalah (1/2)·5, atau 2.5 hadiah.

Adapun kasus di mana kartu yang menang adalah bukan dihapus, probabilitas Anda untuk memenangkan setiap putaran selalu 9/10. Jadi jika Anda sudah menang w hadiah, masuk akal untuk bermain jika 9/10 lebih besar dari w/10. Pada kasus ini, Anda bisa bermain sampai Anda memenangkan sembilan atau 10 hadiah — keduanya menghasilkan nilai harapan yang sama. Probabilitas memenangkan sembilan putaran adalah (9/10)⁹dan kemudian Anda memenangkan sembilan hadiah, yang berarti kemenangan yang Anda harapkan adalah 9¹⁰/10⁹atau tentang 3.487 hadiah.

Untuk kredit tambahan, ibu peri Anda memiliki setumpuk N kartu bukan 10 kartu. Lagi, N1 adalah kartu yang menang dan satu lagi adalah kartu yang kalah. Sekarang apa strategi Anda, dan berapa banyak hadiah yang Anda harapkan untuk menang rata-rata?

Jika Anda menggambar kartu dengan penggantian, maka taruhan terbaik Anda adalah selalu menggambar juga N1 atau N kartu untuk harapan (N1)^N/N^(N1) hadiah. Tetapi jika Anda menggambar tanpa pengembalian, maka jawabannya tergantung pada paritas N (yaitu, apakah N genap atau ganjil). Jika N bahkan, seperti halnya ketika N adalah 10, taruhan terbaik Anda adalah menggambar N/2 kartu untuk harapan N/4 hadiah. Akhirnya, jika N aneh, maka Anda bisa menggambar (N1)/2 atau (N+1)/2 kartu untuk harapan N/4−1/N hadiah.

Bagaimanapun, saya akan menghargai ibu peri yang membagikan hadiah tanpa batasan. Kehilangan kartu, kereta berubah kembali menjadi labu di tengah malam — apa yang memberi?

Solusi untuk Riddler Classic minggu lalu

Selamat kepada Steve Schaefer dari Carlsbad, California, pemenang Riddler Classic minggu lalu.

Minggu lalu, Anda melihat kembali teka-teki dari beberapa tahun yang lalu tentang mobil yang terjebak dalam kemacetan lalu lintas. Dalam teka-teki asli, ada N mobil di jalan raya yang panjang dan lurus dengan satu lajur. Setiap mobil melaju ke arah yang sama tetapi dengan kecepatan konstan yang unik dan dipilih secara acak. Namun, jika seorang pengemudi mengejar mobil lain yang lebih lambat (atau sekelompok mobil yang sama terhalang oleh mobil yang lebih lambat itu), mereka tetap terjebak di belakang mobil yang lebih lambat itu.

Kali ini, jalur kedua telah terbuka. Tangkapannya adalah bahwa ada hanya satu titik masuk ke jalur kedua ini, sehingga setiap mobil memiliki tepat satu kesempatan untuk memutuskan apakah akan melanjutkan ke jalur kedua ini.

Dari mobil pertama di jalur asli ke mobil terakhir, masing-masing memutuskan apakah akan beralih ke jalur kedua saat lewat. Untungnya, setiap mobil mengetahui kecepatan setiap mobil lain, jadi masing-masing membuat saklar asalkan pada akhirnya dapat melaju dengan kecepatan yang lebih tinggi (baik sendiri atau sebagai bagian dari kelompok yang lebih cepat).

Rata-rata, berapa jumlah rombongan mobil yang akhirnya terbentuk di kedua lajur tersebut?

Seperti yang sering kali merupakan ide bagus di sini, mari kita mulai dengan nilai kecil dari N dan lihat apa yang terjadi. Kapan N adalah 1, ada satu kelompok mobil — tidak terlalu menarik. Kapan N adalah 2, selalu ada dua kelompok mobil, karena jika mobil yang lebih cepat mulai dari belakang, ia akan pindah ke jalur kedua dan melanjutkan tanpa hambatan.

Tapi segalanya menjadi lebih rumit ketika N adalah 3. Di antara enam kemungkinan urutan kecepatan relatif mereka di sepanjang jalan, lima menghasilkan ketiga mobil menjadi kelompok mereka sendiri. Tapi ketika mobil paling lambat pertama di jalan dan mobil tercepat terakhir, mobil tengah akhirnya menghalangi mobil tercepat di jalur kedua. Jadi ketika N adalah 3, jumlah rata-rata kelompok adalah 17/6, sedikit kurang dari 3.

Untuk menemukan solusi umum, pemecah Sanandan Swaminathan pertama-tama meninjau versi satu jalur dari teka-teki ini. Ketika ada N mobil, mobil terakhir di jalan hanya membentuk kelompoknya sendiri ketika itu adalah mobil paling lambat, yang terjadi dengan probabilitas 1/N. Itu berarti jumlah kelompok yang diharapkan dengan N mobil, E(N), sama dengan E(N1) + 1/N.

Kini, dengan dua lajur, Sanandan kembali meneliti kemungkinan mobil terakhir di jalan membentuk kelompoknya sendiri. Ketika mobil terakhir adalah yang paling lambat, sekali lagi dengan probabilitas 1/N, itu dijamin untuk membentuk kelompok sendiri. Ketika mobil terakhir adalah kedua-paling lambat, terhambat oleh mobil paling lambat (yang tidak pernah berpindah jalur), sehingga berpindah dan menjadi mobil paling lambat di jalur kedua — lagi-lagi menjamin bahwa ia membentuk grupnya sendiri. Ketika mobil terakhir adalah ketiga-paling lambat, kembali beralih ke jalur kedua. Tapi itu hanya membentuk grupnya sendiri jika mobil paling lambat kedua tidak beralih jalur, yang terjadi setengah dari waktu di mana mobil paling lambat kedua mulai mendahului mobil paling lambat.

Anda mungkin melihat ke mana arahnya, tetapi mari kita lihat satu contoh lagi — ketika mobil terakhir adalah keempat-paling lambat. Sekali lagi, ia beralih jalur, dan menemukan dirinya dalam kelompoknya sendiri ketika mobil paling lambat ketiga mulai di depan mobil paling lambat kedua, yang pada gilirannya mulai di depan mobil paling lambat — sesuatu yang terjadi 1/6 dari waktu.

Sementara rumus rekursif relatif ringkas untuk teka-teki satu jalur, jalur kedua tentu saja membuat air menjadi berlumpur. Kali ini, E(N) = E(N1) + 1/(0!·N) + 1/(1!·N) + 1/(2!·N) + 1/(3!·N) + … 1/((N1)!·N). Kita dapat memeriksa ulang rumus ini ketika ada tiga mobil. Kami sudah mengatakan E(2) adalah 2, jadi E(3) adalah 2 + 1/3 + 1/3 + 1/6, atau 17/6 — nilai yang sama yang kita dapatkan sebelumnya! Ini lebih lanjut berarti bahwa E(4) adalah 17/6 + 1/4 + 1/4 + 1/8 + 1/24, atau 7/2.

Beberapa pemecah melangkah lebih jauh dengan mencoba menemukan pendekatan bentuk tertutup atau bahkan ekspresi yang tepat untuk E(N). Salah satu pendekatan penting yang terlibat adalah memfaktorkan 1/N dari ekspresi sebelumnya, yang memberimu E(N) = E(N1) + 1/N · (1/0! + 1/1! + 1/2! + 1/3! + … + 1/(N−1)!). Jumlah di dalam tanda kurung terkenal konvergen ke e sebagai N menjadi sangat besar. Itu berarti ada kira-kira e kali lebih banyak kelompok mobil dengan dua lajur dibandingkan dengan satu lajur. Pembaca Josh Silverman dan Jim Crimmins masing-masing menunjukkan fakta ini secara empiris: