หัวข้อ:

ทางเดินตรงมีประตู 5 บานอยู่ตลอดด้านหนึ่ง หลังประตูบานหนึ่งมีแมวอยู่ ภารกิจของคุณคือค้นหาแมวโดยการเปิดประตูที่ถูกต้อง คุณสามารถเปิดประตูได้เพียง 1 ประตูต่อวัน ถ้ามีแมวอยู่ตรงนั้น คุณชนะ

ถ้าไม่มีแมวอยู่ ประตูจะปิด และคุณต้องรอจนถึงวันถัดไปจึงจะเปิดประตูได้อีกครั้ง แมวเคลื่อนไหวอย่างไม่สงบ และทุกคืนมันจะย้ายไปนั่งอยู่หลังประตูบานอื่น ประตูที่เลื่อนไปจะเป็นประตูที่อยู่ด้านซ้ายหรือขวาของตำแหน่งที่เลื่อนไป

คุณต้องใช้เวลาอีกกี่วันจึงจะแน่ใจว่าจะพบแมว?

ปัญหาคือการขอให้คุณหาแนวทางที่รับประกันว่าคุณจะจับแมวได้ภายในจำนวนวันที่กำหนด โดยไม่คำนึงว่าแมวจะเริ่มจากประตูไหนและเคลื่อนไหวไปที่ใดในเวลากลางคืน กุญแจสำคัญในการแก้ปัญหาคือเริ่มด้วยจำนวนประตูที่น้อย ค้นหารูปแบบ แล้วค่อยเพิ่มจำนวนประตู

มาเริ่มด้วยเคสที่มีประตูเพียง 3 บานก่อน หากคุณเปิดประตูกลางติดต่อกัน 2 วัน คุณรับรองได้เลยว่าจะจับแมวได้ เนื่องจากหากวันแรกที่เปิดประตูกลาง แมวจะต้องอยู่หลังประตูใดประตูหนึ่งไม่ว่าจะด้านใดด้านหนึ่งก็ตาม และหากอยู่หลังประตูด้านใดด้านหนึ่งในวันที่หนึ่ง ก็ไม่มีทางเลือกอื่นนอกจากต้องย้ายไปที่ประตูกลางในวันที่สอง

ถ้ามีประตู 4 บาน สามารถจับแมวได้ภายใน 4 วัน คุณสามารถหาคำอธิบายได้ในคำตอบด้านล่างนี้ แต่ก่อนหน้านั้น ลองอธิบายด้วยตนเองดูก่อน จำไว้ว่าแมวจะเคลื่อนตัวไปที่ประตูทางขวาหรือซ้ายทันทีเท่านั้น และสามารถกลับไปที่ประตูที่มันนั่งอยู่ก่อนหน้านี้ได้ เชื่อว่าคุณจะรู้สึกมีความสุขเมื่อพบคำอธิบาย

>>> ตอบ

โวก๊วก บา จัน

ครูสอนคณิตศาสตร์ โรงเรียนอาร์คิมิดีส ฮานอย