Pigeonhole Principle: Alternate Proof?

[Panithi Vanasirikul]

อยากรู้ว่า หลักรังนกพิราบนี่พิสูจน์เเบบอื่นนอกจาก contradictionได้มั้ยครับ

[NaPrai]

ใช้การอุปนัยเชิงคณิตศาสตร์ก็ได้ครับ โดยอุปนัยบนจำนวนรังของนกพิราบ เพื่อความสะดวกต่อไปนี้จะให้มีนก $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)$ เป็นจริง

จบการพิสูจน์ครับ