PANTIP.COM : X6825841 แก้ปัญหา 12 เหรียญ ชั่ง 3 ครั้ง ด้วย Information Coding{แตกประเด็นจาก X6825146} [คณิตศาสตร์]

ความคิดเห็นที่ 4

(โพสต์ซ้ำกับคห 12 ของกระทู้ X6825146)

สมมติว่าถ้าโจทย์ไม่สนว่าลูกที่แตกต่างหนักกว่าหรือเบากว่า
ที่ต้องการคือให้ระบุให้ได้ว่าลูกใดกันแน่ที่ผิดปกติ
แล้วถ้าคุณมีลูกหิน 13 ก้อนล่ะ คุณต้องใช้กี่ครั้ง
.
.
.
คำตอบคือ 3 ครั้งเหมือนกัน

เรื่องลูกหิน 12 ก้อนนี้ เป็นคำถามที่เก่ามากจริง ๆ
ผมมีเกร็ดเล็ก ๆ จะเล่าให้ฟัง
คือผมโดนเพื่อนที่ชอบอะไรทำนองนี้ถามเอาเมื่อสัก 20 ปีที่แล้ว
เล่นเอาเพื่อนทั้งฝูงมึนตึ้บ เพราะมันคิดในใจไม่ไหว
ที่สำคัญตอนนั้นเจ้าเพื่อนตัวดีมันแกล้งถามผิด
เพราะมันให้หาว่าลูกไหนผิดปกติ แต่บอกว่ามีลูกหินอยู่ทั้งหมด 13 ลูก
แล้วให้ชั่งได้แค่ 3 ครั้ง ทำยังไง เล่นเอาผมหัวปั่นไป 3-4 ชั่วโมง

จำได้ว่าโดนถามประมาณบ่าย 3 คิดที่คณะฯ ไม่ออก ต่อที่บ้าน
คิดออกก่อนสองทุ่มนิดหน่อย โดยมี decision tree วุ่นวายพอควร
วันต่อมา เจอกันอีก ยังไม่มีใครในก๊วนคิดออกเลย มีแต่ผม
ไอ้เพื่อนตัวดีมันไม่เชื่อ (เพราะไอ้ที่มันจำมาน่ะแค่ 12 ลูก) บอกให้เฉลย
ผมไม่ยอมบอกให้มันเฉลยก่อน ไอ้เพื่อนตัวดีเลยเฉลย ซึ่งเป็นวิธีที่ดูง่ายดีจริง
(ทุกวันนี้ ผมก็ยังชอบวิธีของมันอยู่นะ เพราะคิดตามง่ายกว่า)
คือ ให้แบ่งหินเป็น 3 กอง กองละ 4 ลูก เรียกว่ากอง A, B, C แล้วกัน
ชั่ง #1 ให้ชั่งกอง A กับ B
จากนั้นให้ย้าย 3 ก้อนจากกอง A ไป B, 3 ก้อนจาก B ไป C, 3 ก้อนจาก C ไป A
ชั่ง #2 ให้ชั่ง Accc กับ Baaa
ถ้าทั้งสองครั้งแรกผลเหมือนกัน (คือถ้าเอียงก็เอียงเหมือนกัน ถ้าไม่เอียงก็ไม่เอียงเหมือนกัน)
ก็แปลว่าลูกเจ้าปัญหาอยู่ในหนึ่งในสามที่ไม่ได้ถูกย้าย ชั่งอีกทีก็รู้
ถ้าทั้งสองครั้งแรกผลต่างกัน ก็แปลว่าลูกเจ้าปัญหาอยู่ในหนึ่งในสามก้อนที่ย้ายไป
จะอยู่กองไหน คิดสักหน่อยก็รู้ ทีนี้ชั่งอีกทีก็เสร็จ

เพื่อน ๆ ก็อืมม์ มีแต่ผมแหละที่ท้วงว่า เฮ้ย! ที่ถามเมื่อวานมัน 13 ลูกนี่หว่า
พอผมเฉลย มันก็เลยอึ้งบ้าง
(คิดเองนะ ขี้เกียจเฉลย ถ้าคุณแก้ 12 ลูกได้ 13 ลูกก็ไม่ยากหรอกครับ)

เย็นวันนั้น ผมเลยได้สูตรของผมเอง (3^(n-1))+1
ซึ่งจะเป็นจำนวนลูกหินที่มากที่สุดที่ใช้การชั่ง n ครั้ง แก้ปัญหาได้

หลายปีต่อมา ผมไปเจอปัญหาลูกหิน 12 ลูก อีกครั้งใน booklet เล่มเล็ก ๆ
ที่แถมมากับหนังสือของ Reader's Digest เรียกว่าเหมือนเป๊ะ

ผมลืมเรื่องนี้ไปนานแล้วครับ ไม่ทราบว่ากลับมาฮิตอีก
จนถูกถามคำถามนี้อีก ในงานเลี้ยงรุ่นปลายปีที่แล้ว โดยรุ่นพี่คนหนึ่ง
ซึ่งเข้าใจว่าคลั่งไคล้อะไรทำนองนี้อยู่เหมือนกัน โดยบังคับว่าให้ชั่งได้แค่ 2 ครั้ง
ผมเลยบอกแกไปว่่า 12 ลูกต้องใช้ 3 ครั้งครับ ถ้า 2 ครั้งก็ได้แค่ 4 ลูก
(แกยังไม่เชื่อ อีกวันถึงโทรมาขอโทษผม ซึ่งที่จริงก็ไม่ได้ติดใจอะไร)

วันนี้เลยได้อีกสูตร (3^n-3)/2 ของคุณโจโจ้
เพราะโจทย์นั้น ต่างกันอยู่เล็กน้อย ก็ขอขอบคุณครับ

สงสัยจะเขียนยาวกว่าที่ตั้งใจอยู่สักหน่อย แต่ก็คิดว่าคงมีประโยชน์อยู่บ้างนะครับ

จากคุณ : ลุงแว่นใจดี - [ 24 ก.ค. 51 04:43:20 A:202.91.18.194 X: ]