ปริศนาคณิตศาสตร์ / ตรรกะ
ใครมีข้อมูลเชิงลึกเกี่ยวกับวิธีแก้ปัญหานี้ เพื่อนของฉันถามฉันเกี่ยวกับเรื่องนี้และมันรบกวนฉันมาสองสามวันแล้ว ฉันพยายามเข้าหามันโดยการเหนี่ยวนำ (กรณีฐานที่มีคนสองคนตรงไปตรงมา แต่ฉันติดอยู่ในขั้นตอนอุปนัย) อย่างไรก็ตามฉันคิดว่ามันเป็นปัญหาที่สนุกและอยากรู้ว่าจะเข้าหามันอย่างไร เคล็ดลับในการแก้ปัญหาที่เป็นไปได้จะน่ารัก!
บางคนยืนล้อมวงแลกเปลี่ยนสิ่งของ แต่ละชิ้นเริ่มต้นด้วยช็อกโกแลตจำนวนเท่ากัน - ไม่จำเป็นต้องเหมือนกัน ทุกนาทีแต่ละคนส่งสิ่งของครึ่งหนึ่งไปให้คนทางขวา หากใครลงเอยด้วยช็อคโกแลตจำนวนคี่พวกเขาจะหยิบของอีกชิ้นจากขวดที่อยู่ตรงกลาง พิสูจน์ว่าโดยไม่คำนึงถึงการกระจายช็อคโกแลตครั้งแรกหลังจากขั้นตอนจำนวน จำกัด ทุกคนจะจบลงด้วยวัตถุจำนวนเท่ากัน
คำตอบ
เราสามารถอธิบายสถานการณ์ด้วยตัวเลขสามตัว $(M,m,r)$, ที่ไหน $2M$ คือจำนวนเงินสูงสุดที่ผู้เล่นมี $m$ เป็นจำนวนน้อยที่สุดและ $r$ คือจำนวนผู้เล่นที่มี $2m$.
หากผู้เล่นเป็น $2a$ ชิ้นส่วนและเพื่อนบ้านด้านซ้ายของพวกเขามี $2b$ ในรอบต่อไปผู้เล่นคนนี้จะมี $ (2a-a)+b= a+b\le 2M$ชิ้น. แม้ว่า$a+b$ เป็นเรื่องแปลกก็คือ $\le 2M-1$ และหลังจากเติมจากขวดแล้วก็ยังคงอยู่ $\le 2M$. ในทำนองเดียวกันจำนวนเงินใหม่คือ$\ge 2m$ ด้วยความเท่าเทียมกันถ้าและต่อเมื่อ $a=b=m$. เราสรุปได้ว่าสถานการณ์$(M,m,r)$ กลายเป็น $(M',m',r')$ ด้วย $m\le m'\le M'\le M$. ยิ่งไปกว่านั้นถ้า$m'=m$แล้ว $r'\le r$.
แต่มันไม่สามารถเกิดขึ้นได้ $(M',m',r')=(M,m,r)$ เว้นแต่ $M=m$. อันที่จริงถ้า$m<M$แล้วจะต้องมีใครสักคนด้วย $2m$ชิ้นส่วนเพื่อนบ้านด้านซ้ายของพวกเขามีมากขึ้น แล้วคนนี้จะมี$>2m$ ในรอบถัดไปหมายความว่าอย่างใดอย่างหนึ่ง $m'>m$ หรืออย่างน้อย $r'<r$.
ในอัตราใด ๆ ถ้า $M>m$จากนั้นจะใช้เวลาเพียงขั้นตอนของมนุษย์อย่างละเอียดจนกระทั่ง $M-m$ลดลงอย่างน้อยหนึ่ง หลังจากผ่านไปหลายขั้นตอนเราก็มาถึง$M=m$.
พิจารณาคนที่มีช็อคโกแลตน้อยที่สุดในแต่ละขั้นตอน เธอส่งช็อคโกแลตครึ่งหนึ่งของเธอ แต่ได้รับช็อคโกแลตครึ่งหนึ่งจากคนที่มีช็อคโกแลตอย่างน้อยที่สุดเท่าที่เธอทำ ดังนั้นจำนวนช็อคโกแลตของเธอจึงเพิ่มขึ้นหรือเท่าเดิมหากคนที่อยู่ทางซ้ายของเธอมีช็อคโกแลตเท่ากัน ดังนั้นจำนวนช็อคโกแลตที่น้อยที่สุดในแต่ละขั้นตอนไม่เคยลดลง
สมมติว่าคน ๆ หนึ่งมีมากกว่าอย่างน้อยที่สุด ถ้าจำนวนช็อคโกแลตน้อยที่สุดคือ$L$ และคนที่มีมากกว่าน้อยที่สุด $L + 2a$ จากนั้นเขาก็ให้ไป $\frac 12L + a$ แต่ได้รับอย่างน้อย $\frac 12L$ และมี $L + a > L$. ดังนั้นคนที่ไม่มีอย่างน้อยในขั้นตอนเดียวก็ไปไม่ได้อย่าไปน้อยที่สุดในขั้นต่อไป
ดังนั้นจำนวนช็อคโกแลตที่น้อยที่สุดในขั้นตอนจะไม่สามารถลดจำนวนลงเป็นจำนวนที่น้อยลงได้ในขั้นตอนถัดไป และถ้าจำนวนช็อคโกแลตน้อยที่สุดในขั้นตอนเดียวกับจำนวนช็อคโกแลตที่น้อยที่สุดในขั้นตอนถัดไปสิ่งนั้นจะเกิดขึ้นได้ก็ต่อเมื่อคนที่มีช็อคโกแลตน้อยที่สุดอยู่ทางขวาของคนที่มีจำนวนช็อคโกแลตเท่ากัน และคน ๆ นั้นลงเอยด้วยช็อคโกแลตจำนวนเท่ากัน
[หมายเหตุ: บุคคลที่มีจำนวนน้อยที่สุดก่อนหน้านี้สามารถจบลงในขั้นตอนถัดไปโดยมีจำนวนน้อยที่สุดใหม่ที่มากกว่าตัวเลขต่ำสุดก่อนหน้านี้ แต่บุคคลนั้นสามารถบันทึกลงท้ายด้วยตัวเลขที่น้อยที่สุดก่อนหน้านี้ ]
แต่ถ้าทุกคนมีช็อคโกแลตไม่เท่ากัน (ถ้าทำเสร็จแล้ว) ก็จะมีกลุ่มคนจำนวนมากที่สุดที่มีช็อคโกแลตน้อยที่สุด $n$คนยาว แต่ละก้าวคนที่อยู่ปลายโซ่จะมีช็อคโกแลตมากขึ้นและโซ่จะสั้นลงทีละชิ้น (และจากย่อหน้าก่อนหน้านี้เรารู้ว่าไม่มีคนใหม่ที่จะลงเอยด้วยจำนวนน้อยที่สุดก่อนหน้านี้ ) หลังจากนั้น$n$ ขั้นตอนทุกคนจะมีช็อคโกแลตมากขึ้นและจำนวนน้อยที่สุดที่เป็นไปได้จะเพิ่มขึ้น
ดังนั้นหากมีขีด จำกัด สูงสุดของจำนวนช็อคโกแลตสูงสุดที่เป็นไปได้จำนวนน้อยที่สุดเมื่อสิ้นสุดขั้นตอนในที่สุดก็จะไปถึงจุดที่ทุกคนมีช็อกโกแลตจำนวนเท่ากันสำหรับบางจำนวนที่เท่ากับหรือน้อยกว่าค่าสูงสุดที่เป็นไปได้นั้น
ดังนั้นพิจารณาช็อคโกแลตที่คนส่วนใหญ่มีในตอนท้ายของขั้นตอน โทร$M$ในทางกลับกันคนนั้นให้ช็อคโกแลตครึ่งหนึ่งและรับช็อคโกแลตครึ่งหนึ่งหรือน้อยกว่านั้น ถ้าเขาได้รับมากเท่าที่เขาให้ไปเขามีจำนวนเท่ากันและเขาจะได้จำนวนเท่ากัน$M$. ถ้าเขาได้รับน้อยลงแม้ว่าเขาจะเพิ่มช็อคโกแลตเขาก็จบลงด้วยสิ่งที่เขาเริ่มต้น
ดังนั้น .... ช็อคโกแลตส่วนใหญ่ที่ใคร ๆ ก็เคยมีมานั้นมีจำนวน จำกัด $M=$ ช็อคโกแลตมากที่สุดที่ใคร ๆ ก็เคยทาน $1$. ช็อคโกแลตน้อยที่สุดที่คนอาจมีคือ$L=$ ช็อคโกแลตน้อยที่สุดที่ใคร ๆ ก็เคยทาน $1$แต่ขั้นต่ำนั้นจะเพิ่มขึ้นในจำนวนขั้นตอนที่ จำกัด เสมอเว้นแต่ทุกคนจะมีจำนวนเท่ากัน เนื่องจากมีข้อ จำกัด ว่าขั้นต่ำจะสูงเพียงใดกระบวนการจะต้องจบลงด้วยความเท่าเทียมกัน ในที่สุด.