สวิตท์สองตัว

ปัญหา

มีนักโทษอยู่จำนวน 20 คน ทุกคนตกลงเข้าร่วมเล่นเกมที่มีเดิมพันว่า ถ้าชนะทุกคนจะพ้นโทษ แต่ถ้าแพ้จะถูกประหารทันที

เกมมีอยู่ว่า มีห้องปิดห้องหนึ่ง ที่ภายในห้องมีเพียงกำแพงเปล่าๆ ประตูทางเข้า และสวิตท์ไฟเปล่าๆ ที่ไม่ได้ต่อกับสายไฟสองตัว ที่สามารถสับได้เพียงขึ้นและลง และตอนเริ่มเกม สวิตท์ทั้งสองจะถูกสับแบบสุ่ม

[(ขึ้น ลง) (ลง ลง) (ลง ขึ้น) (ขึ้น ขึ้น) เป็นเงื่อนไขเริ่มต้นที่เป็นไปได้ทั้งหมด]

เมื่อเริ่มเกม นักโทษทุกคนจะถูกแยกไปยังห้องขังต่างๆกัน โดยแต่ละคนไม่สามารถรู้ว่าข้างนอกเกิดอะไรขึ้น จนกว่าจะมีผู้คุมมาเปิดห้องและเรียกออกไป

ผู้คุม จะทำการสุ่มนักโทษมา 1 คน โดยทุกคนจะมีโอกาสถูกสุ่มเท่ากัน

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

โดยถ้าสวิตท์ไฟขึ้นอยู่ นักโทษนั้นต้องสับลง และถ้าสวิตท์ไฟลงอยู่ ก็ต้องสับขึ้น (ไม่สามารถสับให้อยู่ระหว่างกลาง และอยู่ตำแหน่งอื่นๆ ที่ไม่ใช่ตำแหน่งบนสุดและล่างสุด และไม่สามารถเลือกที่จะไม่สับได้)

และนักโทษคนนั้น จะถูกนำกลับไปห้องขังเดิม ผู้คุมจะสุ่มนักโทษขึ้นมาอีกครั้ง (มีโอกาสสุ่มได้คนเดิม) โดยช่วงเวลาระหว่างการเรียกนักโทษแต่ละคนต่างกัน (สามารถเรียกได้ว่าเป้นการสุ่มเช่นกัน) นำนักโทษไปสับสวิตท์ และวนเช่นนี้ไปเรื่อยๆ

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

เกมนี้ จะจบลงก็ต่อเมื่อมีนักโทษคนหนึ่งพูดขึ้นว่า "ผมมั่นใจว่า ผมและเพื่อนทุกคนเคยเข้าห้องนั้น"

ถ้าทุกคนเคยเข้าห้องจริง ทุกคนจะพ้นโทษ แต่ถ้ามีอย่างน้อยคนหนึ่งที่ยังไม่เคยถูกเรียกไปเข้าห้องปิดนั้น ทุกคนจะถูกประหาร

ถ้าอนุญาติให้นักโทษปรึกษากันก่อนจะเริ่มเล่นเกม และมีกฏพิเศษข้อหนึ่งว่า ก่อนเริ่มเกม ต้องเลือกนักโทษคนหนึ่ง นักโทษคนนั้นเลือกสวิตท์ข้างใดข้างหนึ่ง (ซ้าย หรือ ขวา)

และตลอดทั้งเกม ถ้าคนๆนั้นถูกเรียกตัวไปสับสวิตท์ จะต้องสับสวิตท์ที่เลือกไว้เท่านั้น

ถามว่านักโทษต้องทำอย่างไรถึงจะรอดชีวิต (ถ้าไม่มีใครพูดอะไร นักโทษก็จะต้องสับสวิตท์ไปจนตายอยู่ดี)

คำใบ้

- วิธีการที่ถูกต้อง สามารถยืนยันได้ 100%

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

คำตอบ

ผมขอโพส solution ของผมนะ ถูกหรือเปล่าบอกด้วยนะครับ ^^ (คลุมดำเพื่ออ่าน)

switch มี 2 ตัว ให้ตัวนึงชื่อ s อีกตัวหนึ่งชื่อ t และเราจะใช้ s ในการนับจำนวนคน !
ผู้ที่กล่าวจบเกมคือคนที่จะสับสวิทซ์ข้างเดียวตลอด (เลือกที่จะสับ s ตลอด) ขอเรียกคนๆนี้ว่า head

หลักการคือ ใครก็ตามยกเว้น head ที่เพิ่งเห็น s "ขึ้น" เป็นครั้งแรก ต้องกดลงเสมอ ไม่เช่นนั้น ให้ไปสับสวิตซ์ t แทน

เมื่อ head เข้าห้องแต่ละครั้งก็จะดูสถานะของ s หากครั้งก่อน head สับ s ขึ้น แต่เข้ามาแล้ว s มีสถานะลง
แสดงว่ามีน้องใหม่มาสับ s ; ก็สับ s ขึ้นไปตามหน้าที่ที่ต้องทำ และนับจำนวนน้องใหม่เพิ่ม
แต่หาก head เข้ามาแล้วสถานะยังเหมือนกับที่ตัวเองเพิ่งสับไปในครั้งก่อน ก็สับๆๆไปตามปกติ

head จะมั่นใจว่าทุกคนเข้าห้องมาแล้วเมื่อนับน้องใหม่ได้ครบ 19 คน (ไม่รวมตัวเอง)