Puzzle Matematika / Logika
Ada yang punya wawasan tentang cara mengatasi masalah ini? Teman saya bertanya tentang hal itu dan hal itu mengganggu saya selama beberapa hari. Saya mencoba mendekatinya dengan induksi (kasus dasar dengan dua orang sangat mudah, tetapi saya terjebak pada langkah induktif). Bagaimanapun, saya pikir itu adalah masalah yang menyenangkan dan ingin tahu bagaimana mendekatinya. Setiap tip tentang solusi yang mungkin akan menyenangkan!
Beberapa orang berdiri dalam lingkaran bertukar benda. Masing-masing dimulai dengan jumlah cokelat genap - belum tentu sama. Setiap menit, masing-masing orang menyerahkan setengah benda mereka ke orang di sebelah kanannya. Jika ada yang mendapatkan cokelat dalam jumlah ganjil, mereka mengambil benda lain dari toples di tengahnya. Buktikan bahwa terlepas dari distribusi awal cokelat, setelah beberapa langkah, semua orang akan mendapatkan jumlah objek yang sama.
Jawaban
Kita bisa menggambarkan situasi dengan tiga angka $(M,m,r)$, dimana $2M$ adalah jumlah maksimal yang dimiliki pemain, $m$ adalah jumlah minimal, dan $r$ adalah jumlah pemain dengan $2m$.
Jika pemain sebagai $2a$ potongan dan tetangga kiri mereka memiliki $2b$ bidak, di babak berikutnya, pemain ini akan memiliki $ (2a-a)+b= a+b\le 2M$potongan. Bahkan jika$a+b$ itu aneh $\le 2M-1$ dan setelah isi ulang dari toples, itu masih $\le 2M$. Begitu juga dengan jumlah yang baru$\ge 2m$ dengan kesetaraan jika dan hanya jika $a=b=m$. Kami menyimpulkan bahwa situasi$(M,m,r)$ berubah menjadi $(M',m',r')$ dengan $m\le m'\le M'\le M$. Apalagi jika$m'=m$, kemudian $r'\le r$.
Tapi itu tidak bisa terjadi $(M',m',r')=(M,m,r)$ kecuali kalau $M=m$. Memang, jika$m<M$, maka pasti ada seseorang dengan $2m$potongan sementara tetangga kiri mereka memiliki lebih banyak. Maka orang ini akan memilikinya$>2m$ potongan di babak berikutnya, artinya baik $m'>m$ atau setidaknya $r'<r$.
Bagaimanapun, jika $M>m$, maka hanya dibutuhkan langkah-langkah hingga $M-m$berkurang setidaknya satu. Kemudian masih setelah banyak langkah, kami mencapai$M=m$.
Pertimbangkan seseorang dengan jumlah cokelat paling sedikit dalam satu langkah. Dia memberikan setengah coklatnya tetapi menerima setengah dari coklat dari seseorang yang memiliki coklat sebanyak dia. Jadi jumlah coklatnya bertambah atau tetap sama jika orang di sebelah kirinya juga memiliki jumlah coklat yang sama. Jadi jumlah cokelat paling sedikit dalam satu langkah tidak pernah turun.
Sekarang misalkan seseorang memiliki lebih dari yang sedikit. Jika jumlah cokelat paling sedikit$L$ dan orang yang memiliki lebih dari sedikit $L + 2a$ lalu dia memberikan $\frac 12L + a$ tapi setidaknya mendapat $\frac 12L$ dan begitu juga $L + a > L$. Jadi, orang yang tidak memiliki paling sedikit satu langkah pun tidak bisa pergi ke jumlah paling sedikit di langkah berikutnya.
Jadi jumlah cokelat paling sedikit dalam satu langkah tidak akan pernah bisa berkurang menjadi jumlah yang lebih kecil di langkah berikutnya. Dan jika jumlah cokelat paling sedikit dalam satu langkah sama dengan jumlah cokelat paling sedikit di langkah berikutnya, itu hanya dapat terjadi jika orang dengan jumlah cokelat paling sedikit berada di sebelah kanan orang dengan jumlah cokelat yang sama. dan orang itu mendapatkan jumlah cokelat yang sama.
[Catatan: orang dengan lebih dari angka terkecil sebelumnya dapat berakhir di langkah berikutnya dengan angka terkecil baru yang lebih dari angka terkecil sebelumnya, tetapi orang tersebut dapat mencatat berakhir dengan angka terkecil sebelumnya .]
Tetapi jika semua orang tidak memiliki jumlah coklat yang sama (jika mereka melakukannya kita sudah selesai) maka ada rantai maksimum orang dengan jumlah coklat paling sedikit. $n$orang merindukan. Setiap langkah orang di ujung rantai akan mendapatkan lebih banyak cokelat dan rantai akan memendek satu per satu. (Dan dari paragraf sebelumnya kita tahu tidak ada orang baru yang akan mendapatkan jumlah paling sedikit sebelumnya .) Jadi setelah itu$n$ langkah setiap orang akan memiliki lebih banyak cokelat dan jumlah yang paling mungkin akan meningkat.
Jadi, jika ada batas atas untuk jumlah maksimum cokelat yang mungkin, maka jumlah terkecil di akhir langkah pada akhirnya akan mencapai titik di mana setiap orang memiliki jumlah cokelat yang sama untuk beberapa angka yang sama atau kurang dari jumlah maksimum potensial tersebut.
Jadi pertimbangkan cokelat paling banyak yang dimiliki seseorang di akhir langkah. Sebut saja$M$Pada giliran berikutnya orang tersebut memberikan setengah coklat dan menerima setengah atau lebih sedikit coklat. Jika dia menerima sebanyak yang dia berikan, dia memiliki jumlah genap dan dia berakhir dengan jumlah yang sama$M$. Jika dia menerima lebih sedikit, bahkan jika dia menambahkan cokelat, dia akan mendapatkan paling banyak dari apa yang dia mulai.
Jadi .... cokelat paling banyak yang pernah dimiliki seseorang adalah terbatas $M=$ cokelat paling banyak yang dimiliki siapa pun pada langkahnya $1$. Paling sedikit cokelat yang mungkin dimiliki seseorang$L=$ paling sedikit cokelat yang dimiliki siapa pun pada langkahnya $1$tetapi jumlah minimum itu akan selalu bertambah dalam jumlah langkah yang terbatas kecuali semua orang memiliki jumlah yang sama. Karena ada batasan seberapa tinggi minimum dapat menjadi proses harus diakhiri dengan kesetaraan. Akhirnya.