creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 

ปั่นจักรยานชมเมือง


รูปที่เห็นคือแผนที่ถนนเชื่อมจุดท่องเที่ยวภายในเมือง 14 แห่ง เป็นไปได้หรือไม่ที่จะเดินทางผ่านทุกจุดจุดละ 1 ครั้ง?


ปัญหาข้อนี้แก้ได้ง่าย ๆ โดยใช้วิธีลงสี (coloring proof) ให้เราลงสีจุดที่อยู่ติดกันด้วยสีที่ต่างกัน จำนวนสีที่มากที่สุดที่เราใช้คือ 14 สี (เพราะมี 14 จุด) แต่จำนวนสีที่น้อยที่สุดเท่ากับเท่าไรนั้น เราต้องดูโครงสร้างของกราฟ ในที่นี้คือ 2 สี เพราะไม่มี 3 เมืองใดเชื่อมกันเป็นวง ขอใช้สีดำกับสีแดง ถ้าเราไม่เดินทางย้อนกลับเข้าจุดที่เพิ่งจากมา รูปแบบสีของจุดจะต้องสลับกัน ดำ-แดง-ดำ-แดง-... หรือ แดง-ดำ-แดง-ดำ... 14 เมืองจึงต้องมี 7 ดำ และ 7 แดง แต่จากรูปไม่ว่าเราจะลงสีอย่างไรก็ได้ 6 ดำ 8 แดง หรือ 6 แดง 8 ดำ ดังนั้นคำตอบคือเป็นไปไม่ได้ครับ










 

Create Date : 03 มีนาคม 2551    
Last Update : 3 มีนาคม 2551 14:17:43 น.
Counter : 1046 Pageviews.  

หมอดู


มีหมอดู 2 คน คนหนึ่งเป็นหมอดูลูกแก้ว ที่คิดค่าบริการ 7000 เยน ด้วยโอกาสถูก 70% กับอีกคนหนึ่งเป็นหมอดูไพ่ ที่คิดค่าบริการ 2000 เยน ด้วยโอกาสถูก 20%

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


ที่มา Sansuu Pazuru Dashiko Mondai Kessakusen (เชาวน์คณิตพิชิตเซียน) by Norio Nakada แปลโดย ดร.ธนารักษ์ ธีระมั่นคง และคณะ สำหรับ trick ในการตอบคำถามข้อนี้คือ ในเมื่อเรารู้โอกาสทายถูก โอกาสทายผิดที่ชัดเจน หมอดูที่มีโอกาสทายผิดสูง ก็ย่อมเป็นหมอดูที่แม่นเช่นเดียวกัน





 

Create Date : 28 กุมภาพันธ์ 2551    
Last Update : 28 กุมภาพันธ์ 2551 10:26:18 น.
Counter : 1316 Pageviews.  

famous FT pairs

ต่อไปนี้เป็นตัวอย่างคู่การแปลง Fourier ที่น่าสนใจ

h(t) คือ ฟังก์ชันใน time-domain
H(f) คือ Fourier transform ของ h(t) เป็นฟังก์ชั่นใน frequency-domain

1. Boxcar Function



2. Sinc Function



3. Constant Function



4. Dirac delta Function



5. Dirac comb/ train



6. Cosine Function



ขอให้สังเกตว่า FT ของ cosine ได้ delta function 2 ตัว แบบฟังก์ชันคู่และเป็นจำนวนจริง

7. Sine Function



ขอให้สังเกตว่า FT ของ Sine ได้ 2 delta functions เป็นลักษณะฟังก์ชั่นคี่และเป็นจำนวนจินตภาพ





 

Create Date : 13 กุมภาพันธ์ 2551    
Last Update : 13 กุมภาพันธ์ 2551 12:00:52 น.
Counter : 2142 Pageviews.  

พื้นที่ของ fudgeflake

fudgeflake เป็นรูปพื้นผิวระนาบ 2 มิติ เมื่อเราหมุนมัน 120 องศา หน้าตาของมันจะดูเหมือนเดิม (120 degree rotational symmetry) และเมื่อนำ fudgeflake 3 อันมาต่อกันในบางมุม จะต่อกันได้สนิทพอดี (ไม่มีช่องว่าง ไม่ซ้อนทับกัน) ดังรูป เกิดเป็น fudgeflake อันใหญ่ ซึ่งเจ้า fudgeflake อันใหญ่นี้ จะมีรูปทรงมุมเดียวกับ fudgeflake อันเล็กที่ถูกจับหมุนตามเข็มนาฬิกา 30 องศา


ถ้าระยะห่างระหว่างจุดกึ่งกลางของแต่ละ fudgeflake เท่ากับ 1 จงหาพื้นที่ของ fudgeflake อันเล็ก

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



จากนั้นถ้าเราเพิ่ม fudgeflake ชิ้นที่ 4 ต่อไปทางด้านบนของ 3 ชิ้นเดิม แล้วสร้างสามเหลี่ยมอีกรูปหนึ่งขึ้นมา



พื้นที่สามเหลี่ยมรูปบนสามารถเติมเต็มพื้นที่ว่างของ fudgeflake จากสามเหลี่ยมรูปล่างได้พอดี จบอย่างสวยงามครับ








 

Create Date : 12 กุมภาพันธ์ 2551    
Last Update : 12 กุมภาพันธ์ 2551 11:40:48 น.
Counter : 1169 Pageviews.  

โจรสลัดแบ่งสมบัติ (เกม)









โจรสลัด n คน แต่ละคนมีฐานะไม่เท่าเทียมกัน โจรสลัดหมายเลข 1 คือ กัปตัน หมายเลข 2 ผู้ช่วยกัปตัน หมายเลข 3 เป็นคนที่มีฐานะรองลงมา สุดท้ายหมายเลข n คือโจรสลัดลูกเรือที่กระจอกที่สุด โจรสลัดกลุ่มนี้ปล้นได้เหรียญทองจำนวน m เหรียญ (m>n) ต่อไปเป็นวาระการแบ่งสมบัติกัน

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

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

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


โจทย์ปัญหาข้อนี้เป็นแบบฝึกหัดสำหรับนักเรียนที่เรียนวิชาทฤษฎีเกม วิธีคิดให้เริ่มจากกลุ่ม n ที่น้อยที่สุด เริ่มต้นด้วยการสมมติว่ามี 2 คน คือคนที่ n-1 กับคนที่ n กรณีนี้ชัดเจน 100% ครับ คนที่ n-1 ฮุบเอาไว้ทั้ง m โดยไม่แบ่งให้คนที่ n เพราะตัวเองโหวตให้ตัวเอง ก็มีคะแนนเสียงครึ่งหนึ่งพอดี ข้อเสนอผ่าน คนที่ n ไม่สามารถโต้แย้งได้ เพราะฉะนั้นสูงสุดของคนที่ n คือ 0 เหรียญ ถ้าหากคนที่ n ปล่อยให้เหลือเพียง 2 คน

กรณี 3 คน คือ คนที่ n-2, n-1 กับ n คนที่ n-2 และคนที่ n ต่างรู้ดีว่าหากคนที่ n-2 ถูกกำจัดไป เหรียญทั้งหมดจะตกอยู่กับคนที่ n-1 (ตามเหตุผลกรณีที่เหลือ 2 คน) เหตุการณ์แบบนี้คนที่ n-2 สามารถซื้อตัวคนที่ n ได้ด้วยเหรียญ 1 เหรียญ แล้วตัวเองรับไป m-1 เหรียญ โดยไม่แบ่งให้คนที่ n-1 สักแดงเดียว ซึ่งคนที่ n ก็ต้องยอมรับ 1 เหรียญ ถ้าไม่รับ 1 เหรียญ ตัวเองก็จะไม่ได้อะไรเลย สำหรับคนที่ n-1 แม้ไม่ยอม ก็ไม่อาจทำอะไรได้ เกมดำเนินไปตามกติกา

กรณี 4 คน คือ คนที่ n-3, n-2, n-1 กับ n คนที่ n-3 และคนที่ n-1 ต่างรู้ว่า ถ้าหากกำจัดคนที่ n-3 ไป ทั้งคู่จะไม่ได้อะไรเลย (ตามเหตุผลกรณีมี 3 คน) ดังนั้นคนที่ n-3 จะเสนอเหรียญ 1 เหรียญให้คนที่ n-1 ส่วนตัวเองเก็บไว้ m-1 เหรียญ คนที่ n-2 และคนที่ n ไม่ได้อะไรเลย

ทำนองเดียวกัน คนที่ n-4 ต้องให้เหรียญกับคนที่ n-2 และ n คนละ 1 เหรียญ

ดังนั้น ถ้า n เป็นจำนวนคู่
ให้คนที่ 1 เอาเงินไป m - (n/2) + 1 เหรียญ
คนที่ 2, 4, 6, 8, ..., n เอาเงินไป 0 เหรียญ
คนที่ 3, 5, 7, 9, ..., n-1 เอาเงินไป 1 เหรียญ

ถ้า n เป็นจำนวนคี่
ให้คนที่ 1 เอาเงินไป m - [(n-1)/2] เหรียญ
คนที่ 2, 4, 6, 8, ..., n-1 เอาเงินไป 0 เหรียญ
คนที่ 3, 5, 7, 9, ..., n เอาเงินไป 1 เหรียญ





 

Create Date : 17 มกราคม 2551    
Last Update : 17 มกราคม 2551 14:10:18 น.
Counter : 3583 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.