|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
||||
|
||||
Pigeonhole Principle: Alternate Proof?
อยากรู้ว่า หลักรังนกพิราบนี่พิสูจน์เเบบอื่นนอกจาก contradictionได้มั้ยครับ
__________________
Mathematics is not about finding X but finding whY. |
#2
|
||||
|
||||
ใช้การอุปนัยเชิงคณิตศาสตร์ก็ได้ครับ โดยอุปนัยบนจำนวนรังของนกพิราบ เพื่อความสะดวกต่อไปนี้จะให้มีนก $b$ ตัว และรัง $n$ รัง
ให้ $P(n)$ แทนข้อความ "มีนก $b$ ตัว รัง $n$ รัง จะมีอย่างน้อย $1$ รัง ที่มีนกอย่างน้อย $\left\lceil\frac{b}{n}\right\rceil ตัว$" สำหรับ $n \in \mathbb{N}$ ขั้นฐาน $n=1$ ก็ค่อนข้างชัดเจนครับว่านกทุกตัวย่อมอยู่บนรังเดียวกัน นั่นคือ มีอย่างน้อย $1$ รัง ที่มีนก $b=\left\lceil\frac{b}{n}\right\rceil ตัว$ ขั้นอุปนัย สมมติว่า $P(k)$ เป็นจริง พิจารณาสำหรับ $k+1$ รัง $\ \ \ \ \ \ \ \ \ \ \ \ $กรณี $1$ รังที่ 1 มีนกอย่างน้อย $\left\lceil\frac{b}{k+1}\right\rceil ตัว$ ก็ได้เลยว่า $P(k+1)$ เป็นจริงเลยครับ $\ \ \ \ \ \ \ \ \ \ \ \ $กรณี $2$ รังที่ 1 มีนกอย่างมาก $\left\lceil\frac{b}{k+1}\right\rceil-1 $ ตัว จะได้ว่าเหลือนก $\ge b-(\left\lceil\frac{b}{k+1}\right\rceil -1)=b+1-\left\lceil\frac{b}{k+1}\right\rceil $ และรังอีก $k$ รัง โดย $P(k)$ เป็นจริง จะได้ว่ามีอย่างน้อย 1 รัง ที่มีนกอย่างน้อย $\left\lceil\frac{b+1-\left\lceil\frac{b}{k+1}\right\rceil }{k}\right\rceil $ ตัว ให้ $b=(k+1)q-r$ โดยที่ $q$ เป็นจำนวนเต็มบวก และ $r$ เป็นจำนวนเต็มบวกที่มีค่าตั้งแต่ $0$ ถึง $k$ จะได้ว่า \begin{align}\left\lceil\frac{b+1-\left\lceil\frac{b}{k+1}\right\rceil }{k}\right\rceil &=\left\lceil\frac{(k+1)q-r+1-q}{k}\right\rceil\\&=\left\lceil\frac{kq+1-r}{k}\right\rceil \\&= q\\&=\left\lceil\frac{b}{k+1}\right\rceil\end{align} ดังนั้น $P(k+1)$ เป็นจริง จบการพิสูจน์ครับ |
หัวข้อคล้ายคลึงกัน | ||||
หัวข้อ | ผู้ตั้งหัวข้อ | ห้อง | คำตอบ | ข้อความล่าสุด |
Pigeonhole | Pain 7th | คอมบินาทอริก | 11 | 11 กันยายน 2012 13:25 |
pigeonhole principle ครับ | extreme111 | คอมบินาทอริก | 6 | 26 มีนาคม 2012 16:52 |
Well ordering principle | Siren-Of-Step | ทฤษฎีจำนวน | 3 | 12 เมษายน 2010 19:11 |
ข้อสอบ Principle Math | ครูนะ | คณิตศาสตร์อุดมศึกษา | 2 | 16 มีนาคม 2009 05:47 |
The Pigeonhole Principle | Tony | ปัญหาคณิตศาสตร์ทั่วไป | 9 | 08 เมษายน 2005 22:38 |
|
|