อธิบายการใช้ทฤษฏี The pigeonhold principle ให้หน่อยคับ

จินตนาการ สร้างสรรค์ · #1 31 ธันวาคม 2009, 07:31

มีโจทย์ด้วย

1.There are 51 houses on the street. Each house has an address between 100 and

1099,inclusive.Show that at least two houses have address that are consecutive

integers.

2.Construct a sequence of 16 positive integers that has no increasing or decreasing

subsequence of 5 terms.

nongtum · #2 31 ธันวาคม 2009, 13:14

เอาคร่าวๆนะครับ

ข้อแรก ตรง 1099 ต้องเป็น 199 หรือเปล่าครับ
ถ้าเป็น 199 ก็ให้มองเลขที่บ้าน 100-101 เป็นรังที่ 1 เลขที่บ้าน 102-103 เป็นรังที่สอง ... เลขที่บ้าน 198-199 เป็นรังที่ 50
โดยไม่เสียนัย จะให้เลขบ้านทั้ง 50 หลังแรกเป็นเลขคี่
โดยกฏรังนก จะได้ว่า ไม่ว่าบ้านหลังที่ 51 จะอยู่รังไหน เลขบ้านของหลังที่ 51 ซึ่งเป็นเลขคู่จะต้องเป็นเลขเรียงกับเลขที่อยู่ในรังเดียวกันเสมอครับ

ข้อสอง ขอถามนิดนึงครับ ที่ว่า has no increasing or decreasing subsequence of 5 terms จำเป็นต้อง strictly ไหมครับ
ถ้าไม่ ก็มีตัวอย่าง เช่น 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

จินตนาการ สร้างสรรค์ · #3 03 มกราคม 2010, 11:31

อ้างอิง:

ข้อความเดิมเขียนโดยคุณ nongtum

เอาคร่าวๆนะครับ

ข้อแรก ตรง 1099 ต้องเป็น 199 หรือเปล่าครับ
ถ้าเป็น 199 ก็ให้มองเลขที่บ้าน 100-101 เป็นรังที่ 1 เลขที่บ้าน 102-103 เป็นรังที่สอง ... เลขที่บ้าน 198-199 เป็นรังที่ 50
โดยไม่เสียนัย จะให้เลขบ้านทั้ง 50 หลังแรกเป็นเลขคี่
โดยกฏรังนก จะได้ว่า ไม่ว่าบ้านหลังที่ 51 จะอยู่รังไหน เลขบ้านของหลังที่ 51 ซึ่งเป็นเลขคู่จะต้องเป็นเลขเรียงกับเลขที่อยู่ในรังเดียวกันเสมอครับ

ข้อสอง ขอถามนิดนึงครับ ที่ว่า has no increasing or decreasing subsequence of 5 terms จำเป็นต้อง strictly ไหมครับ
ถ้าไม่ ก็มีตัวอย่าง เช่น 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

ข้อหนึ่งโจทย์ต้องเป็น 1000-1099

ส่วนข้อสอง has no increasing or decreasing subsequence ก็คือไม่เพิ่มหรือลดเหตุการณ์ ก็คือเหตุการณ์ยังคงเป็นเหมือนเดิม คำตอบก็คือ 4,3,2,1,8,7,6,5,12,11,10,9,16,15,14,13
ประมาณนี้แหละคับ

nongtum · #4 03 มกราคม 2010, 23:38

#3
โอเคครับ ถ้างั้นข้อแรกก็น่าจะใช้แนวคิดคล้ายๆที่ผมยกมาให้ดูได้ครับ เปลี่ยนแค่เลขนิดหน่อย
ส่วนข้อสอง ผมเข้าใจคำว่า subsequence ว่าเป็นลำดับย่อยครับ ซึ่งที่ยกมาน่าจะใช้ได้แล้วครับ
แต่ถ้าเขาอยากให้แสดงว่าทำไมต้องสร้างลำดับย่อยแบบนี้ ลองดู Erdős–Szekeres theorem นะครับ

จินตนาการ สร้างสรรค์ · #5 08 มกราคม 2010, 09:38

เข้าใจแล้วอ่ะ ขอบคุณ

หัวข้อคล้ายคลึงกัน
หัวข้อ	ผู้ตั้งหัวข้อ	ห้อง	คำตอบ	ข้อความล่าสุด
ข้อสอบ Principle Math	ครูนะ	คณิตศาสตร์อุดมศึกษา	2	16 มีนาคม 2009 05:47
Extreme principle	dektep	คอมบินาทอริก	2	06 เมษายน 2008 08:35
The Pigeonhole Principle	Tony	ปัญหาคณิตศาสตร์ทั่วไป	9	08 เมษายน 2005 22:38