รังนกพิราบ

[polsk133]

1.เห็นหนังสือ O-plus ของเพื่อนคอร์สมหิดลรอบสองมีอยู่เลยอยากทราบว่าทำไงครับ(ปล.ไม่ได้เรียนoplus)

1.จงแสดงว่า ในคน60ล้านคนจะต้องมีอย่างน้อยคู่หนึ่งที่มีเซลเหมือนกัน (อ่านแล้วงงไหมครับ ผมงง)

2.จงแสดงว่า เลือกจำนวนนับจาก 1-200 มา 101 จำนวนจะต้องมีอย่างน้อยคู่หนึ่งที่ตัวหนึ่งหารอีกตัวหนึ่งลงตัว

[วะฮ่ะฮ่า03]

2.แบ่ง200จำนวนเป็น{1,2} {3,6}...เซต{a,2a}
100เซต จากรังนกพิราบจะมีเซต1เซตท่ถูกเลือกสมาชิก 2 ตัวซึ่งหารกันลงตัว

[artty60]

ให้ดูว่าจาก1-200มีจำนวนเฉพาะอยู่กี่จำนวน ซึ่งมีไม่ถึง100จำนวนแน่

เพราะฉะนั้นถ้าเลือกมา101จำนวนย่อมต้องมีจำนวนประกอบอยู่ด้วยอย่างน้อย1คู่

ตามวิธีของ#2 โดยที่$a=prime\,number<200$ จำนวนเซตเท่ากับจำนวน$prime\,number$

[Singularity]

ข้อ 1 โจทย์น่าจะบอกว่าจำนวนเซลแตกต่างกันน้อยกว่า 60 ล้านรูปแบบนะคับ

[Thgx0312555]

ข้อความเดิมเขียนโดยคุณ วะฮ่ะฮ่า03

2.แบ่ง200จำนวนเป็น{1,2} {3,6}...เซต{a,2a}
100เซต จากรังนกพิราบจะมีเซต1เซตท่ถูกเลือกสมาชิก 2 ตัวซึ่งหารกันลงตัว

ใช้วิธีนี้ไม่ได้เพราะ 200 จำนวนที่แบ่งมาพบว่าจำนวนเช่น 197 จะไม่มีที่อยู่คู่ใดเลย
แต่ใน 101 จำนวนนั้นอาจมี 197 อยู่ด้วยก็ได้ครับ จึงไม่เป็นไปตามหลักรังนกพิราบ

ดังนั้นจึงควรใช้วิธีนี้แทน
จับกลุ่ม
{1,2,4,...}{3,6,12,...}{5,10,20,...}{7,14,...}{9,18,...}{11,...}{13,...}{15,...}{17,...}{19,...}...{199}
มี 100 กลุ่ม
ดังนั้นมีสองจำนวนอยู่ในกลุ่มเดียวกัน
พบว่าสองจำนวนนั้นหารกันลงตัว
Q.E.D.

[polsk133]

ขอบคุณครับ

[artty60]

วิธีของ#2ก็ใช้ได้เหมือนกันนะครับ

และ$197$เป็น$prime\,number$ตัวสุดท้ายของ$200$จำนวนแรก

แค่เซตนั้นก็จะมีสมาชิกแค่ตัวเดียว

ผมว่าแสดงได้หลายวิธีนะขอให้แสดงให้ดูเพียงแค่ใน$200$จำนวน

มีจำนวนเพาะไม่ถึง$100$แต่ให้เลือกมา$101$ก็เลือกจำนวนเฉพาะที่ไม่เกิน$200$มาให้หมด

แล้วที่เหลือก็จะเป็นจำนวนประกอบซึ่งก็ต้องมีอย่างน้อย1คู่ที่หารกันลงตัวแน่นอน

[Thgx0312555]

ไม่ค่อยเข้าใจ อธิบายให้หน่อยครับ

จำนวนเฉพาะ ตั้งแต่ 1 - 200 มี 47 จำนวน
จะได้ว่าในจำนวนที่เลือกมา 101 จำนวนนั้น
จะมีจำนวนประกอบอย่างน้อย 54 จำนวน

แล้วทำไม ต้องมีบางคู่ใน 54 จำนวนนั้นหารกันลงตัวด้วยครับ
เช่นผมเลือกจำนวนประกอบตั้งแต่ 1 - 200 มา 54 จำนวน ดังนี้

102, 104, ..., 200 ตรงนี้ก็มี 50 จำนวนแล้วใช่ไหมครับ
เลือกมาอีก 4 จำนวน
121, 169, 111, 123

ในบรรดาจำนวนประกอบ 54 จำนวนนี้ไม่มีจำนวนใดหารกันลงตัวเลย

น่าจะเข้าใจผิดอะไรซักอย่าง อธิบายด้วยครับ ขอบคุณครับ

[artty60]

คือจำนวนประกอบที่เลือกมา54จำนวนจะหารด้วยจำนวนเฉพาะบางตัวที่เลือกไว้ก่อนแล้วลงตัวนะครับ

เช่นถ้าเป็นจำนวนคู่จะหาร2ลงตัว ส่วนจำนวนคี่บางตัวก็จะต้องหารจำนวนเฉพาะที่เป็นคี่บางตัวลงตัวใช่มั๊ยครับ

เช่น111หาร3ลงตัว เป็นต้น

[polsk133]

แล้วในกรณีที่เลือกจำนวนเฉพาะน้อยกว่านี้หล้ะครับ อย่างสมมตเลือก 197มาแค่ตัวเดียว

[artty60]

อาจจะเข้าใจผิดกันที่ผมเอาเรื่องจำนวนเฉพาะไปโยงกับของคุณ#2
ตามวิธีของผมหมายถึงยึดเอาจำนวนเฉพาะเป็นสมาชิกตัวแรกของเซตแต่ละเซต
ซึ่งจะมี47เซต แต่ละเซตจะมีจำนวนสมาชิกไม่เท่ากัน สมาชิกตัวอื่นในแต่ละเซตก็จะเป็นจำนวนประกอบ
เช่น{2,4,6,...}{3,9,15,...}{5,25,35,...}{7,49,77,...}{11,121,143,...}...{191}{193}{197}
ตามที่บอกมาเลือก197มาตัวเดียวอีก100จำนวนแต่มี47เซต รวมกับเลข1 เป็น48เซตให้เลือกยังไงก็ต้องมีเลือกบางเซตที่ซ้ำกัน
จึงมีอย่างน้อย1คู่ใน101จำนวนที่เลือกมาที่หารกันลงตัว
หรือจะไม่เลือกจำนวนเฉพาะเลยก็ได้แต่ยังไงจำนวนที่เลือก101จำนวนต้องมีอย่างน้อยหนึ่งจำนวนที่เป็นตัวประกอบของอีกจำนวนหนึ่ง

[Thgx0312555]

เข้าใจแล้วครับ
แต่วิธีนี้ยังติดปัญหาอยู่ตรงที่ว่า 6, 9 หารกันไม่ลงตัวครับ

[artty60]

ผมมาดูวิธีของคุณ#5อีกทีเพิ่งเข้าใจว่าดูผิดไปในตอนแรกต้องขอโทษด้วยครับ

วิธีของคุณเป็นวิธีที่เห็นชัดเจนที่สุดแล้วครับ ขอบคุณครับ

ส่วนวิธีของผมในเซตถัดไปตัวที่ซ้ำกับเซตก่อนหน้าต้องตัดออกพิมพ์เพลินไปหน่อยครับ