ปัญหา Combinatorics กราฟที่สนุกและท้าทาย
มีปัญหาที่ฉันดิ้นรนมาระยะหนึ่งแล้วและดูเหมือนจะไม่พบหนทางแก้ไขที่ถูกต้อง
ปัญหา: มีการสอบ $5$ คำถามปรนัยกับ $4$ทางเลือกแต่ละอย่าง นักเรียน 2,000 คนเข้าสอบแต่ละคนตอบคำถามทั้ง 5 ข้อ จะพบว่า$(*)$ สำหรับใด ๆ $n$ คุณสามารถหาเอกสารการสอบได้ $4$ เอกสารดังกล่าวใด ๆ $2$ เอกสารมีมากที่สุด $3$คำตอบเดียวกัน ค้นหาสิ่งที่เล็กที่สุด$n$.
สิ่งที่ฉันมี: มี $1024$สามารถตอบข้อสอบได้หลายวิธี ก่อนอื่นให้ค้นหาหมายเลข$m$ ของเอกสารต่างๆจากไฟล์ $1024$ ทรัพย์สินดังกล่าว $(*)$ พอใจแล้วหาขั้นต่ำ $n$ การสอบจาก $2000$ เอกสารการสอบที่จะรวมถึง $m$คำตอบข้อสอบที่แตกต่างกัน ฉันลองกำหนดเป็นกราฟแล้วข้อสอบสองประเภทจะเชื่อมต่อกันหากแตกต่างกันเท่านั้น$1$ คำตอบจากนั้นข้อสอบแต่ละประเภทจะเชื่อมต่อกันทุกประการ $15$อื่น ๆ แล้วพยายามใช้อสมการเพื่อผูกจำนวน$m$แต่มันไม่ได้ผล วิธีแก้คือ$n=25$ ซึ่งฉันเชื่อว่าหมายถึง $m=13$.
ยินดีต้อนรับคำแนะนำหรือวิธีแก้ปัญหาใด ๆ ขอบคุณ.
คำตอบ
ผมคิดว่าโดย "เล็กที่สุด $n$"เราหมายถึง" ที่เล็กที่สุด $n$ ซึ่งเป็นไปได้ $(*)$ ค้างไว้ "- เพื่อให้เราเลือก $2000$ข้อสอบตามที่เราชอบ ในกรณีที่แย่ที่สุดของเอกสารการสอบ$(*)$ จะไม่ยึดมั่นใด ๆ $n$: กรณีที่เลวร้ายที่สุดคือทั้งหมด $2000$ นักเรียนให้คำตอบเดียวกันทั้งหมด
ในการเลือกข้อสอบด้วยวิธีที่ดีที่สุดก็เพียงพอที่จะตรวจสอบให้แน่ใจว่าได้รับคำตอบทุกชุดไม่เกินสอง ถ้าอย่างนั้นคุณคิดถูกแล้ว$n=25$ การสอบมีชุด $m=13$ การสอบที่แตกต่างกัน
สมมติว่าไฟล์ $4$ ตัวเลือกสำหรับแต่ละคำถามจะถูกกำหนดหมายเลข $0, 1, 2, 3$. กำหนดค่ากระดาษข้อสอบแต่ละชุดโดยการบวกตัวเลขสำหรับโมดูลคำตอบทั้งหมด$4$. จากนั้นเอกสารการสอบสองฉบับที่มีค่าเท่ากันอาจมีคำตอบเหมือนกันทั้งหมดหรืออย่างน้อยก็ไม่เห็นด้วย$2$ คำตอบ
มีเพียง $4$ ค่าที่เป็นไปได้สำหรับการสอบดังนั้นในชุดใดก็ได้ $m=13$ การสอบที่แตกต่างกันมี $\lceil \frac m4\rceil = 4$การสอบที่มีค่าเดียวกัน เหล่านี้เป็น$4$ การสอบที่เราต้องการหา
มีการก่อสร้างทางเลือก สมมติว่าไฟล์$2000$ นักเรียนทุกคนให้คำตอบอย่างมีคุณค่า $0$ (โดยโมดูโลเดียวกัน $4$ กฎข้างต้น) และเราแจกจ่ายคำตอบของพวกเขาอย่างเท่าเทียมกันเพื่อให้แต่ละชุด $256$ จะได้รับคำตอบอย่างใดอย่างหนึ่ง $7$ หรือ $8$ครั้ง. แล้วในบรรดา$25$ เอกสารการสอบต้องมีอย่างน้อย $4$ชุดคำตอบที่แตกต่างกัน สิ่งเหล่านี้สามารถเป็นชุดของเราได้$4$: เนื่องจากพวกเขาทั้งหมดมีค่า $0$แตกต่างกันอย่างน้อยสองแห่ง
เราควรแสดงให้เห็นด้วยว่าไม่ว่านักเรียนจะตอบคำถามอะไรก็ตาม $(*)$ ไม่สามารถถือได้ $n=24$.
หากต้องการดูสิ่งนี้ให้จัดกลุ่มเอกสารการสอบเป็น $256$จัดกลุ่มตามคำตอบสี่ข้อแรก จำนวนการสอบเฉลี่ยในกลุ่มคือ$\frac{2000}{256} = 7.8125$ดังนั้นจำนวนการสอบเฉลี่ยในสามกลุ่มคือ$\frac{6000}{256} = 23.4375$. ดังนั้นจึงมีกลุ่มสามกลุ่มที่มีค่าเฉลี่ยนี้เป็นอย่างน้อย: อย่างน้อย$24$ การสอบ
ทำข้อสอบจากทั้งสามกลุ่ม แล้วใด ๆ$4$ในจำนวนนี้มีการสอบสองครั้งจากกลุ่มเดียวกัน ดังนั้นใด ๆ$4$ ของพวกเขามีการสอบสองข้อที่แตกต่างกันในคำตอบมากที่สุดหนึ่งคำตอบและ $(*)$ ไม่ถือสำหรับ $n=24$.