หลักรังนกพิราบทั้งสามแบบ

[Chairote]

ผมมีข้อสงสัยในเรื่องนี้นิดหน่อยครับ ผมเข้าใจว่าหลักรังนกพิราบนั้นมีทั้งหมดสามแบบดังนี้

แบบที่หนึ่ง
ถ้ามีนก $n+1$ ตัวบินเข้ารัง $n$ รัง แล้วมีรังนกอย่างน้อยหนึ่งรังที่มีนกอย่างน้อยสองตัว

แบบที่สอง
ให้ $m,n$ เป็นจำนวนเต็มบวกและ $n > m$
ถ้ามีนก $n$ ตัวบินเข้ารัง $m$ รัง แล้วมีรังนกอย่างน้อยหนึ่งรังที่มีนกอย่างน้อยสองตัว

แบบที่สาม
ให้ $m,n$ เป็นจำนวนเต็มบวกและ $n > m$
ถ้ามีนก $n$ ตัวบินเข้ารัง $m$ รัง แล้วมีรังนกอย่างน้อยหนึ่งรังที่มีนกอย่างน้อย $\left\lfloor\,\dfrac{n}{m}\right\rfloor + 1$ ตัว

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

หากใครเข้าใจหลักการนี้อย่างแจ่มแจ้ง ช่วยอธิบายหน่อยครับ

[nongtum]

แบบที่สามเป็นกรณีทั่วไปกว่ากรณีที่สองครับ
เช่น วางเหรียญ 16 เหรียญ ลงในกล่อง 3 ใบ โดยเงื่อนไขแบบที่สามจะบอกได้ว่ามีกล่องใบหนึ่งมีเหรียญอย่างน้อยหกเหรียญ ซึ่งเป็นไปตามแบบที่สองด้วย

[PP_nine]

แบบที่สาม
ให้ $m,n$ เป็นจำนวนเต็มบวกและ $n > m$
ถ้ามีนก $n$ ตัวบินเข้ารัง $m$ รัง แล้วมีรังนกอย่างน้อยหนึ่งรังที่มีนกอย่างน้อย $\left[\dfrac{n}{m}\right]+1$ ตัว

น่าจะมีการเข้าใจผิดว่า $\left\lfloor\, x\right\rfloor +1 = \left\lceil\, x \right\rceil $ ล่ะมั้งครับ

เพราะลองให้ $x$ เป็นจำนวนเต็ม สมการนี้จะผิดทันที

อันที่จริงควรใช้ว่า

มีนก $n$ ตัว บินเข้ารัง $m$ รัง ต้องมีอย่างน้อย 1 รังที่มีนกอย่างน้อย $\left\lceil\, \frac{n}{m} \right\rceil $ ตัว

[Chairote]

ขอบคุณครับสำหรับคำอธิบาย
...แบบที่สามเป็นกรณีทั่วไปกว่ากรณีที่สองครับ...

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

ถ้าหากว่าต้องมีกล่องอย่างน้อยหนึ่งใบที่มีเหรียญอย่างน้อยหกเหรียญ แสดงว่ากล่องใบนั้นจะมีเหรียญห้าเหรียญ หรือ สี่เหรียญ หรือ สามเหรียญ ไม่ได้ แต่กรณีสามเหรียญนั้นจะไม่ขัดแย้งกับหลักรังนกพิราบแบบที่สองเลย ผมเข้าใจผิดอะไรสักที่แน่ ๆ เลยครับ ช่วยอธิบายอีกครั้งได้ไหมครับ :sweat:

...น่าจะมีการเข้าใจผิดว่า $\left\lfloor\,x\right\rfloor + 1 = \left\lceil\,x\right\rceil $ ล่ะมั้งครับ...
ไม่ใช่ว่า $\left\lfloor\,x\right\rfloor = \left\lceil\,x\right\rceil + 1$ หรอครับ ผมเข้าใจว่า

$\left\lfloor\,x\right\rfloor$ คือจำนวนเต็มบวกค่าน้อยสุดที่มากกว่าหรือเท่ากับ $x$
$\left\lceil\,x\right\rceil$ คือจำนวนเต็มบวกค่ามากสุดที่น้อยกว่าหรือเท่ากับ $x$

[PP_nine]

ไม่ใช่ว่า $\left\lfloor\,x\right\rfloor +1= \left\lceil\,x\right\rceil $ หรอครับ ผมเข้าใจว่า

$\left\lfloor\,x\right\rfloor$ คือจำนวนเต็มบวกค่ามากสุดที่น้อยกว่าหรือเท่ากับ $x$
$\left\lceil\,x\right\rceil$ คือจำนวนเต็มบวกค่าน้อยสุดที่มากกว่าหรือเท่ากับ $x$

นิยามข้างล่างสลับกันครับครับ (แก้ตามใน quote นี้แล้วครับ) แต่นั่นยังไม่ใช่ประเด็น

ตามสมการข้างบน ถ้าผมยกตัวอย่างที่ $x$ เป็นจำนวนเต็มมันจะผิดครับ

เช่น $\left\lfloor\,4\right\rfloor +1 \not= \left\lceil\,4\right\rceil $

เพราะฝั่งซ้ายคือ 5 แต่ฝั่งขวาคือ 4 ยังไงล่ะครับ :)

[PP_nine]

ถ้าหากว่าต้องมีกล่องอย่างน้อยหนึ่งใบที่มีเหรียญอย่างน้อยหกเหรียญ แสดงว่ากล่องใบนั้นจะมีเหรียญห้าเหรียญ หรือ สี่เหรียญ หรือ สามเหรียญ ไม่ได้ แต่กรณีสามเหรียญนั้นจะไม่ขัดแย้งกับหลักรังนกพิราบแบบที่สองเลย ผมเข้าใจผิดอะไรสักที่แน่ ๆ เลยครับ ช่วยอธิบายอีกครั้งได้ไหมครับ :sweat:

ตรงนี้ลองนึกดูว่า

มีนก $n$ ตัว บินเข้ารัง $m$ รัง

โดยหยังรังนกพิราบได้ว่ามีรังอย่างน้อยหนึ่งรังที่มีนกอย่างน้อย $\left\lceil\,\frac{n}{m}\right\rceil $ ตัว

ข้อความนี้ บอกเราได้ว่ามันมีอยู่จริง ที่มีกล่องซักใบซึ่งมีนกอย่างน้อย $\left\lceil\,\frac{n}{m}\right\rceil $ ตัว

แต่เราระบุไม่ได้ว่าตำแหน่งของกล่องใบนั้นอยู่ตรงไหน เท่านั้นเอง

ฉะนั้น ผมคิดว่าคุณน่าจะสับสนพวกตำแหน่งของกล่องที่มีอยู่ ซึ่งไม่มีความสำคัญเลยในทฤษฎีนี้

ส่วนข้อสองกับข้อสาม มันติดอยู่แค่ว่าเข้าใจนิยามที่เค้าใช้ผิด จริงๆต้องเป็น $\left\lceil\,\frac{n}{m}\right\rceil $ (ปัดเศษขึ้น)

ดังนั้น ถ้า $n>m$ แสดงว่า $n=m+k$ โดยที่ $k>0$ จึงเป็นที่มาของข้อสรุปข้อสองที่ว่า มีนกอย่างน้อย $\left\lceil\,\frac{n}{m}\right\rceil = \left\lceil\,\frac{m+k}{m}\right\rceil =1+\left\lceil\,\frac{k}{m}\right\rceil \ge 2$ ตัว

แต่ข้อสามยังเหนือกว่าข้อสองเพราะเรายังไม่ทันสรุปว่า $1+\left\lceil\,\frac{k}{m}\right\rceil \ge 2$ ซะก่อน

แต่เราสรุปโต้งๆเลยว่ามีนกอย่างน้อย $\left\lceil\,\frac{n}{m}\right\rceil$ ตัว ซึ่งอาจจะเป็น 3 หรือ 4 ก็ได้ แต่มันก็ไม่ผิดอะไร เพราะมากกว่า 2 อยู่แล้ว :)

[Chairote]

อ้อ เข้าใจแล้วครับ ขอบคุณครับ

...แต่เราสรุปโต้งๆเลยว่ามีนกอย่างน้อย $\left\lceil\,\dfrac{k}{m}\right\rceil $ ตัว...
ตรงนี้ต้องเป็น $\left\lceil\,\dfrac{n}{m} \right\rceil $ หรือป่าวครับ

นิยามของ $\left\lceil\,x\right\rceil $ และ $\left\lfloor\,x\right\rfloor $ ที่ตอนแรกผมใช้นั้นมาจากหนังสือที่ผมอ่านจริง ๆ ครับ แสดงว่าหนังสือคงจะใช้สัญลักษณ์ผิดสินะครับ

[PP_nine]

อ๋อ พิมพ์ผิดครับๆ

งั้นก็เป็นที่หนังสือพิมพ์ผิดแหละครับๆ :)