|
|
#1
02 กรกฎาคม 2007, 18:30
|
||||
|
||||
พอดีเห็นกระทู้เงียบเหงา เลยเอาโจทย์มาฝากครับ เกี่ยวกับรังนกพิราบไม่ยากไม่ง่ายครับ
1) อยากทราบว่าจะต้องมีคนอย่างน้อยที่สุดกี่คนจึงจะรับประกันได้ว่าจะมีคนเกิดเดือนเดียวกันสามคน และจงพิสูจน์ว่าคำตอบนั้นเป็นจริง 2) มีจุดห้าจุดอยู่ในรูปสามเหลี่ยมด้านเท่ายาวด้านละสองหน่วย จงแสดงว่าจะมีจุดสองจุดที่ห่างกันไม่เกินหนึ่งหน่วย 3) ถ้าให้จุดสิบจุดอยู่ในรูปสี่เหลี่ยมด้านเท่ายาวด้านละสามหน่วย จงแสดงว่าจะมีจุดสองจุดที่ห่างกันไม่เกิน หน่วย 4) ถ้าเรามีจำนวนเต็มบวกที่ต่างกัน n+1 ตัว ที่น้อยกว่าหรือเท่ากับ 2n จงแสดงว่าภายในจำนวนนี้จะมีจำนวนคู่หนึ่งที่บวกกันได้ 2n+1 5) ถ้าเรามีจำนวนเต็มบวกที่ต่างกัน n+1 ตัว ที่น้อยกว่าหรือเท่ากับ 2n จงแสดงว่าภายในจำนวนนี้จะมีจำนวนคู่หนึ่งที่ตัวหารร่วมมากของสองจำนวนนี้เท่ากับหนึ่ง
__________________
ความรู้คือ ประทีป ส่องทาง จริงๆนะครับ 
02 กรกฎาคม 2007 21:58 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ nongtum เหตุผล: Double post merged 
|
|
#2
06 กรกฎาคม 2007, 16:00
|
||||
|
||||
|
ข้อแรกตอบ 25 คนนะครับ พิสูจน์โดยใช้หลักรังนกพิราบอย่างเข้ม นั่นคือ
$\left\lceil\,\frac{ n}{12}\right\rceil=3$ ดังนั้นค่า n ที่น้อยที่สุดคือ $25$
__________________
ความรู้คือ ประทีป ส่องทาง จริงๆนะครับ
|
|
#3
06 กรกฎาคม 2007, 20:17
|
|||
|
|||
Add another question
 6. Given graph with 14 vertices and 29 edges , prove that it must have cycle length 4. (Hint: Using Pigeonhole principle)
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว
|
|
#5
12 กรกฎาคม 2007, 11:22
|
||||
|
||||
|
อ้างอิง:
โดยหลักการรังนกพิราบอย่างเข้มจะได้ว่า มีอย่างน้อย 10 จุดที่บรรจุใจวงแหวนดังกล่าว ไอเดียน่าจะประมาณนี้ใช่ไหมครับ
__________________
ความรู้คือ ประทีป ส่องทาง จริงๆนะครับ
|
|
#6
12 กรกฎาคม 2007, 14:14
|
|||
|
|||
|
อ้างอิง:
This question is well-known. If I remember right, the idea to solve is related to area of circle and annulus ring.
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว
|
|
#8
13 กรกฎาคม 2007, 11:17
|
|||
|
|||
|
One way to prove this is to start with representing graph in terms of adjacent matrix and prove from such matrix.
You only set up matrix 14*14 and put "1" or "0" in each element to form adjacent matrix. I hope that you can guess the meaning of "1" and "0". The remaining is just Pigeonhole principle.
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว
|
|
#9
17 กรกฎาคม 2007, 16:13
|
||||
|
||||
|
อ้างอิง:
__________________
ความรู้คือ ประทีป ส่องทาง จริงๆนะครับ
|
|
#10
30 สิงหาคม 2007, 10:56
|
||||
|
||||
|
อ้างอิง:
ข้อ 4) สร้างเซตต่อไปนี้ $\{1,2n\},\{2,2n-1\},\{3,2n-2\},...,\{n,n+1\}$ ให้เซตเหล่านี้ทั้งหมดแทนรัง ให้จำนวนทั้งหมด $n+1$ แทนนก เราจะได้สิ่งที่ต้องการ ข้อ 5) ทำนองเดียวกับข้อ 4 แต่สร้างเซตแบบนี้ค่ะ $\{1,2\},\{3,4\},\{5,6\},...,\{n,n+1\}$
__________________
การเรียนรู้ไม่มีวันสิ้นสุด
|
  |
|
|
