GotoKnow
  • เข้าระบบ
  • สมัครสมาชิก
  • แผงจัดการ
  • ออกจากระบบ
GotoKnow

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

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

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

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

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

พิสูจน์

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

 

 

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

คำสำคัญ (keywords): uncategorized
หมายเลขบันทึก: 33084
เขียน:
แก้ไข:
ความเห็น: 1
อ่าน:
สัญญาอนุญาต: สงวนสิทธิ์ทุกประการ

ความเห็น (1)

อะโห ฟังปุ๊บเอามา up ปั๊บเลย^^ เพื่อนเราเจ๊ง เอ้ย เจ๋งๆๆ !!!