โจทย์ข้อนี้มีระดับ มาช่วยกันทำเถอะ

[Catt]

ข้อนี้เป็นข้อสอบในจีน(แต่ไม่ใช่โอลิมปิคของจีน) คล้ายๆกับเป็นข้อสอบใช้สอบประเทศกลุ่มในเครือจีน (ไม่ค่อยเข้าใจเหมือนกัน) และยังได้นำมาใช้เป็นข้อสอบคัดเลือกตัวแทนประเทศไทยด้วย(ปี25xx) จึงน่าลองมาทำกันดู
2. ให้ X = {1,2,3,...,2001} จงหาจำนวนเต็มบวก m ค่าน้อยที่สุดที่มีสมบัติว่า ถ้า W เป็นสับเซตของ X และ W มีสมาชิก m ตัว แล้วจะต้องมี u.v ที่เป็นสมาชิกของ W (u,vอาจเท่ากันได้) ซึ่ง u+v อยู่ในรูป 2^k โดยที่ k เป็นจำนวนเต็มบวก

[TOP]

คิดคร่าวๆได้ตั้ง 999 น้องๆคนอื่นว่าไงครับ ช่วยกันคิดบ้างก็ดี

[eX]

ทำไมเป็น 1 ไม่ได้หรอคับ ก็
W={1} มีสมาชิก 1 ตัว เป็น subset ของ X
ีu =1 v =1
u + v = 2
k = 1

ขออธบายให้น้องeXหน่อย
m จะต้องมีสมบัติที่ว่า ไม่ว่าเลือกตัวใดๆมา m ตัว ก็จะสอดคล้องเงื่อนไขเสมอ
ถ้า m=1 เราเลือก 1 ตัวเดียวแล้วใช้ได้ก็จริง แต่ถ้าเกิดเลือก 5 มาตัวเดียวก็จะใช้ไม่ได้ ดังนั้น m=1 ไม่ได้

[TOP]

นี่เป็นวิธีที่คิดได้คร่าวๆ(ไม่ค่อยจะสวยงามนัก) ยังหาที่ผิดไม่เจอ(จึงยังไม่ได้มองหาวิธีอื่น)
ให้เราจับคู่ของตัวเลขที่ทำให้ได้ผลรวมอยู่ในรูป 2^k ดังนี้

(1,1)
(2,14) , (3,13) , (4,12) , (5,11) , (6,10) , (7,9)
(8,8)
(15,17)
(16,16)
(18,46) , (19,45) , (20,44) , (21,43) , ... , (28,36) , (29,35) , (30,34) , (31,33)
(32,32)
(47,2001) , (48,2000) , (49,1999) , (50,1998) , ... , (1022,1026) , (1023,1025)
(1024,1024)

คู่ของ (1,1) , (8,8) , (16,16) , (32,32) , (1024,1024) ตรงเงื่อนไขในตัวมันเองจึงตัดทิ้ง คงเหลือเพียงคู่ดังต่อไปนี้

(2,14) , (3,13) , (4,12) , (5,11) , (6,10) , (7,9)
(15,17)
(18,46) , (19,45) , (20,44) , (21,43) , ... , (28,36) , (29,35) , (30,34) , (31,33)
(47,2001) , (48,2000) , (49,1999) , (50,1998) , ... , (1022,1026) , (1023,1025)

รวมทั้งสิ้น 998 คู่
\ หากเราเลือกตัวเลขมา 999 ตัว จะต้องมี 2 ตัวใดๆอยู่ใน 998 คู่นี้ หรือไม่ก็มีตัวใดตัวหนึ่งอยู่ใน { (1,1) , (8,8) , (16,16) , (32,32) , (1024,1024) } ซึ่งก็ทำให้สามารถเขียนได้ในรูป 2^k จึงได้ว่า m ณ 999

ต่อไปจะแสดงว่า m > 998
พิจารณาเซ็ตต่อไปนี้
A = { 9 , 10 , 11 , 12 , 13 , 14 }
B = { 17 }
C = { 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 , 43 , 44 , 45 , 46 }
D = { 1025 , 1026 , 1027 , 1028 , ... , 2001 }
หากกำหนดให้ s_XY = สมาชิกของเซ็ตที่เกิดจากการบวกสมาชิก 2 ตัวใดๆของ X และ Y จะพบว่า
16 < 18 ฃ s_AA ฃ 28 < 32
s_BB = 34
64 < 66 ฃ s_CC ฃ 92 < 128
2048 < 2050 ฃ s_DD ฃ 4002 < 4096
16 < 26 ฃ s_AB ฃ 31 < 32
32 < 42 ฃ s_AC ฃ 60 < 64
1024 < 1034 ฃ s_AD ฃ 2015 < 2048
32 < 50 ฃ s_BC ฃ 63 < 64
1024 < 1042 ฃ s_BD ฃ 2018 < 2048
1024 < 1058 ฃ s_CD ฃ 2047 < 2048
จะพบว่าไม่สามารถหาสมาชิก 2 ตัวใดๆใน A ศ B ศ C ศ D ที่ทำให้ผลบวกอยู่ในรูป 2^k และเนื่องจาก จำนวนสมาชิกของ A ศ B ศ C ศ D คือ 998 แสดงให้เห็นว่า m > 998

\ m = 999

[Catt]

ถูกต้องแล้วค่ะ คำตอบคือ 999
ขอเพิ่มนิดนึงนะคะ คิดว่าถ้าจะเขียนให้เข้าใจง่ายขึ้นน่าจะเขียนว่า "กรณีที่มีเลข 1,8,16,32,1024 ใน 999 ตัวที่เลือกมาก็จะสอดคล้องเงื่อนไขตามที่กำหนด ดังนั้นพิจรณากรณีที่ไ่ม่มีเลข 1,8,16,32,1024 ใน 999 ตัวที่เลือกมา นำมาจับคู่ดังนี้ .....(ตามที่คุณTOPทำ)"
ข้อสอบชุดนี้มี 6 ข้อ ข้อนี้เป็นข้อที่ 2 แล้วจะเขียนข้ออื่นให้ลองทำกันอีกนะคะ
ปล.คุณTOP ขยันพิมพ์จริงๆ