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

ปัญหา

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

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

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

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

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

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

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

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

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

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

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

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

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

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

คำใบ้

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

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

คำตอบ

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

switch มี 2 ตัว ให้ตัวหนึ่งชื่อ s อีกตัวหนึ่งชื่อ t และเราจะใช้ s ในการนับจำนวนคน !
ขอเรียกคนที่สับสวิตช์ได้ข้างเดียวตลอดว่า "head" โดยกำหนดให้ head สับเพียงสวิตช์ s เท่านั้น และ head นี่แหละคือผู้ที่จะนับจำนวนคน หากนับได้ครบ 19 คนแล้ว (ไม่รวมตัวเอง) head ก็จะเป็นคนประกาศว่า "ทุกคนเข้ามาในห้องครบแล้ว"

หลักการคือ นักโทษทุกคน (ยกเว้น head) เมื่อตนเข้ามาในห้องแล้วเห็น s "ขึ้น" เป็นครั้งแรก ต้องสับ s ลง (กล่าวคือ ทุกคนยกเว้น head จะมีสิทธิ์สับ s ได้ครั้งเดียว คือ สับ s ลงเมื่อตนเข้ามาแล้วเห็น s ขึ้นเป็นครั้งแรก) สำหรับกรณีอื่นๆ นั้น ให้ไปสับสวิตซ์ t แทน

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

หาก head นับน้องใหม่ได้ครบ 19 คน หรือพูดง่ายๆ คือนับ "จำนวนครั้งที่มีคนสับสวิตช์ s ลง" ได้ครบ 19 ครั้ง ก็เท่ากับนักโทษทั้ง 20 คนเคยเข้ามาในห้องแล้วนั่นเอง

แต่ทว่า ปัญหาคือ head จะไม่รู้ว่า ตนเข้ามาในห้องเป็นคนที่เท่าไร หาก head เข้ามาครั้งแรกแล้วเห็นสวิตช์ s "ลง" อยู่แล้ว ก็คิดได้ 2 กรณี
กรณีที่ 1 คือ สวิตช์ s ลงอยู่ตั้งแต่ต้นแล้ว (ตั้งแต่ก่อนนักโทษคนแรกมาเข้าห้อง) หากเป็นกรณีนี้ก็เท่ากับว่ายังไม่เคยมีใครสับสวิตช์ s ลง มาก่อน head จึงสามารถนับ "จำนวนครั้งที่มีคนสับสวิตช์ s ลง" จนครบ 19 ครั้งได้
กรณีที่ 2 คือ สวิตช์ s นั้น ตอนแรกสุดมันขึ้น แต่ก่อนหน้าที่ head จะเข้ามา มีนักโทษ 1 คน สับ s ลง โดยที่ไม่รู้ว่าตนได้เข้ามาก่อนหน้า head กรณีนี้ หลังจากครั้งนั้นนักโทษคนนั้นก็จะไม่สับสวิตช์ลงอีกเลย ทำให้ head สามารถนับ "จำนวนครั้งที่มีคนสับสวิตช์ s ลง" ได้เพียง 18 ครั้งเท่านั้น ซึ่ง head ก็จะไม่รู้ว่า ที่ตนนับได้ 18 นั้น เป็นเพราะมีนักโทษ 1 คนที่ยังไม่เคยเข้ามาในห้องเลยหรือเปล่า

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

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