ค่ายคัดเลือกคณิตศาสตร์โอลิมปิกครั้งที่ 1(คอมบินาทอริก)

[Tony]

1. ผู้เข้าประชุมมี n คน แต่ละคนเคยดูหนังกับผู้เข้าประชุมเป็นจำนวน 8 คน นอกจากนั้นสองคนใดๆ ที่เคยดูหนงด้วยกันจะมีคนสี่คนที่เคยดูหนังกับคนสองคนนั้น และสองคนใดๆที่ไม่เคยดูหนังด้วยกันจะมีคนทั้งหมดสองคนที่เคยดูหนังกับคนสองคนนั้น ถ้า $n \not= 21$ จงแสดงว่าไม่มีค่า n ที่เป็นไปได้

2. จงหาจำนวนรูปสามเหลี่ยมมุมแหลมที่มากที่สุดที่เป็นไปได้ที่แต่ละจุดยอดมาจากจุด 27 จุดที่อยู่บนวงกลมเดียวกัน

3. แต่ละหลักของบิทสตริง S เป็น 0 หรือ 1 และสตริงย่อยของ S คือเลขที่ติดกันในสตริงนั้น (เช่น 010 เป็นสตริงย่อยของ 1001001) เราใช้สัญลักษณ์ $\Delta (S)$ แทนจำนวนของ 1 ใน S ลบด้วยจำนวนของ 0 ใน S (ตัวอย่างเช่น $\Delta (0010010)= - 3$ ) เรา้เรียกบิทสตริงว่า สมดุลย์ ถ้าทุกสตริงย่อย T ใน S สอดคล้องกับอสมการ $-2\leq \Delta (T) \leq 2$ จงหาจำนวนบิทสตริงสมดุลย์ทั้งหมดที่มี n หลัก

[juju]

กรุณาเฉลย ค่ายคณิตศาสตร์โอลิมปิก ครั้งที่ 1 (คอมบินาทอริก) ขอขอบคุณ

[kanakon]

ข้อความเดิมเขียนโดยคุณ juju

กรุณาเฉลย ค่ายคณิตศาสตร์โอลิมปิก ครั้งที่ 1 (คอมบินาทอริก) ขอขอบคุณ

เท่าที่รู้มามันยากมากนะครับ (ขนาดผู้แทนปีที่แล้วก็ยังไม่มั่นใจเลยครับในบางข้อ)

[dektep]

ข้อความเดิมเขียนโดยคุณ Tony

1. ผู้เข้าประชุมมี n คน แต่ละคนเคยดูหนังกับผู้เข้าประชุมเป็นจำนวน 8 คน นอกจากนั้นสองคนใดๆ ที่เคยดูหนงด้วยกันจะมีคนสี่คนที่เคยดูหนังกับคนสองคนนั้น และสองคนใดๆที่ไม่เคยดูหนังด้วยกันจะมีคนทั้งหมดสองคนที่เคยดูหนังกับคนสองคนนั้น ถ้า $n \not= 21$ จงแสดงว่าไม่มีค่า n ที่เป็นไปได้

2. จงหาจำนวนรูปสามเหลี่ยมมุมแหลมที่มากที่สุดที่เป็นไปได้ที่แต่ละจุดยอดมาจากจุด 27 จุดที่อยู่บนวงกลมเดียวกัน

3. แต่ละหลักของบิทสตริง S เป็น 0 หรือ 1 และสตริงย่อยของ S คือเลขที่ติดกันในสตริงนั้น (เช่น 010 เป็นสตริงย่อยของ 1001001) เราใช้สัญลักษณ์ $\Delta (S)$ แทนจำนวนของ 1 ใน S ลบด้วยจำนวนของ 0 ใน S (ตัวอย่างเช่น $\Delta (0010010)= - 3$ ) เรา้เรียกบิทสตริงว่า สมดุลย์ ถ้าทุกสตริงย่อย T ใน S สอดคล้องกับอสมการ $-2\leq \Delta (T) \leq 2$ จงหาจำนวนบิทสตริงสมดุลย์ทั้งหมดที่มี n หลัก

ข้อ 2. ครับ ตอบ 819 รูปครับ
รูปทั่วไป ถ้า $n$ เป็นจำนวนคู่ $\rightarrow จะมีอย่างมากที่สุด \frac{(n-2)(n)(n+2)}{24}$
ถ้า $n$ เป็นจำนวนคี่ $\rightarrow จะมีอย่างมากที่สุด \frac{(n-1)(n)(n+1)}{24}$
ส่วนวิธีพิสูจน์ค่อนข้างยาวครับ แล้วจะเอามาลงวันหลังครับ

[paoboy]

พี่dektepตกลงทำยังไงครับ

[dektep]

ข้อนี้เป็นโจทย์ Romania TST 1999 ครับ

Reference:mathematics problem around the world 1999-2000

[paoboy]

ขอบคุณครับพี่

[Anonymous314]

รบกวนท่าน ๆ ขอวิธีทำด้วยครับผม ข้อ 1 กับ 3 อะครับ

[passer-by]

ข้อ 3 ลองดูใน
PUTNAM 1996

ส่วนข้อ 1 ใช้ double counting ครับ
ถ้าทำมาถูกทาง สุดท้าย จะได้สมการ $ 2(n-9)= (3)(8)$

[RoSe-JoKer]

ข้อหนึ่งให้ $S((a_i,a_j),a_k) $เป็นจำนวนของเซตที่หมายความว่า $a_k$ ได้ดูหนังกับ $a_i,a_j$ ทั้งคู่
นับทางแรก $S((a_i,a_j),*)$
จากเงื่อนไขเห็นได้ว่าจะมี 4n คู่ที่ดูหนังด้วยกัน ดังนั้นจึงมีคน $\binom{n}{2}-4n$ คู่ที่ไม่ได้ดูหนังด้วยกันดังนั้นจากเงื่อนไขที่โจทย์กำหนดเราจึงได้ว่า
$|S|=4(4n)+2(\binom{n}{2}-4n)$
นับทางที่สอง $S(*,a_k)$
สำหรับคนแต่ละคนเรามีวิธีเลือกคู่ให้ดูหนังได้ด้วยกัน
$\binom{8}{2}n$ วิธีดังนั้นเราได้ว่า
$4(4n)+2(\binom{n}{2}-4n) =\binom{n}{2}n$
นั้นคือ
$n(n-21)=0$
แสดงว่ามี $n= 21$ เท่านั้นที่สอดคล้องกับเงื่อนไขแต่จากที่โจทย์บอกว่า n!=21 ดังนั้นเราจึงได้ว่าจัดกลุ่มไม่ได้ตามต้องการ

[God Phoenix]

คุณ Rose Joker เก่งจังเลยครับ
ยกย่องๆ