รังนกพิราบ

[mercedesbenz]

พอดีเห็นกระทู้เงียบเหงา เลยเอาโจทย์มาฝากครับ เกี่ยวกับรังนกพิราบไม่ยากไม่ง่ายครับ
1) อยากทราบว่าจะต้องมีคนอย่างน้อยที่สุดกี่คนจึงจะรับประกันได้ว่าจะมีคนเกิดเดือนเดียวกันสามคน และจงพิสูจน์ว่าคำตอบนั้นเป็นจริง

2) มีจุดห้าจุดอยู่ในรูปสามเหลี่ยมด้านเท่ายาวด้านละสองหน่วย จงแสดงว่าจะมีจุดสองจุดที่ห่างกันไม่เกินหนึ่งหน่วย

3) ถ้าให้จุดสิบจุดอยู่ในรูปสี่เหลี่ยมด้านเท่ายาวด้านละสามหน่วย จงแสดงว่าจะมีจุดสองจุดที่ห่างกันไม่เกิน หน่วย

4) ถ้าเรามีจำนวนเต็มบวกที่ต่างกัน n+1 ตัว ที่น้อยกว่าหรือเท่ากับ 2n จงแสดงว่าภายในจำนวนนี้จะมีจำนวนคู่หนึ่งที่บวกกันได้ 2n+1

5) ถ้าเรามีจำนวนเต็มบวกที่ต่างกัน n+1 ตัว ที่น้อยกว่าหรือเท่ากับ 2n จงแสดงว่าภายในจำนวนนี้จะมีจำนวนคู่หนึ่งที่ตัวหารร่วมมากของสองจำนวนนี้เท่ากับหนึ่ง

[mercedesbenz]

ข้อแรกตอบ 25 คนนะครับ พิสูจน์โดยใช้หลักรังนกพิราบอย่างเข้ม นั่นคือ
$\left\lceil\,\frac{ n}{12}\right\rceil=3$ ดังนั้นค่า n ที่น้อยที่สุดคือ $25$

[passer-by]

Add another question

6. Given graph with 14 vertices and 29 edges , prove that it must have cycle length 4. (Hint: Using Pigeonhole principle)

[gools]

อีกข้อนึงครับ
กำหนดวงกลมที่มีรัศมี 16 และมีจุดที่แตกต่างกัน 650 จุดอยู่ข้างใน
พิสูจน์ว่าต้องมีอย่างน้อย 10 จุดที่บรรจุในวงแหวนที่มีรัศมีวงในเท่ากับ 2 และรัศมีวงนอกเท่ากับ 3

[mercedesbenz]

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

อีกข้อนึงครับ
กำหนดวงกลมที่มีรัศมี 16 และมีจุดที่แตกต่างกัน 650 จุดอยู่ข้างใน
พิสูจน์ว่าต้องมีอย่างน้อย 10 จุดที่บรรจุในวงแหวนที่มีรัศมีวงในเท่ากับ 2 และรัศมีวงนอกเท่ากับ 3

Solution สร้างวงแหวนที่รัศมีวงใน 2 วงนอก 3 จำนวน 52 วง
โดยหลักการรังนกพิราบอย่างเข้มจะได้ว่า มีอย่างน้อย 10 จุดที่บรรจุใจวงแหวนดังกล่าว
ไอเดียน่าจะประมาณนี้ใช่ไหมครับ

[passer-by]

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

Solution สร้างวงแหวนที่รัศมีวงใน 2 วงนอก 3 จำนวน 52 วง
โดยหลักการรังนกพิราบอย่างเข้มจะได้ว่า มีอย่างน้อย 10 จุดที่บรรจุใจวงแหวนดังกล่าว
ไอเดียน่าจะประมาณนี้ใช่ไหมครับ

This question is well-known. If I remember right, the idea to solve is related to area of circle and annulus ring.

[gools]

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

Add another question

6. Given graph with 14 vertices and 29 edges , prove that it must have cycle length 4. (Hint: Using Pigeonhole principle)

ข้อนี้ทำไงอ่ะคับ

[passer-by]

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.

[mercedesbenz]

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

พอดีเห็นกระทู้เงียบเหงา เลยเอาโจทย์มาฝากครับ เกี่ยวกับรังนกพิราบไม่ยากไม่ง่ายครับ

2) มีจุดห้าจุดอยู่ในรูปสามเหลี่ยมด้านเท่ายาวด้านละสองหน่วย จงแสดงว่าจะมีจุดสองจุดที่ห่างกันไม่เกินหนึ่งหน่วย

Hint of the solution if you interest.

และใช้หลักการรังนกพิราบครับ

[konkoonJAi]

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

พอดีเห็นกระทู้เงียบเหงา เลยเอาโจทย์มาฝากครับ เกี่ยวกับรังนกพิราบไม่ยากไม่ง่ายครับ
1) อยากทราบว่าจะต้องมีคนอย่างน้อยที่สุดกี่คนจึงจะรับประกันได้ว่าจะมีคนเกิดเดือนเดียวกันสามคน และจงพิสูจน์ว่าคำตอบนั้นเป็นจริง

2) มีจุดห้าจุดอยู่ในรูปสามเหลี่ยมด้านเท่ายาวด้านละสองหน่วย จงแสดงว่าจะมีจุดสองจุดที่ห่างกันไม่เกินหนึ่งหน่วย

3) ถ้าให้จุดสิบจุดอยู่ในรูปสี่เหลี่ยมด้านเท่ายาวด้านละสามหน่วย จงแสดงว่าจะมีจุดสองจุดที่ห่างกันไม่เกิน หน่วย

4) ถ้าเรามีจำนวนเต็มบวกที่ต่างกัน n+1 ตัว ที่น้อยกว่าหรือเท่ากับ 2n จงแสดงว่าภายในจำนวนนี้จะมีจำนวนคู่หนึ่งที่บวกกันได้ 2n+1

5) ถ้าเรามีจำนวนเต็มบวกที่ต่างกัน n+1 ตัว ที่น้อยกว่าหรือเท่ากับ 2n จงแสดงว่าภายในจำนวนนี้จะมีจำนวนคู่หนึ่งที่ตัวหารร่วมมากของสองจำนวนนี้เท่ากับหนึ่ง

ข้อ 3) สร้างรูปสี่เหลี่ยมด้านเท่าด้านละ 1 หน่วย จะได้ 9 รูป ให้ 9 รูปนั้นแทนรัง และ 10 จุดนั้นแทนนก เราจะได้สิ่งที่ต้องการ
ข้อ 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\}$