ของฝากจากมหา

รังนกพิราบเป็นวิชาที่เกี่ยวข้องกับการเรียงสับเปลี่ยนและจัดกลุ่มสิ่งของ

เมื่อไหร่ก็ตามเมื่อนกมากกว่ารังจะมีนกมากกว่ารังละ  1 ตัว

หลักการรังนกพิราบ

" ถ้ามีของอยู่จำนวน k+1 ชิ้นหรือมากกว่าใส่ลงในกล่องแล้วจะต้องมีกล่องอย่างน้อย  1 กล่องที่บรรจุของมากกว่า 1 ชิ้น "

พิสูจน์

พิสูจน์โดยใช้ข้อขัดแย้งสมมติว่าข้อความนี้ไม่จริง นั่นคือทุกกล่องมีของไม่เกิน 1 ชิ้นจึงได้ว่ามีของได้อย่างมาก k ชิ้น

 

 

บันทึกนี้เขียนที่ GotoKnow โดย  ใน ลัยลา

คำสำคัญ (Tags)#uncategorized

หมายเลขบันทึก: 33084, เขียน: 03 Jun 2006 @ 16:08 (), แก้ไข: 13 May 2012 @ 11:35 (), สัญญาอนุญาต: สงวนสิทธิ์ทุกประการ, ความเห็น: 1, อ่าน: คลิก


ความเห็น (1)

ตัสนีม 4/ทีต้า เลขที่ 15
IP: xxx.129.49.211
เขียนเมื่อ 
อะโห ฟังปุ๊บเอามา up ปั๊บเลย^^ เพื่อนเราเจ๊ง เอ้ย เจ๋งๆๆ !!!