|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
|||
|
|||
หลักรังนกพิราบทั้งสามแบบ
ผมมีข้อสงสัยในเรื่องนี้นิดหน่อยครับ ผมเข้าใจว่าหลักรังนกพิราบนั้นมีทั้งหมดสามแบบดังนี้
แบบที่หนึ่ง ถ้ามีนก $n+1$ ตัวบินเข้ารัง $n$ รัง แล้วมีรังนกอย่างน้อยหนึ่งรังที่มีนกอย่างน้อยสองตัว แบบที่สอง ให้ $m,n$ เป็นจำนวนเต็มบวกและ $n > m$ ถ้ามีนก $n$ ตัวบินเข้ารัง $m$ รัง แล้วมีรังนกอย่างน้อยหนึ่งรังที่มีนกอย่างน้อยสองตัว แบบที่สาม ให้ $m,n$ เป็นจำนวนเต็มบวกและ $n > m$ ถ้ามีนก $n$ ตัวบินเข้ารัง $m$ รัง แล้วมีรังนกอย่างน้อยหนึ่งรังที่มีนกอย่างน้อย $\left\lfloor\,\dfrac{n}{m}\right\rfloor + 1$ ตัว สังเกตว่าเงื่อนไขของแบบที่สองเป็นเงื่อนไขเดียวกับของแบบที่สาม แต่ข้อสรุปออกมาต่างกัน ตอนอ่านตำราผมก็งงในแบบที่สองครับว่ามันจะเป็นจริงได้อย่างไร ผมคิดว่าถ้าเงื่อนไขเป็นแบบที่สองหรือแบบที่สามแล้ว ข้อสรุปควรจะออกมาเป็นแบบที่สามครับ หากใครเข้าใจหลักการนี้อย่างแจ่มแจ้ง ช่วยอธิบายหน่อยครับ 18 พฤศจิกายน 2011 23:44 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ Chairote |
#2
|
||||
|
||||
แบบที่สามเป็นกรณีทั่วไปกว่ากรณีที่สองครับ
เช่น วางเหรียญ 16 เหรียญ ลงในกล่อง 3 ใบ โดยเงื่อนไขแบบที่สามจะบอกได้ว่ามีกล่องใบหนึ่งมีเหรียญอย่างน้อยหกเหรียญ ซึ่งเป็นไปตามแบบที่สองด้วย
__________________
คนไทยร่วมใจอย่าใช้ภาษาวิบัติ ฝึกพิมพ์สัญลักษณ์สักนิด ชีวิต(คนตอบและคนถาม)จะง่ายขึ้นเยอะ (จริงๆนะ) Stay Hungry. Stay Foolish. |
#3
|
||||
|
||||
อ้างอิง:
เพราะลองให้ $x$ เป็นจำนวนเต็ม สมการนี้จะผิดทันที อันที่จริงควรใช้ว่า อ้างอิง:
__________________
keep your way.
|
#4
|
|||
|
|||
ขอบคุณครับสำหรับคำอธิบาย
อ้างอิง:
อ้างอิง:
อ้างอิง:
$\left\lfloor\,x\right\rfloor$ คือจำนวนเต็มบวกค่าน้อยสุดที่มากกว่าหรือเท่ากับ $x$ $\left\lceil\,x\right\rceil$ คือจำนวนเต็มบวกค่ามากสุดที่น้อยกว่าหรือเท่ากับ $x$ 19 พฤศจิกายน 2011 08:50 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ nongtum เหตุผล: double post |
#5
|
||||
|
||||
อ้างอิง:
ตามสมการข้างบน ถ้าผมยกตัวอย่างที่ $x$ เป็นจำนวนเต็มมันจะผิดครับ เช่น $\left\lfloor\,4\right\rfloor +1 \not= \left\lceil\,4\right\rceil $ เพราะฝั่งซ้ายคือ 5 แต่ฝั่งขวาคือ 4 ยังไงล่ะครับ
__________________
keep your way.
18 พฤศจิกายน 2011 22:57 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ PP_nine |
#6
|
||||
|
||||
อ้างอิง:
อ้างอิง:
แต่เราระบุไม่ได้ว่าตำแหน่งของกล่องใบนั้นอยู่ตรงไหน เท่านั้นเอง ฉะนั้น ผมคิดว่าคุณน่าจะสับสนพวกตำแหน่งของกล่องที่มีอยู่ ซึ่งไม่มีความสำคัญเลยในทฤษฎีนี้ ส่วนข้อสองกับข้อสาม มันติดอยู่แค่ว่าเข้าใจนิยามที่เค้าใช้ผิด จริงๆต้องเป็น $\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 อยู่แล้ว
__________________
keep your way.
18 พฤศจิกายน 2011 23:54 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ PP_nine |
#7
|
|||
|
|||
อ้อ เข้าใจแล้วครับ ขอบคุณครับ
อ้างอิง:
นิยามของ $\left\lceil\,x\right\rceil $ และ $\left\lfloor\,x\right\rfloor $ ที่ตอนแรกผมใช้นั้นมาจากหนังสือที่ผมอ่านจริง ๆ ครับ แสดงว่าหนังสือคงจะใช้สัญลักษณ์ผิดสินะครับ |
#8
|
||||
|
||||
อ๋อ พิมพ์ผิดครับๆ
งั้นก็เป็นที่หนังสือพิมพ์ผิดแหละครับๆ
__________________
keep your way.
|
|
|