pigeonhole principle ครับ

[extreme111]

how many ordered pairs of integers (a,b) are neede to guarantee that there are two ordered pairs (a1,b1)and (a2,b2) such that a1 mod 5= a2 mod5 and b1 mod5 = b2 mod5

มันคิดไงครับมึนนิดๆ

[passer-by]

โดยปกติ ถ้า $ a_i $ ใน mod 5 ซ้ำกัน 6 ตัวแล้ว จะต้องมี $ b_k \equiv b_l \pmod{5}$ แน่นอน เพราะหลังรักนกพิราบ

ดังนั้น จำนวนคู่อันดับ (สมมติเป็น n) ที่การันตีว่า เกิดเหตุการณ์ตามที่โจทย์ถาม จะต้องสอดคล้องกับสมการ $ \left\lceil\, \frac{n}{5}\right\rceil = 6 $

โดย n น้อยสุดที่เป็นไปได้คือ 26

[กระบี่ทะลวงด่าน]

เเค่หกคู่อันดับก็พอไม่ใช่เหรอครับ

[Euler-Fermat]

คู่อันดับ (a,b) ที่เป็นไปได้ ใน mod 5
โดย a $\equiv 0,1,2,3,4$
b $\equiv 0,1,2,3,4 $
ดังนั้น คู่อันดับเกิดได้ทั้งหมด 25 คู่อันดับ
ดังนั้น แค่ 26 คู่อันดับ ก็สามารถการันตีได้ ว่า จะมีคู่อันดับที่ congruence กัน

[กระบี่ทะลวงด่าน]

ลองพิจารณาตัวอย่างของผมนะครับ
(9,1)
(13,4)
(6,5)
(20,3)
(2,7)จากคู่อันดับพวกนี้ไม่ว่าจะสร้างคู่อันดับอะไรเพิ่มอีก1อันโจทย์ก็จะจริงเสมอครับ

[PP_nine]

อันนั้นเป็นการยกตัวอย่างที่ถูกครับ แต่เราต้องการว่ามันถูกทุกกรณี ไม่ใช่กรณีตัวอย่าง

แต่ถ้ายกตัวอย่างที่ผิดมาได้ ข้อความนั้นก็ผิดทันทีครับ เช่น

(1,2)
(2,3)
(3,4)
(4,0)
(0,1)
(1,3)

เท่านี้ก็ทราบแล้วครับว่ามันไม่จริงกับบางกรณี แสดงว่าเลือกอย่างน้อย 6 ไม่จริง

[กระบี่ทะลวงด่าน]

อ๋อ เข้าใจเเล้วครับ. ขอบคุณครับคุณpp nine