creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
สามเหลี่ยมปาสคาล

มีอะไรหลายอย่างซุกซ่อนอยู่ในสามเหลี่ยมปาลคาล มันเริ่มจากโจทย์ข้อหนึ่งซึ่งมีคนโพสต์ไว้ทางอินเทอร์เนตในเว็บบอร์ดห้องหว้ากอของ pantip.com โหดใช้ได้เลยทีเดียวครับ ระหว่างที่คิดไปคิดมาอยู่เป็นชั่วโมงก็พบคุณสมบัติบางประการที่น่าสนใจของสามเหลี่ยมปาสคาล จึงนำมาเล่าสู่กันฟัง ขอเริ่มจากสามเหลี่ยมปาสคาลแล้วค่อยย้อนกลับไปหาโจทย์ก็แล้วกัน


ตอนเรียน ม. ต้น ม. ปลายคงนึกออกเพราะเราใช้มันช่วยหาสัมประสิทธ์ของการกระจาย (x + y)n ถ้าเรียกแถวที่เป็นยอดบนสุดของสามเหลี่ยมว่าแถวที่ n = 0 และแถวถัดมาว่า n = 1, 2, ... เรียงต่อไปเรื่อย ๆ แบบนี้ แถวที่ n = 4 ก็คือ 1 4 6 4 1 แล้วนำตัวเลขแต่ละแถวมาเรียงใหม่เป็น 3 แถว ดังนี้

n = 0; 1
1
0
0

n = 1; 1 1
1
1
0

n = 2; 1 2 1
1
2
1

n = 3; 1 3 3 1
1 1
3
3

n = 4; 1 4 6 4 1
1 4
4 1
6

n = 16;
1 560 8008 11440 1820 16
16 1820 11440 8008 560 1
120 4368 12870 120


จากการสังเกตเราพบว่า เมื่อเรียงแบบใหม่นี้แล้ว ถ้านำเลขแต่ละแถวมารวมกัน จะมี 2 แถวที่ได้ผลรวมเท่ากันเสมอ ผมขอเรียก 2 แถวนี้ว่าแถวพันธมิตรนะครับ ส่วนอีกแถวที่เหลือจะมีผลรวมน้อยกว่าหรือมากกว่าแถวพันธมิตรอยู่ 1 เสมอ ซึ่งผมขอเรียกว่าแถวโดดเดี่ยว (ใครจะลองนำไปพิสูจน์ดูก็ดีครับ ผลตรงนี้มาจากการสังเกตอย่างเดียว) เมื่อลองเขียนเล่น ๆ แบบนี้จนพบความสัมพันธ์ระหว่างแถวพันธมิตรกับแถวโดดเดี่ยวจึงเกิดคำถามขึ้นว่า เมื่อไรแถวโดดเดี่ยวจะมีผลรวมมากกว่าแถวพันธมิตรและเมื่อไรจะน้อยกว่า จากการสังเกตได้คำตอบว่ามันขึ้นอยู่ที่ค่า n ถ้า n = 3j หรือ n = 3j + 2 (เมื่อ j = 0, 1, 2, ...) แถวโดดเดี่ยวจะมากกว่าแถวพันธมิตรถ้า j เป็นจำนวนคู่ แต่จะน้อยกว่าถ้า j เป็นจำนวนคี่ และตรงกันข้ามถ้า n = 3j + 1 ตัวอย่างเช่น n = 6 เราเขียนเรียงใหม่

1 20 1
6 15
15 6

แถวพันธมิตรคือ 6 15 กับ 15 6 มีผลรวมเท่ากันเท่ากับ 21 ส่วนแถวโดดเดี่ยวคือ 1 20 1 มีผลรวมเท่ากับ 22 กรณีนี้ n = 3j เมื่อ j คือ 2 เป็นจำนวนคู่ ผลรวมแถวโดดเดี่ยวมากกว่าผลรวมแถวพันธมิตรอยู่ 1 คุณสมบัติที่น่าสนใจนี่แหละครับที่ช่วยหาคำตอบให้กับโจทย์ปัญหา combinatorics ที่กล่าวถึงในตอนแรกได้



สิ่งที่โจทย์ให้หาคือ C(2008,2) + C(2008,5) + C(2008,8) + ... + C(2008,2006) ขอเขียนแทนด้วย C3k+2 และเรารู้จากทฤษฎีการกระจายสัมประสิทธิทวินามว่า

C(2008,0) + C(2008,1) + C(2008,2) + ... + C(2008,2008) = 22008

สิ่งที่โจทย์ให้หาเป็นผลรวมของ subsequence หนึ่งใน 22008 อาจเขียนแทนด้วย

22008 = A3k + B3k+1 + C3k+2

เมื่อ

A3k = C(2008,0) + C(2008,3) + C(2008,6) + ... + C(2008,2007)
B3k+1 = C(2008,1) + C(2008,4) + C(2008,7) + ... + C(2008,2008)
C3k+2 = C(2008,2) + C(2008,5) + C(2008,8) + ... + C(2008,2006)

ตรงนี้มันก็คือการเขียนแถวที่ n = 2008 = 3(669) + 1 ของสามเหลี่ยมปาสคาล โดยมีแถว C3k+2 เป็นแถวโดดเดี่ยว และอยู่ในแบบ n = 3j + 1 เมื่อ j เป็นจำนวนคี่ หรือแถวโดดเดี่ยวมีผลรวมมากกว่าแถวพันธมิตรอยู่ 1 ดังนั้นถ้าเราให้แถวพันธมิตรมีผลรวมเท่ากับ x เราสามารถเขียนสมการง่าย ๆ ได้ว่า

22008 = x + x + x + 1

ได้ x = (22008 - 1)/3 หรือ C3k+2 = x + 1 = (22008 + 2)/3





Create Date : 25 เมษายน 2551
Last Update : 26 เมษายน 2551 13:48:28 น. 1 comments
Counter : 5969 Pageviews.

 
งงง อยู่ดีช่วยอธิบายด้วยครับ


โดย: my in love วันที่: 29 เมษายน 2551 เวลา:19:35:14 น.  

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.