|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
|||
|
|||
โจทย์ข้อนี้มีระดับ มาช่วยกันทำเถอะ
ข้อนี้เป็นข้อสอบในจีน(แต่ไม่ใช่โอลิมปิคของจีน) คล้ายๆกับเป็นข้อสอบใช้สอบประเทศกลุ่มในเครือจีน (ไม่ค่อยเข้าใจเหมือนกัน) และยังได้นำมาใช้เป็นข้อสอบคัดเลือกตัวแทนประเทศไทยด้วย(ปี25xx) จึงน่าลองมาทำกันดู
2. ให้ X = {1,2,3,...,2001} จงหาจำนวนเต็มบวก m ค่าน้อยที่สุดที่มีสมบัติว่า ถ้า W เป็นสับเซตของ X และ W มีสมาชิก m ตัว แล้วจะต้องมี u.v ที่เป็นสมาชิกของ W (u,vอาจเท่ากันได้) ซึ่ง u+v อยู่ในรูป 2^k โดยที่ k เป็นจำนวนเต็มบวก |
#2
|
||||
|
||||
คิดคร่าวๆได้ตั้ง 999 น้องๆคนอื่นว่าไงครับ ช่วยกันคิดบ้างก็ดี
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson. |
#3
|
|||
|
|||
ทำไมเป็น 1 ไม่ได้หรอคับ ก็
W={1} มีสมาชิก 1 ตัว เป็น subset ของ X ีu =1 v =1 u + v = 2 k = 1 |
#4
|
|||
|
|||
ขออธบายให้น้องeXหน่อย
m จะต้องมีสมบัติที่ว่า ไม่ว่าเลือกตัวใดๆมา m ตัว ก็จะสอดคล้องเงื่อนไขเสมอ ถ้า m=1 เราเลือก 1 ตัวเดียวแล้วใช้ได้ก็จริง แต่ถ้าเกิดเลือก 5 มาตัวเดียวก็จะใช้ไม่ได้ ดังนั้น m=1 ไม่ได้ |
#5
|
||||
|
||||
นี่เป็นวิธีที่คิดได้คร่าวๆ(ไม่ค่อยจะสวยงามนัก) ยังหาที่ผิดไม่เจอ(จึงยังไม่ได้มองหาวิธีอื่น)
ให้เราจับคู่ของตัวเลขที่ทำให้ได้ผลรวมอยู่ในรูป 2k ดังนี้ (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) } ซึ่งก็ทำให้สามารถเขียนได้ในรูป 2k จึงได้ว่า 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 } หากกำหนดให้ sXY = สมาชิกของเซ็ตที่เกิดจากการบวกสมาชิก 2 ตัวใดๆของ X และ Y จะพบว่า 16 < 18 ฃ sAA ฃ 28 < 32 sBB = 34 64 < 66 ฃ sCC ฃ 92 < 128 2048 < 2050 ฃ sDD ฃ 4002 < 4096 16 < 26 ฃ sAB ฃ 31 < 32 32 < 42 ฃ sAC ฃ 60 < 64 1024 < 1034 ฃ sAD ฃ 2015 < 2048 32 < 50 ฃ sBC ฃ 63 < 64 1024 < 1042 ฃ sBD ฃ 2018 < 2048 1024 < 1058 ฃ sCD ฃ 2047 < 2048 จะพบว่าไม่สามารถหาสมาชิก 2 ตัวใดๆใน A ศ B ศ C ศ D ที่ทำให้ผลบวกอยู่ในรูป 2k และเนื่องจาก จำนวนสมาชิกของ A ศ B ศ C ศ D คือ 998 แสดงให้เห็นว่า m > 998 \ m = 999
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson. 19 ตุลาคม 2001 18:50 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ TOP |
#6
|
|||
|
|||
ถูกต้องแล้วค่ะ คำตอบคือ 999
ขอเพิ่มนิดนึงนะคะ คิดว่าถ้าจะเขียนให้เข้าใจง่ายขึ้นน่าจะเขียนว่า "กรณีที่มีเลข 1,8,16,32,1024 ใน 999 ตัวที่เลือกมาก็จะสอดคล้องเงื่อนไขตามที่กำหนด ดังนั้นพิจรณากรณีที่ไ่ม่มีเลข 1,8,16,32,1024 ใน 999 ตัวที่เลือกมา นำมาจับคู่ดังนี้ .....(ตามที่คุณTOPทำ)" ข้อสอบชุดนี้มี 6 ข้อ ข้อนี้เป็นข้อที่ 2 แล้วจะเขียนข้ออื่นให้ลองทำกันอีกนะคะ ปล.คุณTOP ขยันพิมพ์จริงๆ |
|
|