creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 

คุณสมบัติของอัศวิน (Knight)

ผมเก็บมาเล่าจากบทความ The Mathematical Knight ของโปรเฟสเซอร์ n.d.e แห่ง harvard กับโปรเฟสเซอร์ r.p.s แห่ง mit พูดถึงการวิเคราะห์ endgame และคุณสมบัติพื้นฐาน (แต่มีความน่าสนใจอย่างยิ่งยวด) ของม้าหมากรุก หรืออัศวิน เริ่มจากรูปแบบดังรูป (สร้างโดย n.d.e)



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

ลองดูกรณีตัวอย่าง หากคิงขาวกินเบี้ย c2 อัศวินจะเดินไป d3 ดังรูป



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

1. Kc1 Nd3+
2. Kxc2 (ดูรูปที่ 2)
2. ... Nb4+
3. Kc1

ถึงทีที่ 3 นี้สภาพเป็นดังรูปที่ 3 ครับ



คงเห็นว่า ถ้าทีต่อไปขาวเป็นฝ่ายเดิน ย่อมแพ้ เพราะถูกบีบให้ออกจากสภาพที่กักคิงดำ แต่ทีต่อไปเป็นฝ่ายดำเดินย่อมเปิดโอกาสให้คิงขาวไปยัง c2 ถ้าคิงขาวสามารถเดินกลับไปกลับมาระหว่าง c1-c2 ได้โดยไม่ถูกรบกวนก็สามารถกักดำได้สำเร็จ และรูปเกมออกมาเสมอกัน คำถามคือ ม้าดำมีพื้นที่อีกมากมายทั้งกระดานให้หาเส้นทาง เป็นไปได้มั้ยที่มันจะเดินกลับมาบีบคิงขาว ตอนนี้จุดตั้งต้นของเราคือม้าอยู่ ณ b4 ส่วนคิงขาวอยู่ c1 (รูปที่ 3) ดำเดินก่อน มีขาวจะออสซิลเลตอยู่ระหว่าง c1 กับ c2 โดยอยู่จะอยู่ช่อง c1 เมื่อเดินทีที่เป็นจำนวนคู่ และอยู่ช่อง c2 เมื่อเดินทีที่เป็นจำนวนคี่ หากมีหนทางให้ม้าไปอยู่ยัง d3 ในทีที่เป็นจำนวนคู่ก็จะบีบคิงขาวได้ครับ ซึ่งตำแหน่ง d3 นี้สมมูลกันกับตำแหน่ง b3 และ e2 เพราะทั้ง 3 ช่องนี้กันคิงขาวไม่ให้เดินไปยัง c1 และแต่ละช่องเดินถึงกันได้ใน 2 หรือจำนวนคู่ที

เพื่อแก้ปัญหาดังกล่าวเราให้ม้าดำเดินไปยังตำแหน่งใด ๆ ใช้ m ที แล้วเดินกลับมายัง d3 ใช้ n ที ถ้า m+n เป็นจำนวนคู่ ดำชนะ เรามองกระดานหมากรุก 8 x 8 เป็นกราฟ G8,8 โดย vertices คือช่องทั้ง 64 ช่อง จึงมี 64 จุด และ edges คือเซ็ตของเส้นเชื่อมช่องหมากรุกในรูปแบบการเดินของม้า สามารถพิสูจน์ได้ไม่ยากว่า G8,8 เป็น connected graph เป็นกราฟที่จากจุดใด ๆ สามารถมีเส้นเชื่อมไปยังจุดอื่น ๆ ได้ทุกจุด และ G8,8 เป็น bipartite คือเซ็ตของจุดช่องดำ กับเซ็ตของจุดช่องขาว (Bipartite graph คือกราฟที่จุดสามารถแบ่งออกได้เป็น 2 กลุ่มที่ไม่มีสมาชิกร่วมกัน และทุก edge เชื่อมระหว่างจุดที่มาจากคนละกลุ่มกัน) พิสูจน์ได้จากเงื่อนไขของ edge ที่บอกว่าเป็นเส้นเชื่อมช่องทางเดินของม้า ทุกครั้งที่ม้าเดินจะเปลี่ยนสีช่องที่มันยืน เมื่อ G8,8 เป็น bipartite การเดินเป็นวงกลับมาสู่สีเดิมของมันจึงไม่มีวงเลขคี่ หรือการเดินไปสู่จุดที่อยู่คนละกลุ่มกัน (คนละช่องสี) ไม่มีวงที่เป็นเลขคู่ ดังนั้น m+n เป็นจำนวนคี่เสมอครับ นั่นหมายความว่าเกมนี้ม้าไม่สามารถบีบบังคับคิงจากการเดินกลับไปกลับมาระหว่าง c1 กับ c2 ได้ เสมอกันครับ






 

Create Date : 12 พฤษภาคม 2551    
Last Update : 12 พฤษภาคม 2551 14:13:23 น.
Counter : 1326 Pageviews.  

เท่ากันเพราะเหตุใด


ข้อนี้เป็นโจทย์จากเว็บของโปรเฟสเซอร์ n.d.e แกเล่าถึงตอนไปคอนเฟอเร็นซ์เดือนธันวาคม 2003 ที่ SASTRA University อินเดีย จากนิทรรศการซึ่งจัดขึ้นที่พิพิธภัณฑ์รามานุจัน Prof. n.d.e ขยายผลเป็นโจทย์ว่า แต่ละคู่ในกลุ่มต่อไปนี้เท่ากันเพราะเหตุใด นอกเหนือจากการมีผลรวมที่เท่ากัน

(3, 3, 12) = (1, 8, 9)
(4, 8, 9, 21) = (3, 7, 14, 18)
(4, 7, 21, 36) = (1, 12, 27, 28)
(5, 7, 10, 14, 27) = (3, 6, 15, 18, 21)
(5, 85, 85, 169, 425) = (13, 17, 125, 289, 325)
(17, 21, 24, 48, 54, 238) = (3, 4, 14, 119, 126, 136)

ตัวอย่างการค้นพบของรามานุจันก็คือ (3, 3, 12) = (1, 8, 9) ผลรวม 3 + 3 + 12 = 18 = 1 + 8 + 9 และ 33 x 33 x 1212 = 6,499,837,226,778,624 = 11 x 88 x 99 น่าสนใจดีใช่มั้ยครับ ลองดูว่ามีข้อสังเกตอะไรบ้าง 3 x 3 x 12 = 36 และ 1 x 8 x 9 = 72 ทั้งสองจำนวนมีจำนวนเฉพาะที่เป็นตัวประกอบเหมือนกันคือ 2 กับ 3 ในกรณีคู่ 4 x 8 x 9 x 21 = 6048 และ 3 x 7 x 14 x 18 = 5292 จำนวนเฉพาะที่เป็นตัวประกอบของทั้งคู่คือ 2, 3, 7 ดังนั้นจะตอบว่าผลคูณของแต่ละกลุ่มมีจำนวนเฉพาะเป็นตัวประกอบเหมือนกันก็โอเคครับ แต่สิ่งที่เท่ากันอย่างสวยงามนั้นคือผลคูณของ xx

33 33 1212 = 11 88 99
44 88 99 2121 = 33 77 1414 1818
44 77 2121 3636 = 11 1212 2727 2828
55 77 1010 1414 2727 = 33 66 1515 1818 2121
55 8585 8585 169169 425425 = 1313 1717 125125 289289 325325
1717 2121 2424 4848 5454 238238 = 33 44 1414 119119 126126 136136

ยังมีอะไรนี่น่าตื่นเต้นกว่านั้นอีกนิด คู่ (5,27,28,70) = (6,15,49,60), (1,6,8,20,30) = (2,2,12,24,25), และ (3,21,21,25,63) = (5,7,27,45,49) อันหลังนี่เป็นจำนวนคี่ทั้งหมดเลยนะ นอกจากจะมีผลรวมเท่ากัน ผลคูณของ xx เท่ากันแล้ว ผลคูณของมันยังเท่ากันด้วยครับ





 

Create Date : 08 พฤษภาคม 2551    
Last Update : 8 พฤษภาคม 2551 13:57:23 น.
Counter : 909 Pageviews.  

ปัญหาการจัดกลุ่มโหวต

สมมติว่าจะมีการเลือกตั้งเลือกประธานาธิบดีในประเทศ x ซึ่งมีประชากร 20 ล้านเสียง โดยประธานาธิบดีคนปัจจุบัน y มีเสียงสนับสนุนจากประชาชนไม่ถึง 1 เปอร์เซ็นต์ ส่วนเสียงที่เหลือสนับสนุน z คู่แข่งคนสำคัญที่ลงชิงชัยในการเลือกตั้งครั้งหน้า

y ต้องการเป็นประธานาธิบดีอีกครับ (แน่นอนว่าตามแบบวิถีประชาธิปไตย - ใช้เสียงของประชาชนส่วนใหญ่เป็นตัวแทน...มั้ง) เธอก็คิดอะไรขึ้นมาได้อย่างหนึ่ง โดยเริ่มจากแบ่งเสียง 20 ล้านเสียงซึ่งมีสิทธิโหวตออกเป็น n1 กลุ่ม แต่ละกลุ่มมีคนเท่า ๆ กัน จากนั้นแบ่งคนจากแต่ละกลุ่มออกเป็น n2 กลุ่มย่อย แต่ละกลุ่มย่อยก็มีคนเท่า ๆ กัน และแบ่งแต่ละกลุ่มย่อยออกเป็น n3 กลุ่มย่อยลงไปอีก แบ่งย่อย ๆ แบบนี้ไปเรื่อย ๆ นะครับ โดยกลุ่มย่อยในอันดับที่ i ก็ใช้เสียงข้างมากเป็นตัวแทนกลุ่ม เพื่อเป็นตัวแทนโหวตในอันดับที่ i-1 (ถ้ามีคะแนนเสียงเท่ากันในแต่ละโหวต คุณ y เธอประกาศว่ายอมถือว่าตัวเองแพ้ z ในโหวตนั้น)

คำถามคือ ด้วยวิธีการนี้ y สามารถแบ่งกลุ่ม และกระจายเสียงที่สนับสนุนหล่อน เพื่อเอาชัยในการเลือกตั้งได้มั้ยครับ



โจทย์ข้อนี้เป็นปัญหาคลาสสิกยอดฮิตอีกข้อหนึ่งซึ่งมีคนเขียนเฉลยไว้หลายแบบ แบบหนึ่งที่ตรงไปตรงมา คือ ให้ N เป็นผลคูณของ non-trivial factor

N = Nk = n1 x n2 x n3 x ... x nk

ให้ mi = (ni/2) + 1

จำนวนผู้สนับสนุน Mk = m1 x m2 x m3 x ... x mk ก็เพียงพอให้ชนะการเลือกตั้ง พูดง่าย ๆ คือเราแบ่งคนออกเป็น Nk-1 กลุ่ม แต่ละกลุ่มมีขนาด nk แล้วแบ่งผู้สนับสนุนเป็น Mk-1 กลุ่ม กลุ่มละ mk ก็จะชนะโดยการเหนี่ยวนำขึ้นมาจากระดับ i สู่ i-1 ตัวอย่างตัวเลขจริง 20 ล้าน = 57 x 44 สามารถถูกเหนี่ยวนำโดย 37 x 34 = 177147 ซึ่งน้อยกว่า 1%





 

Create Date : 03 พฤษภาคม 2551    
Last Update : 3 พฤษภาคม 2551 23:30:04 น.
Counter : 912 Pageviews.  

koch Snowflake

เป็นอีกหนึ่ง fractal ติดอันดับฮิต ที่พ่วงคุณสมบัติอะเมซซิ่งข้อหนึ่งคือ มันเป็นรูปทรงที่มีเส้นรอบรูปอนันต์แต่กลับมีพื้นที่จำกัด เราเริ่มจากวิธีสร้างกันก่อนนะครับ

(1) วาดสามเหลี่ยมด้านเท่า



(2) แบ่งแต่ละด้านออกเป็น 3 ส่วนเท่า ๆ กัน แล้วแทนที่ส่วนกลางของแต่ละด้าน ด้วยเส้น 2 เส้นที่มีความยาวเท่ากับเส้นที่ลบทิ้งไป (มันก็คือแตกหน่อ 2 ด้านของสามเหลี่ยมด้านเท่าที่มีความยาวด้านเท่ากับด้านที่ลบทิ้งไป)



(3) ย้อนกลับไปทำ (2) ซ้ำอนันต์ครั้ง ผลที่ได้จากการวนทำ 2 ครั้ง 3 ครั้ง และ 4 ครั้งแสดงดังรูปด้านล่างนี้



เราลองมาดูความยาวเส้นรอบรูปกันนะครับ เนื่องจากมันตั้งต้นด้วยสามเหลี่ยมด้านเท่า เราจึงพิจารณาเพียงด้านเดียวพอ กำหนดให้ด้านยาว L




มีความยาวเท่ากับ L



มี 4 ส่วนแต่ละส่วนยาว L/3 ดังนั้นความยาวรวมเท่ากับ (4/3)L



แต่ละส่วนทั้ง 4 ส่วนในรอบที่แล้วมี 4 ส่วน แต่ละส่วนยาว (L/3)/3 ดังนั้นความยาวรวมเท่ากับ (4/3)2L



ถ้าเราวนตามขั้นตอนดังกล่าว n รอบ จะได้ความยาวรวม (4/3)nL ซึ่งเห็นชัดเจนว่าเมื่อ n เข้าสู่อนันต์ ลำดับนี้ก็มีค่าเข้าสู่อนันต์ นั่นหมายความว่าเส้นรอบรูปเกร็ดหิมะ Koch มีความยาวเป็นอนันต์

ดูพื้นที่ ถ้าให้สามเหลี่ยมตั้งต้นมีพื้นที่เท่ากับ A ในการทำรอบแรกเราได้ พ.ท. เพิ่มขึ้นอีกเนื่องจากมีสามเหลี่ยมเล็ก ๆ งอกจาก A อีก 3 รูป จากความรู้เรขาคณิต (พ.ท. สามเหลี่ยมด้านเท่ายาวด้านละ x)2 เท่ากับ 3x4/16 หรือ พ.ท. แปรตาม x2 ถ้าความยาวด้านของสามเหลี่ยมลดลง 3 เท่า พื้นที่จะลดลง 9 เท่า ดังนั้นสามเหลี่ยมที่งอกมาอีก 3 รูปแต่ละรูปมี พ.ท. A/9 เมื่อวนลูปสร้างรอบที่ 2 จะมีสามเหลี่ยมเล็ก ๆ งอกเพิ่มขึ้นมาอีก 3 x 4 = 12 ลูก แต่ละลูกมี พ.ท. A/92 เมื่อวนลูปสร้างรอบที่ 3 จะมีสามเหลี่ยมเล็ก ๆ งอกเพิ่มขึ้นมาอีก 12 x 4 = 48 ลูก แต่ละลูกมี พ.ท. A/93 เมื่อวนลูปสร้างรอบที่ n จะมีสามเหลี่ยมเล็กๆ งอกเพิ่มขึ้นมาอีก 3(4)n-1 ลูก แต่ละลูกมี พ.ท. A/9n หรือมีพื้นที่รวมเท่ากับ A + 3A/9 + 3(4)A/92 + 3(4)2A/93 + ... + 3(4)n-1A/9n = S(n)

หรือหา S(n) เมื่อ n เป็นอนันต์ได้

S = A[1 + (1/3)(1+(4/9) + (4/9)2 + (4/9)3 + (4/9)4 + ...)] = 8A/5

น่าอัศจรรย์ดีใช่มั้ยครับ เส้นรอบรูปยาวเป็นอนันต์แต่มีพื้นที่จำกัด






 

Create Date : 02 พฤษภาคม 2551    
Last Update : 6 กรกฎาคม 2551 17:19:51 น.
Counter : 1800 Pageviews.  

sierpinski Triangle

สามเหลี่ยม Sierpinski เป็น fractal ยอดนิยมรูปหนึ่งซึ่งมักนำมายกตัวอย่างอธิบายการสร้างรูปทรงที่ซับซ้อนจากรูปทรงเรขาคณิตพื้นฐาน โดยเริ่มจากสามเหลี่ยมด้านเท่า (1) เราเชื่อมจุดกึ่งกลางของสามเหลี่ยมด้านเท่าทั้ง 3 ด้านเข้าด้วยกัน เราจะได้สามเหลี่ยมด้านเท่าที่มีขนาดเล็ก 4 รูป



(2) กำจัดสามเหลี่ยมตรงกลางทิ้ง



(3) ย้อนกลับไปเริ่มทำซ้ำตั้งแต่ (1) สำหรับสามเหลี่ยมทุกรูป ตัวอย่างผลที่ได้จากการวนลูปครั้งที่ 2 - 4 แสดงดังนี้







 

Create Date : 02 พฤษภาคม 2551    
Last Update : 2 พฤษภาคม 2551 15:15:05 น.
Counter : 1876 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.