creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 

the game of Nim

นิมถือเป็นเกมที่สุดแห่งความยอดฮิตในการเกริ่นนำทฤษฎีเกม กติกาง่าย ๆ แบ่งเหรียญเป็น n กอง กองที่ i มีจำนวน xi เหรียญ ผู้เล่น 2 คนผลัดกันหยิบเหรียญออกคนละครั้ง ครั้งละกอง กองละกี่เหรียญก็ตามใจ ตั้งแต่ 0 ถึง xi (แต่ถ้าใครคิดจะหยิบ 0 เหรียญก็อย่าเล่นดีกว่าครับ ต่างฝ่ายต่างหยิบ 0 เหรียญก็นั่งมองตากันเท่านั้นเอง) ใครหยิบเหรียญสุดท้ายเป็นคนชนะ



เรามาวิเคราะห์แบบเบสิกกรณี n = 1 คือมีเหรียญกองเดียว จำนวน x1 เหรียญ คนเล่นก่อนก็หยิบมันทั้งกองคว้าชัยชนะไป กรณี n = 2 แต่ละกองมีเหรียญจำนวน x1 และ x2 ตามลำดับ เขียนแทนด้วย (x1,x2) ถ้า x1 ไม่เท่ากับ x2 คนแรกหยิบเหรียญเพื่อทำให้ x1 = x2 ซะ ก็จะชนะ ถูกมั้ยครับ สถานะ (x1,x1) แบบนี้เราเรียกสถานะ P คือสถานะที่หากผู้ใดเริ่มเล่นในสถานะนี้ย่อมแพ้ สถานะต่อไปถัดจาก P ต้องเป็น N เท่านั้น, N คือสถานะที่หากผู้ใดเริ่มเล่นในสถานะนี้ย่อมมีกลยุทธ์ที่นำไปสู่ชัยชนะ เพราะสถานะที่ต่อจาก N ต้องมีอย่างน้อย 1 สถานะที่เป็น P ฉะนั้นกลยุทธ์ของผู้เล่นเกมที่ได้เล่นในสถานะ N คือ เลือกทางเดิน (หรือเลือกหยิบเหรียญ) ที่ทำให้คู่ต่อสู้เผชิญหน้ากับสถานะ P อย่างเช่นในกรณี n = 2 ผู้เริ่มที่ (x1,x2) ต้องหยิบเหรียญเพื่อทำให้เป็น (x1,x1) หรือ (x2,x2) ก็จะชนะครับ กรณี n = 3 ก็ทำนองเดียวกัน คงมองออกได้ไม่ยากว่า (1,1,1) เป็น N หรือ (1,1,2), (1,1,3), (1,2,2) เหล่านี้ก็เป็น N เพราะมันสามารถหยิบแล้วทำให้เกิด (0,1,1), (1,1,0), (1,1,0) และ (0,2,2) ซึ่งเป็น P ได้ ตามลำดับ หรือสถานะ (1,2,3) เป็น P ไม่ว่าคนที่เล่นในสถานะนี้จะหยิบแบบใด สถานะถัดไปคือ N คำถามที่น่าสนใจคือ มันมีวิธีการทั่วไปใดจะตรวจสอบได้มั้ยว่า (x1,x2,x3) เป็น N หรือ P ?

มีครับ นั่นคือทฤษฎีของ Charles L. Bouton เขาว่า สถานะ (x1,x2,x3,...,xn) เป็น P ก็ต่อเมื่อ x1 x2 x3 ... xn = 0, เครื่องหมาย แทน bitwise XOR ในเลขฐาน 2 อาจเรียกว่า nim-sum (ใครที่เรียนดิจิทัลมาจะรู้ว่า มันก็คือการบวกเลขฐาน 2 บิตเดียวที่ไม่มี carry)

พิสูจน์ได้โดยกำหนดให้ P แทนเซ็ตสถานะทั้งหมดที่มี nim-sum เท่ากับศูนย์ และ N แทนเซ็ตสถานะอื่น ๆ ที่เหลือ เรารู้ว่า ณ สถานะสุดท้ายคือ (0,0,0,...,0) เป็น P หรือ 0 0 0 ... 0 = 0 และทุกสถานะที่อยู่ใน N ย่อมมีทางที่ไปสู่ P ทำได้โดยการเขียน (x1,x2,x3,...,xn) เป็นเลขฐาน 2 แล้วเปลี่ยน 1 เป็น 0 สำหรับ xi เพื่อทำให้ใน nim-sum เท่ากับ 0 ด้วยวิธีการนี้ xi* ที่เกิดจากการเปลี่ยนดังกล่าวจะมีค่าน้อยกว่า xi นั่นคือทุกสถานะใน N จะมีอย่างน้อยหนึ่งทางนำไปสู่สถานะใดสถานะหนึ่งใน P และจากสถานะใน P ทุกทางจะนำไปสู่สถานะใดสถานะหนึ่งใน N เพราะการเปลี่ยนจาก xi* ที่เป็น P ซึ่งมี x1 x2 x3 ... xi* ... xn = 0 ไปเป็น xi** ไม่สามารถทำให้ x1 x2 x3 ... xi** ... xn = 0 ได้ เนื่องจาก หากมันเท่ากับ 0 แล้ว xi* = xi** ซึ่งเป็นไปไม่ได้ครับ ดังนั้น (x1,x2,x3,...,xi**,...,xn) อยู่ใน N

เช่นเกมเริ่มต้นด้วยเหรียญ 3 กอง มีจำนวนกองละ 13 12 และ 8 ตามลำดับ เขียนแทน (13,12,8) ด้วยเลขฐาน 2

11012 = 13
11002 = 12
10002 = 8

nim-sum = 10012 = 9 มันเป็น N ดังนั้นผู้เล่นคนแรกทำให้เป็น P ได้โดยเปลี่ยน 11012 ให้เป็น 01002 หรือเปลี่ยน 11002 ให้เป็น 1012 หรือเปลี่ยน 10002 ให้เป็น 12 ซึ่งได้แก่การหยิบ 9 เหรียญออกจากกงอ 13 เหรียญ หรือหยิบ 7 เหรียญออกจากกอง 12 เหรียญ หรือหยิบ 7 เหรียญออกจากกอง 8 เหรียญตามลำดับ เลือก 1 ใน 3 แบบนี้ผู้เล่นคนแรกบังคับให้คู่ต่อสู้เผชิญหน้า P และพ่ายแพ้ในที่สุดครับ

พูดมาตั้งนาน สงสัยมั้ยครับ ทำไมเรียกเกมนิม นิมนี่ว่ากันว่า (อย่าเชื่อมากนะ) เริ่มแรกมาจากเกมหยิบหิน หรือ Jianshizi ของจีน ที่เรียก Nim อาจแผลงมาจาก Nimm! ซึ่งเป็น imperative รูป du ในภาษาเยอรมันจากอินฟินิทีฟ Nehmen แปลว่า take (ในภาษาอังกฤษโบราณเอง nim ก็แปลว่า take) ทั้งมีคนสังเกตว่าแอมบิแกรมของ NIM ก็คือ WIN





 

Create Date : 16 พฤษภาคม 2551    
Last Update : 17 พฤษภาคม 2551 10:09:32 น.
Counter : 2509 Pageviews.  

กลิ้งกับสไลด์ใครถึงก่อนกัน

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



การที่เค้าติดล้อไว้นี่เพื่อจะลดแรงเสียดทานจากการไถลนะครับ ถ้าผิวสัมผัสระหว่างอะลูมินั่มแนวตั้งกับรางไม้ไม่มี ส.ป.ส. ความเสียดทาน เราก็ไม่จำเป็นต้องติดล้อเล็ก ๆ นั่น คำถามนี้หากนำไปหลอกถามเด็ก ๆ อาจจะคิดว่ากลิ้งมาเร็วกว่า แต่ถ้ารู้ concept เรื่องพลังงานนิด ๆ หน่อย ๆ ระดับมัธยมปลายก็จะตอบว่าไถลลงมาเร็วกว่า หรืออาจจะตอบว่าถึงพื้นพร้อมกัน ที่สำคัญคือมองให้ออกว่าอะลูมินั่ม 2 ก้อนนั่นมันเคลื่อนที่ได้ยังไง คำตอบคือพลังงานครับ จุดที่ปล่อยมันมีพลังงานศักย์อยู่ และมันคงสภาพนั้นไม่ได้ถ้าไม่มีมามือจับ หลังจากปล่อยมือ พลังงานศักย์เปลี่ยนเป็นพลังงานจลน์ mv2/2 อะลูมินั่มทั้ง 2 ก้อนมีมวลเท่ากัน ก็น่าจะมีความเร็วเท่ากันมาถึงพร้อมกันสิ ถ้าคิดแบบนี้แสดงว่าเราลืมเรื่องการกลิ้งไป เพราะก้อนที่กลิ้งนั่นมันไม่ใช่แค่เคลื่อนที่ลงมา แต่มันยังหมุนกลิ้งด้วย มันเอาพลังงานจากไหนมากลิ้งล่ะ ก็ต้องเอามาจากพลังงานศักย์ตั้งต้นนั่นแหละครับ นั่นคือก้อนที่กลิ้งแย่งพลังงานส่วนหนึ่งมาทำให้กลิ้ง จึงมีพลังงานจลน์ลดลง สรุปพลังงานจลน์ของตัวกลิ้งถูกแบ่งเป็น 2 ส่วน คือ translational (mv2/2) กับ rotational (Iw2/2) สำหรับรูปทรงในข้อนี้พลังงานทั้งสองส่วนยังถูกแบ่งเท่า ๆ กันด้วยครับ





 

Create Date : 15 พฤษภาคม 2551    
Last Update : 15 พฤษภาคม 2551 16:40:13 น.
Counter : 971 Pageviews.  

เกมเปิดไพ่...ใครแพ้แก้ผ้า

เล่นไพ่ถ้าจะให้สนุกต้องมีเดิมพัน สมมติว่าเราเดิมพันแก้ผ้าก็แล้วกันนะครับ ภานุกับผมผลัดกันเปิดไพ่จากสำรับคนละใบ (ถ้าคุณนึกหน้าภานุไม่ออกก็ให้วาดตี๋น้อย หรือหมวยในดวงใจ เลือกเอาสักคน) ตามลำดับ คว่ำหน้าไพ่วางซ้อน โดยเริ่มเปิดจากบนลงล่าง และไพ่สลับอย่างสุ่ม ใครจะเป็นคนเริ่มก่อนดี สมมติว่าภานุไม่คิดอะไรมาก บอกว่าโอกาสมันก็ 50-50 เท่ากัน จริงเร๊อะ เสร็จผมละครับ เพราะผมจะฉวยโอกาสที่ภานุยังไม่ทันคิดอะไรนี่แหละขอให้เขาเริ่มก่อน ใครเจอ Ace เป็นคนแรกคนนั้นแก้ผ้า

คุณคิดว่าโอกาสที่ภานุแก้ผ้าเป็นเท่าไร ? จะเท่ากับ 50% มั้ย ?



เรามาดูกรณีเบสิกที่มี Ace เพียงใบเดียว จากไพ่ 4 ใบ ถ้าภานุแก้ผ้า เขาต้องเปิดเจอ ace ใบแรก ซึ่งมีโอกาส 1/4 หรือเปิดเจอ ace ใบที่ 3 มีโอกาสเท่ากับ โอกาสที่ภานุไม่เจอ ace ใบแรกและผมก็ไม่เจอ ace และภานุซวยในทีนั้น เท่ากับ (3/4)(2/3)(1/2) = 1/4 รวมแล้วโอกาสแก้ผ้าของภานุเท่ากับ 1/2 อย่างนั้นใครเปิดก่อนเปิดหลังก็ไม่สำคัญสิ เพราะโอกาสแก้ผ้ามีเท่ากัน... ถูกต้องครับ สำหรับกรณีที่มี ace แค่ใบเดียว ในกรณีไพ่ 52 ใบ การเล่นแบบนี้ มองอีกอย่างคือเราแบ่งไพ่ทั้ง 52 ใบออกเป็นคู่ ๆ ได้ 26 คู่ มันมีเพียงคู่เดียวที่มี ace อีก 25 คู่ไม่มีผลอะไร คู่ที่มี ace มี ace เพียงใบเดียว มันสลับกันได้แค่ 2 แบบ แบบหนึ่งผมโดน อีกแบบภานุโดน ดังนั้นโอกาสแก้ผ้า 50-50 เท่ากัน

ถ้ามี ace มากกว่า 1 ใบล่ะ เราลองคิดง่าย ๆ กรณีไพ่ 4 ใบ ที่มี ace 2 ใบ พานุเปิดก่อนมีโอกาสแก้ผ้า 1/2 ถ้าพานุรอดรอบนี้ผมเปิดต่อมีโอกาสแก้ผ้าเท่ากับโอกาสที่พานุรอดและโอกาสที่ผมพ่าย (1/2) x (2/3) = 1/3 ถ้าผมรอดรอบนี้รอบต่อไปพานุแก้ผ้าแน่นอนครับ เพราะเหลือ ไพ่ 2 ใบ และเหลือ ace 2 ตัว สรุปโอกาสพานุแก้ผ้าเท่ากับ 1/2 + (1/2)(1/3)(1) = 2/3 ในขณะที่ผมมีโอกาสแก้ผ้าเพียง 1/3 คงเริ่มเห็นภาพว่าเกมแบบนี้คนเปิดก่อนเสียเปรียบแล้วใช่มั้ยครับ

คิดแบบเดิม แบ่งไพ่ 52 ใบเป็นคู่ ๆ ได้ 26 คู่ การกระจายของ ace ทั้ง 4 ใบใน 26 คู่นั้นแบ่งได้เป็น 3 กรณี

กรณีที่ 1: ace จับคู่กัน 2 คู่ คือ AA AA

กรณีนี้ผมชนะได้ดูโชว์แน่นอน โอกาสเกิดกรณีนี้ เราสามารถคิดโดยมองว่ามีกล่องเปล่า 26 กล่อง เลือกมา 2 กล่อง ซึ่งเลือกได้ C(26,2) แบบ เพื่อใส่ ace กล่องละ 2 ใบ แต่ละแบบสลับที่กันได้ 4! ที่เหลืออีก 24 กล่องใส่ไพ่ที่เหลือ 48 ไป สลับกันได้ 48! ดังนั้นโอกาสเกิดกรณีนี้คือ C(26,2)4!48!/52! = 1/833

กรณีที่ 2: ace จับคู่กัน 1 คู่ คือ AA AX AX

กรณีนี้ถ้า AA มาก่อน AX ผมก็ได้ดูโชว์ แต่ถ้า AX มาก่อน AA ก็มีโอกาส 50-50 (เพราะมันอาจเป็น AX หรือ XA ก็ได้) คิดแบบเดิมครับ จาก 26 กล่อง เลือกมา 3 กล่อง ได้ C(26,3) แบบ แต่ละแบบใส่ ace 2 ใบลง 1 กล่อง ส่วนอีก 2 กล่องที่เหลือใส่กล่องละใบ สมมติว่ากล่องที่ 1 ใส่ 2 ใบ เลือกได้ C(4,2) แบบ กล่องที่ 2 และกล่องที่ 3 ใส่อย่างละ 1 ใบ เลือกได้ 2 แบบ และกล่องที่มี ace 2 ใบ ยังสลับกันได้อีก 2 แบบ แต่เราไม่จำเป็นต้องใส่กล่องที่ 1 ด้วย ace 2 ใบ เราอาจจะใส่กล่อง 2 หรือกล่อง 3 จำนวน 2 ใบก็ได้ สรุปแล้วเราใส่ ace ได้ 3x2x2C(4,2) วิธี ไพ่ที่เหลืออีก 48 ใบสลับใส่กล่องที่เหลือ 23 กล่องและที่ว่างที่เหลือในกล่องที่ใส่ ace 1 ใบ 2 กล่องได้ 48! แบบ อย่าลืมว่าในกล่องที่มี ace อยู่ 1 ใบยังสลับกันได้อีกกล่องละ 2 แบบ ดังนั้นโอกาสเกิดกรณีนี้คือ 3x2x2x2x2C(4,2)C(26,3)48!/52! = 96/833

โอกาสที่ AA มาก่อน AX คือ 1/3 ส่วนโอกาสที่ AX มาก่อน AA คือ 2/3 ในกรณีที่ AX มาก่อน AA ผมมีโอกาสชนะ 1/2 ดังนั้นโอกาสที่ผมได้ดูภานุแก้ผ้าในกรณีที่ 2 เท่ากับ 32/833 + 16/833 + 16/833 = 64/833

กรณีที่ 3: ace ไม่จับคู่กันเอง คือ AX AX AX AX

เลือก 4 กล่องจาก 26 กล่อง แต่ละกล่องใส่ ace 1 ใบ ace สลับกันได้ 4! วิธี ไพ่อีก 48 ใบที่เหลือสลับกันได้ 48! และกล่องที่มี ace ทั้ง 4 กล่องยังสลับกันได้อีกกล่องละ 2 แบบ (AX หรือ XA) ดังนั้นโอกาสเกิดกรณีที่ 3 เท่ากับ 4!C(26,4)x2x2x2x2x48!/52! = 736/833 และในกรณีนี้โอกาสที่ผมหรือภานุจะแพ้มีเท่า ๆ กัน คือ 368/833

เมื่อรวมทั้ง 3 กรณี โอกาสที่ผมหยิบไพ่ได้ ace หลังภานุเท่ากับ 1/833 + 64/833 + 368/833 = 433/833 หรือคิดเป็นประมาณ 51.98% ภานุจะกล้าเสี่ยงกับโอกาสแพ้ประมาณ 52% นี้มั้ยครับ แต่ที่แน่ ๆ ผมไม่กล้าเสี่ยงกับโอกาสชนะ 52% เว้นแต่ผมใส่เสื้อผ้าตุนไว้มากพอสำหรับเกมระยะยาว สมมติ เราทั้งคู่มีเสื้อผ้ารวมคนละ 4 ชิ้น โอกาสที่ภานุหมดตัวโดยผมถอด 2 ชิ้น มีเพียง (0.52)4(0.48)26!/4!2! = 0.25 หรือ 25% เท่านั้นเอง






 

Create Date : 14 พฤษภาคม 2551    
Last Update : 23 พฤษภาคม 2551 0:09:02 น.
Counter : 3290 Pageviews.  

impartial Game

เป็นเกมที่มีผู้เล่น 2 คน ทั้ง 2 คนต่างรู้ข้อมูลจำเป็นในการเล่นเกมเท่าเทียมกัน ผลัดกันเล่น มีคนเริ่มก่อน มีคนเล่นทีหลัง เกมแบบนี้เราสามารถเขียนเป็นกราฟได้ครับ โดยจุดของกราฟก็คือสถานะของเกม การเดินไปตามกติกาในเกมคือการเปลี่ยนจุดกราฟตามทิศทางของเส้นเชื่อม ส่วนมากผลแพ้ชนะกำหนดโดยใครจะเป็นผู้เล่นที่เล่นเกมในสถานะสุดท้าย ในที่นี้ขอกำหนดให้คนเล่นเกม ณ สถานะสุดท้าย (สถานะที่เคลื่อนต่อไปยังสถานะอื่นไม่ได้อีก) เป็นผู้แพ้ ตัวอย่างกราฟดังรูป สถานะสุดท้ายมีได้ 2 จุด



ถ้าเรากำหนดชื่อเรียกจุดใด ๆ ว่าเป็นจุด P (the previos player is to win) ก็ต่อเมื่อทุกจุดที่มันชี้เป็นจุด N (the next player is to win) หรือเป็นจุดสุดท้าย และเรียกจุดใด ๆ ว่าเป็นจุด N เมื่อมีบางจุดที่มันชี้เป็น P เราสามารถกำหนดกลยุทธ์เพื่อชัยชนะได้จากการดูจุด N-P นี่แหละครับ



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

แล้วในกรณีที่มีมากกว่า 1 เกมล่ะ เรารู้เฉพาะจุด N-P ของแต่ละเกมเพียงพอมั้ย ? เป็นโจทย์ที่นำไปสู่ทฤษฎีของ Sprague-Grundy ซึ่งเป็นการค้นพบของ R.P. Sprague (1935) กับ P.M. Grundy (1939) แยกกันนะครับ ไม่ได้ทำงานร่วมกัน ต่างคนต่างเสนอไอเดียคนละวาระกัน กรณีที่มากกว่า 1 เกมนี้หมายถึง แต่ละรอบ ผู้เล่นเลือกได้ว่าจะเล่นเกมไหน แล้วทำไปตามกติกาของเกมนั้น สมมติว่า 2 เกมคือ G1 กับ G2 ผลรวมของมัน G1 + G2 ถือเป็นอีกเกมหนึ่งต่างหาก ผู้ชนะคือผู้ที่ทำให้คู่ต่อสู้ไม่อาจเดินไปยังสถานะต่อไปได้อีกแล้ว (ติดอยู่ที่จุดสุดท้าย)

กราฟของเกม G1 + G2 มีลักษณะคล้ายกับกราฟที่เกิดจากผลคูณคาร์ทีเชียนของกราฟทั้งสอง ถ้า G1 = (V1,E1) และ G2 = (V2,E2) เกมที่รวม 2 เกมนี้แทนด้วย Gsum = (Vsum,Esum) เมื่อ

Vsum = V1 x V2
Esum = {(v1v2,w1v2)|(v1,w1 E1)} U {(v1v2, v1w2) | (v2, w2) E2}

การเล่นเกมที่รวมจากหลาย ๆ เกมแบบนี้รู้เฉพาะจุด N-P ไม่พอ แต่ต้องรู้ฟังก์ชัน Sprague-Grundy ด้วยครับ พูดง่าย ๆ ค่า Sprague-Grundy นี้ก็คือค่าจำนวนเต็มไม่ติดลบที่จะกำหนดให้กับจุด ที่จุด v ใด ๆ มีค่า Sprague-Grundy เท่ากับจำนวนเต็มไม่ติดลบที่น้อยที่สุดที่ไม่ใช่ค่า Sprague-Grundy ของจุดที่มันชี้ หรือหากจะพูดให้เป็นทางการ กำหนด N = {0,1,2,...} เมื่อ S N แล้ว mex (minimum excluded value) S ได้แก่สมาชิกใน N ที่มีค่าน้อยที่สุดที่ไม่เป็นสมาชิกของ S

mex S = min (N\S)

กราฟ G = (V,E) มีฟังก์ชั่น Sprague-Grundy g: V → N นิยามโดย

g(v) = mex {g(w) | (v, w) E}

ดังนั้นที่สถานะสุดท้าย (ใครเริ่มเล่นเกม ณ สถานะนี้เป็นคนแพ้) มีค่า g(v) = 0 ดูตัวอย่างดังรูป



คุณสมบัติที่น่าสนใจคือจุด P เป็นจุดที่ g(v) = 0 พิสูจน์ง่าย ๆ ครับ จุด P คือจุดที่ชี้ไปยังจุด N ในขณะที่จุด N ต้องมีอย่างน้อย 1 เส้นทางที่ชี้ไปยัง P ดังนั้นไม่มีจุด N ใด ๆ ที่มี g(v) = 0 เท่ากับทุก ๆ จุด P มี g(v) = 0

ที่น่าสนใจจริง ๆ คือ ถ้า G = G1 + G2 เป็นเกมที่รวม 2 เกม และ v = v1v2 เป็นจุดบน G แล้ว g(v) = g(v1) g(v2) เครื่องหมาย แทน XOR ในที่นี้เป็น bitwise ดังนั้นเราต้องเขียนมันเป็นเลขฐาน 2 ก่อน การทำ XOR ระหว่างบิตคือการดูความเหมือนหรือความต่างระหว่างบิต ถ้าเหมือนกัน เช่น 1 1 หรือ 0 0 จะได้ผลลัพธ์เป็น 0 แต่ถ้าต่างกัน เช่น 1 0 หรือ 0 1 จะได้ผลลัพธ์เป็น 1 เครื่องหมาย นี้บางทีก็เรียกมันว่า nim-sum ตัวอย่าง 3 5 = 0112 1012 = 1102 = 6 กล่าวคือจุด v1v2 ที่ g(v1) = g(v2) จะมี g(v1v2) = 0

ลองมาพิสูจน์ทฤษฎีที่อ้างว่า g(v1v2) = g(v1) g(v2) กันนะครับ (คุณอาจขยายเป็นกรณี n เกมใด ๆ ) เริ่มต้น จุด v = v1v2 และกำหนดให้ b = g(v1) g(v2) โดยเราจะแสดงว่าสำหรับ g(v1v2):

(1) ทุกจำนวนเต็มไม่ติดลบ a < b จะมีจุด x1x2 ที่ถูกชี้โดย v1v2 ที่มี g(x1x2) = a

(2) ไม่มีจุด x1x2 ที่ถูกชี้โดย v1v2 มี g(x1x2) เท่ากับ b

ในการแสดงตาม (1) ให้ d = a b และ k เท่ากับจำนวนหลักของ d เมื่อเขียนเป็นเลขฐาน 2 ดังนั้น 2k-1 ≤ d < 2k และ d มี 1 อยู่ตำแหน่งหลักที่ k (นับหลักที่ 1 จากทางขวามือ) เมื่อเรากำหนดให้ a < b และ b ก็ต้องมี 1 อยู่ตำแหน่งหลักที่ k ดังนั้น ณ ตำแหน่งเดียวกันของ a ต้องเป็น 0 และ g(v1) หรือ g(v2) ต้องมี 1 ตัว ที่ตำแหน่งหลักที่ k เป็น 1 (ส่วนอีกตัวก็ต้องเป็น 0) ไม่งั้น หลักที่ k ของ b จะไม่เป็น 1 สมมติว่า g(v1) มีหลักที่ k เป็น 1 ก็แล้วกันนะครับ ถ้าเราเอามันมา XOR กับ d มันจะมีค่าน้อยกว่าตัวมันเอง หรือเขียนว่า d g(v1) < g(v1) ดังนั้นย่อมมีทางเดินจาก v1 สู่ x1 ที่ g(x1) = d g(v1) เท่ากับว่าการเดินจากจุด v1v2 ไปยังจุด x1v2 เป็นการเดินที่เป็นไปได้ตามกติกา และ g(x1) g(v2) = d g(v1) g(v2) = d b = a

พิสูจน์ (2) โดยใช้ข้อขัดแย้ง กำหนดให้ v1v2 ชี้ไปยัง x1x2 ที่มี g(x1x2) = b สมมติให้ x1x2 คือ x1v2 และ g(x1) g(v2) = g(v1) g(v2) อย่างนี้ก็แปลว่า g(x1) = g(v1) นะสิ เกิดข้อขัดแย้งครับ เพราะต้องไม่มีจุดที่มีค่า Sprague-Grundy เท่ากันเชื่อมด้วย edge เดียวตามนิยาม

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





 

Create Date : 14 พฤษภาคม 2551    
Last Update : 17 พฤษภาคม 2551 10:30:01 น.
Counter : 1100 Pageviews.  

วาดกราฟ de Bruijn

กราฟ de Bruijn ที่ง่ายที่สุดมีจำนวนจุด (node) อยู่ในรูป 2n แต่ละจุด มี 2 เส้น (edges) ที่ออกจากมัน และมี 2 เส้น (edges) ที่เข้าหามัน ถ้าเขียนเลขตั้งแต่ 0 ถึง 2n-1 แทนแต่ละจุด ที่จุด x ใด ๆ มีเส้นพุ่งออกจากมันไปยังจุด 2x และ 2x+1 ยกเว้นในกรณีที่ 2x หรือ 2x+1 มากกว่า 2n-1 ก็ให้ลบด้วย 2n ทำแบบนี้เพื่อให้มันพุ่งไปยังจุดที่อยู่ในพิสัย 0 ถึง 2n-1 ดูตัวอยางรูปวาดกรณี n = 6 ผมนำมาจากบทความของ Herbert Taylor



หรือรูปวาดที่เจอบ่อยสไตล์ 2-pire กรณี n = 5



การประยุกต์ใช้งานสมบัติของกราฟนี้เราจะพบในวิชาเรียนจำพวก coding theory หรือในงาน electronic memory ครับ





 

Create Date : 13 พฤษภาคม 2551    
Last Update : 13 พฤษภาคม 2551 13:16:47 น.
Counter : 2028 Pageviews.  

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.