ของฝากจากมหา
รังนกพิราบเป็นวิชาที่เกี่ยวข้องกับการเรียงสับเปลี่ยนและจัดกลุ่มสิ่งของ
เมื่อไหร่ก็ตามเมื่อนกมากกว่ารังจะมีนกมากกว่ารังละ 1 ตัว
หลักการรังนกพิราบ
" ถ้ามีของอยู่จำนวน k+1 ชิ้นหรือมากกว่าใส่ลงในกล่องแล้วจะต้องมีกล่องอย่างน้อย 1 กล่องที่บรรจุของมากกว่า 1 ชิ้น "
พิสูจน์
พิสูจน์โดยใช้ข้อขัดแย้งสมมติว่าข้อความนี้ไม่จริง นั่นคือทุกกล่องมีของไม่เกิน 1 ชิ้นจึงได้ว่ามีของได้อย่างมาก k ชิ้น
คำสำคัญ (Tags): #uncategorized
หมายเลขบันทึก: 33084เขียนเมื่อ 3 มิถุนายน 2006 16:08 น. ()ความเห็น (1)
ตัสนีม 4/ทีต้า เลขที่ 15
อะโห ฟังปุ๊บเอามา up ปั๊บเลย^^ เพื่อนเราเจ๊ง เอ้ย เจ๋งๆๆ !!!