Pigeonhole Principle Problem - วงกลม

Question

ฉันกำลังแก้ไขปัญหาการบ้านโดยมีคำแนะนำต่อไปนี้:

สมมติว่ามีนักเรียนชั้น 2 nชื่อต่างกันนั่งอยู่ในการแสดงขนาดใหญ่และบอกวงกลม ครูส่งการบ้านคืน แต่นักเรียนแต่ละคนในวงกลมจะได้รับการบ้านของนักเรียนอีกคน ดังนั้นชั้นเรียนตกลงที่จะส่งการบ้านไปให้นักเรียนนั่งทางขวา อีกครั้งชื่อผิดทั้งหมด สำหรับครั้งแรกnครั้งที่พวกเขาทำเช่นนี้พวกเขาทั้งหมดมีชื่อที่ไม่ถูกต้องทำการบ้าน ดังนั้นในทั้งหมดจึงมีการกำหนดค่าn + 1ที่นักเรียนทุกคนจับคู่กับการบ้านของคนอื่น) แสดงว่าถ้าพวกเขาส่งการบ้านไปทางขวาต่อไปในที่สุดพวกเขาก็จะไปถึงโครงร่างที่นักเรียน 3 คนมีการบ้านพร้อมชื่อของตัวเอง

ฉันได้ทำปัญหาบางอย่างเกี่ยวกับหลักการของนกพิราบ แต่ปัญหานี้ทำให้ฉันมีปัญหามากขึ้นเป็นพิเศษ ฉันได้วาดภาพสองกรณีแยกกันโดยที่n = 2ซึ่งทั้งสองส่งผลให้มีขนาดชั้นเรียนเท่ากับ 4 ตัวอักษรตัวพิมพ์ใหญ่คือเด็กและตัวพิมพ์เล็กเป็นการบ้านที่ตรงกัน

ทดสอบกับชั้น 4

ด้วยการกำหนดค่าเริ่มต้นข้างต้นฉันไม่สามารถทำให้มันเป็นที่ที่นักเรียนสามคนมีการบ้านที่ถูกต้องพร้อมกันเพียงสองคนพร้อมกัน ฉันยังไม่ได้ละเมิดข้อห้ามใด ๆ :

1. นักเรียนแต่ละคนไม่ได้รับการบ้านโดยเริ่มต้น
2. นักเรียนแต่ละคนไม่มีการบ้านหลังจากผ่านไป 1 รอบ

กรณีที่สองในภาพวาดคือการยกตัวอย่างสิ่งที่จะเกิดขึ้นหากนักเรียนที่อยู่ทางซ้ายมือมีการบ้านคือต้องใช้บัตรเพียงใบเดียว อย่างไรก็ตามฉันค่อนข้างแน่ใจว่าคำถามนี้บอกว่าสิ่งนี้ไม่ได้รับอนุญาตตั้งแต่นั้นมา

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

หมายความว่ารอบหลังผ่านรอบแรกต้องมั่นใจว่าไม่มีใครทำการบ้าน ฉันเชื่อว่าคำถามนั้นถูกต้องในสิ่งที่เสนอ แต่ฉันมีปัญหาในการทำความเข้าใจและใช้หลักการ Pigeonhole คือ "หลุม" เด็กและ "นกพิราบ" เขาทำการบ้านและหากดังนั้นวิธีที่จะเป็นหนึ่งในการคำนวณในกรณีที่มันไม่ง่ายเหมือนนกพิราบในหลุม แต่ที่ถูกต้องนกพิราบในหลุมที่ถูกต้องหรือไม่ ความช่วยเหลือใด ๆ จะได้รับการชื่นชม

Answer 1

หากเราดำเนินการอย่างเต็มรูปแบบ $2n - 1$ผ่านไปทุกคนก็ได้เห็นการบ้านของพวกเขาเพียงครั้งเดียว เรารู้ว่าประการแรก$n$ ผ่านไปครั้งแรก $n + 1$การกำหนดค่าไม่มีใครเห็นการบ้านของพวกเขา หากเราดำเนินต่อไปในส่วนที่เหลือ$n - 1$การกำหนดค่าและที่มากที่สุด 2 คนดูบ้านของพวกเขาในทุก ๆ การกำหนดค่าที่มากที่สุดหลายวิธีที่นักเรียนได้เห็นบ้านของพวกเขา? สิ่งนี้ขัดแย้งกับสิ่งที่เราได้กล่าวไปแล้วอย่างไร

Answer 2

นี่คือวิธีที่คุณสามารถเข้าถึงได้ เติมช่องว่างด้วยตัวคุณเอง

โดยทั่วไปเมื่อใช้ PP สิ่งสำคัญมากที่จะต้องชัดเจนว่ารูและนกพิราบคืออะไร การกำหนดสิ่งเหล่านี้มักจะเป็นการเริ่มต้นที่ดีดังนั้น:
ให้รูเป็น "การกำหนดค่าที่นักเรียนจะได้รับการบ้านหมุนเวียน$k$ครั้ง "
ให้นกพิราบ" นักเรียนทำการบ้านถูกต้อง "

สมมติว่าคำจำกัดความเหล่านี้เป็นคำจำกัดความที่ถูกต้องที่จะใช้เรามาดูกันว่า PP ทำงาน
อย่างไร: มีนกพิราบกี่ตัว?
จำนวนหลุมสูงสุดที่เราสามารถมีได้คือเท่าใดเพื่อให้แน่ใจว่ามีบางหลุมที่มีนกพิราบ 3 ตัว?
เราแสดงให้เห็นได้ไหมว่าเรามีหลุมนี้มากที่สุด? ถ้าไม่เราจะปรับรู (หรือนกพิราบ) ได้อย่างไร?

---

มีความไม่แน่นอนบางประการเกี่ยวกับจำนวนหลุมที่แน่นอน

• ถ้าจำนวนหลุมเท่ากับ $n-1$ (หมายความว่ามี $n+1$ การกำหนดค่าที่ไม่ตรงกันโดยสิ้นเชิง) จากนั้น PP จะทำงานโดยตรง
• ถ้าจำนวนหลุมเท่ากับ $n$ (หมายความว่ามี $n$การกำหนดค่าที่ไม่ตรงกันโดยสิ้นเชิง) คำถามนั้นผิด โดยเฉพาะอย่างยิ่งข้อความที่เป็นจริงสำหรับคู่$n$ และเท็จสำหรับคี่ $n$. สิ่งนี้สามารถพิสูจน์ได้โดย 1) การขัดแย้งกับ "เอกสาร 2 ฉบับที่ตรงกัน$n$ เป็นคู่ "และ 2) การสร้างเคสสำหรับ" กระดาษ 2 ชิ้นที่ตรงกัน $n$ เป็นเลขคี่ ".