Wednesday, November 17, 2004

WhichCoin: โปรแกรมแก้ปัญหาชั่ง n เหรียญ

Blog นี้ เป็นเรื่องราวต่อจาก ปัญหาชั่งก้อนหิน นั่งนึกดูดีๆ ก้อนหินขนาดพอดีๆกันคงไม่มี เปลี่ยนเป็นเหรียญน่าจะถูกต้องมากกว่า

ตอนที่แล้วจบที่ว่า ถ้าหากชั่ง k ครั้ง จำนวนเหรียญสูงสุดที่นำมาชั่งแล้วจะบอกได้ว่าเหรียญไหนมีน้ำหนักผิดปกติ และผิดปกติอย่างไร (หนักหรือเบา) คือ (3^k-1)/2 -1 เหรียญ แต่ไม่ได้พูดถึงว่าในหนังสือเขา คิดยังไง ?

เอามาสรุปใส่ BLOG สักครั้งก็ดี

การเขียนวิธีชั่ง

ยกตัวอย่างกรณีชั่งสองครั้ง จำนวนเหรียญ 3 เหรียญ วิธีชั่งอาจจะเขียนเป็นรูปแบบนี้

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

Trial #1
On  LEFT: 2  (1)
On RIGHT: 3  (1)
On TABLE: 1  (1)
------------------------
Trial #2
On  LEFT: 1  (1)
On RIGHT: 3  (1)
On TABLE: 2  (1)
------------------------
แล้วก็เอาผลการชั่งแต่ละครั้ง มาเปิดตารางตรวจผล
-L = HI 1
-R = LO 1
L- = HI 2
LL = LO 3
R- = LO 2
RR = HI 3
ในตาราง L คือเอียงซ้าย R คือเอียงขวา และ - คือไม่เอียง เช่น บรรทัดแรกบอกว่า ถ้าครั้งแรกไม่เอียง ครั้งที่สองเอียงซ้าย แสดงว่า เหรียญเบอร์ 1 หนัก (HI)

ในวิธีชั่งแบบเปิดตาราง จะเห็นว่า วิธีวางเหรียญในการชั่งครั้งที่สอง (1 อยู่ซ้าย 3 อยู่ขวา 2 อยู่บนโต๊ะ) จะไม่ขึ้นกับผลการชั่งครั้งแรกเลย คือ ไม่ว่าชั่งครั้งแรกจะออกมาเอียงเช่นใด ครั้งที่สองจะชั่งโดยวางแบบเดิม เพียงแต่ในภาพ อาจจะแทนเหรียญที่รู้แล้วว่าน้ำหนักปกติด้วย O จึงเห็นเป็น 1-O, O-3

ในกรณี 12 เหรียญ ก็เขียนแบบนี้ได้เหมือนกัน เช่น รูปวิธีชั่งนี้

เขียนเป็นตารางได้

Trial #1
On  LEFT: 7 9 10 11  (4)
On RIGHT: 3 5 8 12  (4)
On TABLE: 1 2 4 6  (4)
------------------------
Trial #2
On  LEFT: 1 3 9 12  (4)
On RIGHT: 4 6 8 10  (4)
On TABLE: 2 5 7 11  (4)
------------------------
Trial #3
On  LEFT: 2 5 6 11  (4)
On RIGHT: 3 4 8 10  (4)
On TABLE: 1 7 9 12  (4)
และจากผลการชั่ง เปิดตาราง
Results Lookup Table
--L = HI 2
--R = LO 2
-L- = HI 1
-LL = LO 4
-LR = LO 6
-R- = LO 1
-RL = HI 6
-RR = HI 4
L-- = HI 7
L-L = HI 11
L-R = LO 5
LL- = HI 9
LLL = LO 8
LR- = LO 12
LRL = LO 3
LRR = HI 10
R-- = LO 7
R-L = HI 5
R-R = LO 11
RL- = HI 12
RLL = LO 10
RLR = HI 3
RR- = LO 9
RRR = HI 8
รูปกับตาราง ก็คือ วิธีชั่งแบบเดียวกัน (ความจริงเอาข้อมูลจากตารางไปวาดรูป) การวางเหรียญในการชั่งครั้งที่ 2, 3 ไม่ได้ขึ้นกับผลการชั่งครั้งที่ 1, 2 ก่อนหน้าเลย เพียงแต่ในรูปจะวาดเหรียญที่รู้ว่ามีน้ำหนักปกติแล้ว ด้วย O และถ้าหากมี O ทั้งสองข้าง ก็เอาออกซะเป็นคู่ๆ ให้แลดูสะอาดตา เพราะไม่มีผลต่อผลการชั่ง

วิธีชั่ง คิดจากตาราง

ดูจากตารางดีๆจะเห็นว่า วิธีตรวจผลการชั่งจะตรงไปตรงมา เช่น ในตารางข้างบน สองบรรทัดแรกเขียนว่า

--L = HI 2
--R = LO 2
ก็เพราะว่าเหรียญเบอร์ 2 วางไว้บน โต๊ะ-โต๊ะ-ซ้าย ในการชั่งครั้งที่ 1-2-3 ตามลำดับ ถ้าผลออกมาตรงกับการวางนี้ คือ เป็น --L ย่อมแสดงว่า เบอร์ 2 หนักกว่าปกติ และหากสลับ L กับ R ในทุกหลักให้หมด เป็น --R ผลก็ย่อมเป็นตรงข้าม คือ เบอร์ 2 เบากว่าปกติ

ถ้าดูของเบอร์ 3 ก็จะเหมือนกัน คือ เบอร์ 3 หนักเมื่อผลการชั่งเป็น RLR และเบาเมื่อ LRL เพราะว่าเบอร์ 3 ถูกวางบนตาชั่งฝั่ง ขวา-ซ้าย-ขวา

สรุปแล้ว ถ้าหากกำหนดวิธีการขึ้นตาชั่งสำหรับแต่ละเหรียญให้แตกต่างกัน ก็จะสามารถแยกแยะจากผลการชั่งที่ออกมาได้ว่า เหรียญใด มีน้ำหนักผิดปกติ และผิดปกติอย่างไร โจทย์ที่ให้หาวิธีการชั่งสำหรับ n เหรียญใน k ครั้ง ก็กลายเป็นโจทย์ให้เลือกวิธีขึ้นตาชั่ง n แบบ จากจำนวนรูปแบบทั้งหมด 3^k แบบ โดยจำนวนเหรียญสูงสุดที่เลือกได้ หาได้จาก

  • ในการชั่ง k ครั้ง รูปแบบวิธีการขึ้นตาชั่งจะมีทั้งหมด 3^k แบบ คือ ---, --L, --R, -L-, -LL, -LR, ..., RRR

  • ตัดรูปแบบที่ไม่ขึ้นตาชั่งเลยออกไป --- (เนื่องจากถ้าไม่ขึ้น จะไม่รู้ว่าหนักหรือเบา) เหลือรูปแบบที่เลือกใช้ได้ 3^k-1

  • ในจำนวนนี้ มีรูปแบบที่เป็นส่วนกลับ L/R ของกันและกันอยู่ เช่น -LR กับ -RL ซึ่งรูปแบบที่เป็นส่วนกลับของกันและกันนี้ จะต้องกำหนดให้กับเหรียญเดียวกัน จะได้แยกแยะได้ว่า หนัก หรือ เบา กว่าปกติ ดังนั้นจึงเหลือจำนวนรูปแบบที่เลือกสำหรับเหรียญได้ (3^k-1)/2 รูปแบบ ซึ่งหารสองลงตัวเนื่องจาก 3^k เป็นเลขคี่แน่นอน

  • ในแต่ละรูปแบบ จะมี k หลัก ซึ่งแต่ละหลักจะแทนการชั่ง 1 ครั้ง (ซ้ายสุดหรือขวาสุดจะเป็นครั้งแรกก็แล้วแต่จะเลือก) ในแต่ละหลักจำเป็นที่จะต้องเลือกให้มีจำนวน L เท่ากับจำนวน R (มิฉะนั้นตาชั่งจะเอียงเพราะจำนวนเหรียญแต่ละข้างไม่เท่ากัน)

    ในจำนวน (3^k-1)/2 = (3^k-3)/2+1 รูปแบบที่เหลือ หากเอามาหาร 3 จะได้ (3^(k-1)-1)/2+(1/3) คือ ใน L, R, - จะมีสองอันที่นับได้ (3^(k-1)-1)/2 และอีกอันนับได้ (3^(k-1)-1)/2+1 เนื่องจาก --- ถูกลบออกไปในตอนต้น - จึงต้องน้อยกว่า L, R แน่นอน ดังนั้นที่เกินมา +1 จึงต้องเป็นของ L หรือ R เท่านั้น

    ตรงนี้เลยต้องเอารูปแบบออกไปอีก 1 เพื่อลดจำนวน L หรือ R สุดท้ายจะเหลือ (3^k-1)/2-1 รูปแบบ ที่จำนวน L เท่ากับ R ในทุกๆหลัก (ในการชั่งทุกครั้ง) และไม่เป็นส่วนกลับ L/R ของกันและกัน

    แปลว่าจำนวนเหรียญสูงสุดที่ชั่งได้ คือ (3^k-1)/2-1 เหรียญ

วิธีชั่ง n เหรียญ

ในหนังสือไม่พิสูจน์ว่าจะสามารถเลือก n รูปแบบออกมาได้จริง เลยลองทำโปรแกรมมาทดสอบดู ให้โปรแกรมลองเลือก n รูปแบบจาก 3^k ดูว่าจะหา n รูปแบบที่เหมาะสมได้ที่ทุก n จริงหรือเปล่า

โปรแกรม WhichCoin: WhichCoin.jar

เมื่อรันโปรแกรมแล้ว ป้อนจำนวน n โปรแกรมจะคำนวณหาค่าจำนวนครั้งที่ชั่ง k ที่เหมาะสม และเลือก n รูปแบบ ที่เหมาะสม พร้อมแสดงตารางวิธีการชั่ง และตารางตรวจสอบผลการชั่ง

จากนั้นหากกดปุ่ม "วาดภาพ" โปรแกรมจะวาดวิธีการชั่ง เช่น ในกรณี n=5

เนื่องจากคำตอบมิได้มีเพียงคำตอบเดียว หากดปุ่ม คำนวณ ไปเรื่อยๆ อาจจะได้คำตอบที่แตกต่างออกมาอีก เช่น

ซึ่งแสดงให้เห็นว่า ในการชั่งครั้งแรก ไม่จำเป็นต้องวางเหรียญให้มากที่สุดเสมอไป

ถ้า k>4 ...

ถ้า k เป็น 5 จำนวน n จะถูกเลือกมาจาก 3^5-1 = 242 รูปแบบ ซึ่งกินเวลามาก ยังไม่เคยรอจนโปรแกรมทำงานเสร็จสักที สูงสุดที่เคยลองคือ n=13 และ n=39 ของ k=4 ทั้งคู่

กรณี n=13

กรณี n=39 (คลิกบนภาพจะได้ภาพเต็ม)

เลือก n=13,39 จาก 3^4-1=80 ก็พยายามใส่ไบ้+Optimize ไปแยะแล้ว ของ k>=5 ไว้ค่อยๆคิดจะเลือกยังไงให้ฉลาดขึ้น

แก้ไขเพิ่มเติม

เอาภาพหน้าจอมาแปะ (ข้างบน)

1 comment:

apirak said...

ทำให้เหรียญน้ำหนักไม่เท่ากันนี่ยากกว่าก้อนหินอีกนะ