|
|
|||||||
| สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
  |
|
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
|
#1
05 มิถุนายน 2007, 19:46
|
||||
|
||||
รังนกพิราบ 2 ครับ ช่วยหน่อยนะครับ!!
คิดว่าน่าจะรังนกพิราบ นะครับ (USAMO 1978)
1. มีคน $n$ คน มีโครงการ $n+1$ โครงการ แต่ละโครงการมีคนทำงาน 3 คน โดยที่ไม่มี 2 โครงการใดมีคนทำงานชุดเดียวกัน จงพิสูจน์ว่า มีโครงการ 2 โครงการ ซึ่งมีคนทำงานร่วมกันคนเดียว 2.ให้ $A\subseteq {1,2,3,...,50}$ เป็นเซตซึ่งมีสมาชิก 10 ตัว จงแสดงว่า มีสับเซตของ $A$ อย่างน้อยสองเซตซึ่งมีสมาชิก 4 ตัว และผลบวกของสมาชิกทั้งสี่ตัวในเซตทั้งสองนั้นเท่ากัน นั่นคือ มี $B=\left\{\,\right. b_1,b_2,b_3,b_4\left.\,\right\} \subseteq A$ และ $C=\left\{\,\right. c_1,c_2,c_3,c_4\left.\,\right\} \subseteq A$ ซึ่ง $b_1+b_2+b_3+b_4 = c_1+c_2+c_3+c_4$ 3.ให้ $S=\left\{\,\right. 1,2,...,2n\left.\,\right\} $ เมื่อ $n$ เป็นจำนวนเต็มบวกใดๆ หยิบจำนวนเต็มใดๆ มาจาก $S$ จำนวน $n$ จำนวน จงพิสูจน์ว่า มีจำนวนเต็มอย่างน้อย 2 จำนวน $k$ และ $m$ ซึ่งไม่มีตัวประกอบร่วมที่ไม่ใช่ 1.
__________________
คาราวะ 05 มิถุนายน 2007 20:56 : ข้อความนี้ถูกแก้ไขแล้ว 8 ครั้ง, ครั้งล่าสุดโดยคุณ expol 
|
|
#2
06 มิถุนายน 2007, 03:52
|
|||
|
|||
ข้อ 3 ภาษาดูเข้าใจยากจังครับ ตรงที่บอกว่าให้พิสูจน์เกี่ยวกับ k,m น่าจะใช้คำว่า มีจำนวนเต็มบวก k,m ที่เป็น relative prime จะูเข้าใจง่ายขึ้นนะครับ
อีกอย่างผมว่า โจทย์ข้อนี้์ผิดหรือเปล่าครับ ผมว่าน่าจะหยิบออกมา n+1 จำนวนนะครับ ไม่ใช่ n จำนวน เช่น ถ้าเลือก 2,4,6,...,2n จะพบว่าไม่มี k ,m ที่โจทย์ต้องการแน่่นอน แต่ถ้าแก้เป็น n+1 จำนวน แล้ว การพิสูจน์ก็ง่ายมากครับ ลอง pair up {1,2} ,{3,4} ,...{2n-1,2n} เสมือนเป็นรัง n รัง แล้วเลือกนกออกมา n+1 ตัว ก็จะได้ k,m ที่ต้องการและเป็น relative prime ครับ ส่วนข้อ 1 ดูที่นี่ สิครับ และข้อ 2 เพราะ possible sums ของตัวเลข 4 ตัวใน A มีตั้งแต่ 1+2+3+4=10 ไปจนถึงมากสุด 50+49+48+47=194 เท่ากับว่ามี possible sums อย่างมาก 185 แบบ (รัง) แต่เนื่องจากจำนวนสับเซตที่มีสมาชิก 4 ตัวมี $ \binom{10}{4}=210 $ แบบ (นก) เมื่อมีนกมากกว่ารัง ก็จะได้สิ่งที่โจทย์ต้องการครับ
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว 06 มิถุนายน 2007 17:04 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ passer-by
|
|
#4
08 มิถุนายน 2007, 19:18
|
||||
|
||||
อ้างอิง:
 พึ่งเคยเรียนเรื่องนี้อ่ะครับ
|
|
#5
09 มิถุนายน 2007, 02:57
|
|||
|
|||
|
จะเห็นว่า เลขตั้งแต่ 1 ถึง 2n ถูก partition ออกเป็น n เซต เซตละ 2 จำนวน ตามที่เห็นด้านบนครับ
เมื่อเราเลือก ตัวเลข n+1 จำนวน ย่อมจะต้องมีอย่างน้อย 1 เซตที่ถูกเลือกทั้ง 2 ตัว (ถ้าไม่เชื่อ ลองเลือกดูได้ครับ) แต่จะเห็นว่า เลข ในแต่ละเซต เป็นเลขที่ติดกัน ซึ่งแน่นอนว่า ห.ร.ม. เป็น 1 เสมอ หรือที่เรียกว่า relative prime แล้วเราก็จะได้ k,m ที่โจทย์ต้องการครับ p.s. จริงๆ concept ของหลักรังนกพิราบ ไม่มีอะไรซับซ้อนหรอกครับ แต่การหานก หารัง ก็มักทำให้เราหงุดหงิดอยู่เสมอ ดังจะเห็นได้จากข้อสอบโอลิมปิกของประเทศต่างๆหรือระดับนานาชาติครับ
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว
|
|
#6
10 มิถุนายน 2007, 10:42
|
||||
|
||||
|
ขอบคุณมากครับคุณ passer-by กระจ่างแล้วครับ คราวหลังคงต้องขอคำชี้แนะอีกนะครับ
 
|
| |
|
|
