ข้อสอบ 4th TMO ณ ร.ร.เตรียมทหาร

[Mathophile]

เพื่อความสะดวกในการดูข้อสอบ ขออนุญาตตั้งกระทู้ใหม่สำหรับข้อสอบครั้งนี้ครับ
----------
การแข่งขันคณิตศาสตร์โอลิมปิก สอวน. ครั้งที่ 4
วันที่ 4-9 พฤษภาคม 2550
----------

[Mathophile]

ข้อสอบวันที่สอง
----------
1. จงหาฟังก์ชัน $f:R \rightarrow R$ ทั้งหมดซึ่ง
$$\sum_{i=1}^{2549}f(x_i+x_{i+1})+f(\sum_{i=1}^{2550}x_i)\leq \sum_{i=1}^{2550}f(2x_i)$$สำหรับทุกจำนวนจริง $x_1,x_2,...,x_{2550}$

2. นักเรียนหญิง $n$ คนและนักเรียนชาย $n$ คนในชั้น ม.1/1 อยู่ในงานปาร์ตี้ที่มีการเต้นรำแห่งหนึ่ง ในแต่ละเพลง จะมีนักเรียนชายหญิงจับคู่ขึ้นไปเต้นรำอย่างน้อยหนึ่งคู่ นักเรียนทุกคนที่ขึ้นไปเต้นรำจะได้รับพวงมาลัยคนละหนึ่งพวงเมื่อจบเพลงเสมอ ถ้ามีการเต้นรำทั้งหมด $m$ เพลง
จงแสดงว่าสำหรับทุกจำนวนนับ $k\leq n$ จะต้องมีกลุ่มนักเรียนที่ประกอบด้วยชาย $k$ คนและหญิง $n-k$ คนซึ่งได้รับพวงมาลัยรวมกันอย่างน้อย $m$ พวง

3. วงกลมสองวงตัดกันที่จุด $X$ และ $Y$ เส้นตรงที่ผ่านจุดศูนย์กลางของวงกลมทั้งสองตัดวงกลมแรกที่จุด $A$ และ $C$ และตัดวงกลมที่สองที่จุด $B$ และ $D$ โดยที่จุด $B$ อยู่บนส่วนของเส้นตรง $AC$ และจุด $C$ อยู่บนส่วนของเส้นตรง $BD$ คอร์ดร่วม $XY$ ตัด $BC$ ที่จุด $P$ ให้จุด $O$ เป็นจุดใด ๆ บน $XP$ ที่อยู่ระหว่าง $X$ กับ $P$ ต่อ $CO$ พบวงกลมแรกที่จุด $M$ และต่อ $BO$ พบวงกลมที่สองที่จุด $N$ ต่อ $AM$ และ $DN$ ออกไปพบกันที่ $Z$ จงพิสูจน์ว่า $X,Y$ และ $Z$ อยู่บนเส้นตรงเดียวกัน

4. จงหาจำนวนเฉพาะ $p$ ทั้งหมดที่ทำให้ $\displaystyle{\frac{2^{p-1}-1}{p}}$ เป็นกำลังสองสัมบูรณ์

5. ชั้น ม.1 มีนักเรียนชาย 229 คนและนักเรียนหญิง 271 คน แบ่งเป็น 10 ห้อง ห้องละ 50 คน นักเรียนแต่ละห้องมีเลขที่ 1 ถึง 50 ครูต้องการจัดทีมวิ่งผลัดหนึ่งทีม โดยมีนักเรียนหญิง 1 คนและชาย 3 คน หรือนักเรียนหญิง 3 คนและชาย 1 คน และมีเงื่อนไขเพิ่มเติมว่านักเรียนสี่คนนี้มาจากสองห้อง ห้องละสองคนที่มีเลขที่ตรงกัน (เช่น นักเรียนเลขที่ 2 และ 15 จากห้อง ม.1/1 และ ม.1/3)
จงแสดงว่ามีวิธีตั้งทีมวิ่งผลัดเป็นจำนวนคี่

6. รูปสามเหลี่ยมรูปหนึ่งมีเส้นรอบรูปยาว $2s$ ถ้าวงกลมแนบในมีรัศมี $r$ และระยะจากจุดศูนย์กลางวงกลมแนบในไปยังจุดยอดทั้งสามเป็น $s_a,s_b$ และ $s_c$ แล้วจงแสดงว่า
$$\frac{3}{4}+\frac{r}{s_a}+\frac{r}{s_b}+\frac{r}{s_c}\leq \frac{s^2}{12r^2}$$

----------
เฉลย
ข้อสอบวันแรก
ข้อ 7,8
ข้อ 10
ข้อ 12
ข้อ 15
ข้อ 17
ข้อสอบวันที่สอง
ข้อ 3
ข้อ 6 (วิธีที่ 1) (วิธีที่ 2)

ปล. ข้อที่ยังไม่ได้ทำลิงค์คือข้อที่ยังไม่มีคนทำหรือยังทำไม่ถูกต้อง(ในกระทู้เก่า)ครับ
(ยกเว้นข้อ 1 วันที่สอง ให้ติดตามอ่านได้ในกระทู้เก่านะครับ เพราะมีหลายโพสต์พอสมควร)

[kanakon]

ข้อ 2 วันแรก

[[Tong]_1412]

ขอทำข้อ 4 วันที่ 2 ก่อนละกันครับ

[nongtum]

ผมคิดข้อ 9 ได้ไม่ตรงกับที่คุณ gon แปะไว้ในกระทู้เดิม คือคิดได้ 167 ดังนี้ครับ

เริ้มจากการทดสอบง่ายๆ สมมติว่าฟังก์ชันนี้เป็นสมการพหุนามกำลัง $n$ โดยไม่เสียนัย เราจะเช็คเงื่อนไขจาก $f(x)=x^n$
ซึ่งจะพบว่า $f(y^2)-2f(y^2)=y^{2n}$ มีดีกรีสูงสุดเป็นสองเมื่อ $n=1$ ดังนั้นจะสมมติให้ $f(x)=Ax+B$
แทน $x=0,1$ ในสมการโจทย์ จะได้ $f(3)+2f(5)=17,\ 2f(3)+f(5)=13$ นั่นคือ $f(3)=3,\ f(5)=7$
แทน $x=3,5$ ในสมการที่สมมติไว้แล้วแก้หา $A,B$ จะได้ $A=2,\ B=-3$ ตรวจสอบกับสมการโจทย์พบว่าสอดคล้อง
ดังนั้น $f(85)=2(85)-3=167$

[passer-by]

ขอเคลียร์ฺข้อที่พิมพ์สั้นๆก่อนนะครับ

GEOMETRY (วาดรูปเองนะครับ ไม่ซับซ้อนมาก แต่ถ้าคิดเลขผิดก็บอกด้วยนะ)

1. เขียน AC, OD ในเทอมของรัศมีวงกลม จะได้ $ \sqrt{3} r - \frac{\sqrt{3}r}{2}= 2 $ ดังนั้น AC ยาว 4 หน่วย

3. หามุมในสามเหลี่ยมมุมฉากจากตรีโกณ ม.ต้น จากนั้น ก็ลากเส้นผ่าน center ทั้ง 2 วง ซึ่งจะไปแบ่งครึ่งมุม 60 องศาในสามเหลี่ยมพอดิบพอดี แล้วก็ไล่หาด้านไปเรื่อยๆ จะได้ รัศมีวงที่สอง เท่ากับ $ \frac{1}{3}$ หน่วย

4. จากอัตราส่วนของพื้นที่สามเหลี่ยม พบว่า $ \frac{AM}{MB} =\frac{1}{1}= \frac{16 \sin \theta_1}{12 \sin \theta_2}$

ในขณะเดียวกัน $ \frac{EG}{GF} =\frac{3 \sin \theta_1}{ \sin \theta_2}$

จาก 2 สมการนี้ สรุปได้ว่า EG:GF = 9:4

5. ให้ มุม C กาง $\theta $ และ AD ยาว x หน่วย ดังนั้น $ \frac{2}{2+x}= \cos \theta $
ขณะเดียวกัน $ \frac{x}{2}= \cos 2\theta = 2\cos^2 \theta -1 = 2(\frac{2}{2+x})^2 -1$

แล้วก็แก้สมการหาค่า $x+2 $ ซึ่งก็คือความยาว AC พบว่า เท่ากับ $ 2^{\frac{4}{3}}$ หน่วย

6. (ข้อนี้น่าสนใจดีครับ)
วาดวงกลมล้อมรอบสามเหลี่ยม MAC
สังเกตได้ว่า มุม ABC จะใหญ่สุด เมื่อ AB สัมผัสวงกลมพอดี (ลองวาดรูปดูเองนะครับ) และ เมื่อ AB เป็น tangent จะได้ $ \frac{BC}{BA}= \sqrt{2}$ โดยใช้ ทฤษฎีที่บอกว่่า $AB^2= MB \cdot BC $

ALGEBRA

9. จริงๆพี่ gon ลอกโจทย์ผิดน่ะครับ ไม่งั้นคำตอบก็ถูกแน่นอน

ผมแปะอีกวิธีแล้้วกัันครับ

ขั้นแรก เป็น optional step ครับ คือ จะทำหรือไม่ทำก็ได้ (ถ้าทำก็จะคิดเลขสะดวกขึ้น)

สังเกตว่า $ 6x^2-10x+17= 4(x^2-3x+5)+2(x^2+x+3)-9 $

ขั้้นที่ 2 : set ค่าให้ $x^2-3x+5=85 $ ดังนั้น
$ f(89\pm 2 \sqrt{329}) +2f(85) = 331 + 2(89\pm 2 \sqrt{329}) \cdots(1)$

จากนั้น ก็ set ให้ $x^2+x+3=85 $ ดังนั้น
$ f(85)+ 2f(89\pm 2 \sqrt{329}) = 4(89\pm 2 \sqrt{329})+161 \cdots(2)$

ขั้นที่ 3: แก้สมการหาค่า f(85) ซึ่งจะเท่ากับ 167 ครับ

COMBINATORICS

14. ผม generalize เลยแล้วกัันครับ

$$ \sum_{k=r}^{n-r} \binom{k}{r} \binom{n-k}{r} =\binom{n+1}{2r+1} $$

ส่วนคำอธิบายแบบ combinatorial นี่พูดยากแฮะ แต่จะพยายามครับ

สมมติมีเลข 1 ถึง n+1 แล้วเลือกมา 2r+1 จำนวนครับ โดยเมื่อเขียนเรียงจากน้อยไปมาก ให้ยึดตัวที่ r+1 ไว้ครับ(สมมติเป็นเลข k+1) จากนั้นจะเกิดเลข 2 ฝั่ง ฝั่งละ r จำนวน
มองอีกแง่หนึ่ง พบว่า r ตัวแรก เลือกมาจาก 1 ถึง k ด้วยวิธีเลือก $ \binom{k}{r}$ ซึ่งส่งผลให้ r ตัวหลัง จะมีวิธีเลือก $ \binom{n-k}{r}$ แล้วก็จะได้ identity ข้างต้นครับ

ดังนั้น ข้อนี้ตอบ $ \binom{8085}{169}$

ปล. ข้อ 13 กับ 18 ดูอึดๆดีจัง ไม่ทราบว่า ข้อ 13 ตอบ 4100 และข้อ 18 ตอบ 1273 หรือเปล่าครับ

[Mathophile]

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

ปล. ข้อ 13 กับ 18 ดูอึดๆดีจัง ไม่ทราบว่า ข้อ 13 ตอบ 4100 และข้อ 18 ตอบ 1273 หรือเปล่าครับ

ข้อ 13 ยังไม่ถูกครับ แต่ข้อ 18 ถูกแล้ว
ข้อ 13 ไม่อึดอย่างที่คิดครับ มันจะมีทริคในการมองอยู่นิด ๆ ครับ (คล้าย ๆ กับข้อนึงใน สอวน. ครั้งที่ 3 ครับ)

[[Tong]_1412]

ข้อ 13 ถ้าเดา ก็คงใช้ หลักการเพิ่มเข้า และตัดออกรึป่าวคับ โดยพิจารณาจะเซตใด ๆ สองเซตที่ไม่มีสมาชิกรวมกัน

[passer-by]

ขอคั่นด้วยผลการแข่งขัน 4th POSN-MO ที่เพิ่งผ่านไปนะครับ
RESULT

ส่วนข้อ 13 ตกลงเป็น 3600 หรือเปล่าครับ (ตอนแรก ผมบวกเลขผิดนิดหน่อย) และสำหรับใครที่มีเฉลยในมือ ก็สามารถเสนอแนะหรือเช็คคำตอบข้อที่ทำไปแล้วด้วยนะครับ เผื่อมีข้อผิดพลาด

ส่วนใครจะ clear ข้อที่เหลือ ก็ตามสบายเลยนะครับ รู้สึกจะมีแต่ combinatorics อย่างเดียวที่ตกค้างอยู่

[Mathophile]

สงสัยวิธีทำข้อ 4 วันที่ 2 ของคุณ [Tong]_1412 นิดนึงครับว่าทำไมถึงบอกว่า
" เนื่องจาก $2^{\frac{p-1}{2}}-1$ เป็นจำนวนคี่ จึงมีค่า k ที่สอดคล้องเพียงค่าเดียวคือ $k=1$ "

Alternative Solution (<< ขอยืมคำนี้มาใช้หน่อยนะครับ )
ข้อ 7. ใช้ symmetric polynomial
ให้ $\sigma_1=a+b+c,\sigma_2=ab+bc+ca,\sigma_3=abc,S_n=a^n+b^n+c^n$
จะได้ $S_n=\sigma_1S_{n-1}-\sigma_2S_{n-2}+\sigma_3S_{n-3}$ เมื่อ $n=3,4,5,...$ (พิสูจน์ได้โดยการแทนค่า )
แทนค่าตามโจทย์จะได้ $S_4=\sigma_1S_3-\sigma_2S_2+\sigma_3S_1=3-2(ab+bc+ca)+abc...(*)$
พิจารณา $ab+bc+ca=\frac{1}{2}((a+b+c)^2-(a^2+b^2+c^2))=-\frac{1}{2}$
และ $a^3+b^3+c^3-3abc=(a+b+c)(a^2+b^2+c^2-ab-bc-ca)$
$3-3abc=(1)(2-(-\frac{1}{2}))\Longrightarrow abc=\frac{1}{6}$
แทนค่ากลับใน $(*)$ จะได้ $a^4+b^4+c^4=S_4=\frac{25}{6}$

ข้อ 8. สมมติให้ $y=x-1$ ฉะนั้น
$$\sum_{k=1}^{84}\frac{x_k}{x_k-1}=\sum_{k=1}^{84}\frac{y_k+1}{y_k}=\sum_{k=1}^{84}(1+\frac{1}{y_k})=84+\frac{(-สปส. y)}{สปส. y^0}$$
(โดย Vieta's Formulas)
แทน $x=y+1$ ในโจทย์จะได้ $0=(y+1)^{84}+7(y+1)-6=y^{84}+...+84y+1+7y+7-6=y^{84}+...+91y+2$
$$\therefore \sum_{k=1}^{84}\frac{x_k}{x_k-1}=84-\frac{91}{2}=\frac{77}{2}$$
ข้อ 9. อีกวิธีนึงคือ (วิธีนี้เห็นจากเฉลย ) แทน $x$ ด้วย $1-x$ ครับ (...แล้วใครจะมองออกล่ะนี่)

ปล. พี่ passer-by ช่วยแสดงวิธีคิดข้อ 18 ที่พี่ใช้ให้ดูหน่อยครับ (ข้อ 13 ไม่ใช่ 3600 ครับ)

HINT ข้อ 13

วาดแผนภาพเซต 2 เซต (หลักเพิ่มเข้าตัดออก อาจจะได้ใช้นิดหน่อยครับ)

[passer-by]

ข้อ 13 ตอบ 3025 (ไม่น่าจะผิดแล้วมั้งครับ)

งั้นผมขอแสดงวิธีทำ 2 วิธีของข้อนี้ให้ดูล่ะกัน

(1) วิธีตรง
เลือกเลขอย่างน้อย 2 ตัวออกมา แล้วนำมา partition เป็น 2 sets ซึ่งจะได้คำตอบเท่ากับ

$\binom{8}{2} + \binom{8}{3}(\binom{3}{1}) +\binom{8}{4}(\binom{4}{1} +\frac{\binom{4}{2}}{2} ) +\binom{8}{5}(\binom{5}{1} +\binom{5}{2})+\binom{8}{6}(\binom{6}{1} +\cdots \frac{\binom{6}{3}}{2}) + \binom{8}{7}(\binom{7}{1} +\cdots \binom{7}{3}) +\binom{8}{8}(\binom{8}{1} +\cdots \frac{\binom{8}{4}}{2}) $

ลองคิดดูนะครับ ว่าทำไมบางอันมีหารสอง แต่บางอันไม่มี

(2) วิธีลัด (inspired by N' Mathophile)

นึกถึงวงกลม 2 วง เหลื่อมกันครับ จะเห็นว่ามี 3 บริเวณ โดยเราจะบรรจุ 1 ถึง 8 ลงไปใน 3 บริเวณนี้ครับ โดยจะเห็นว่าเลข 1 ตัวมีวิธีเลือกบริเวณได้ 3 วิธี ดังนั้นคำตอบข้อนี้เทียบเท่ากับ วิธีการวางเลข 8 ตัวลงไปใน 3 บริเวณโดย มีเลขเต็มทั้ง 3 บริเวณ หรือ ตรงกลางว่างช่องเดียวเท่านั้น ซึ่งมี $ \frac{3^8-3-2(2^8-2)}{2}=3025$ วิธี

Note: ในกรณีที่เลขเต็มทั้ง 3 บริเวณหรือตรงกลางว่าง จะเห็นว่าการอ่านเลขในบริเวณซ้าย ขวา ก็คือ 2 สับเซตที่ต้องการครับ


ส่วนข้อ 18 ผมก็ทำแบบทื่อๆเลยครับ เพราะ number theory กับผม ไม่ค่อยถูกกันเท่าไหร่
่
หลักการคร่าวๆก็คือ ใช้สมบัติของ modulo ร่วมกับ ทฤษฎีบทแฟร์มาต์ และ พิจารณา ตัวหารของ $ p^4-1$ครับ จนได้ว่า

$ sum \equiv 1 \pmod{6} $
$ sum \equiv 23 \pmod{25} $
$ sum \equiv 15 \pmod{17} $

แล้วก็ใช้ Chinese remainder theorem ปกติเลยครับ

Note : $ 2550 = 6 \cdot 25 \cdot 17 $

[Mathophile]

ข้อ 13 ถูกต้องแล้วครับ ตอบ 3025
ข้อที่ยังไม่ได้เฉลย : วันแรก ข้อ 11,16 วันที่สอง ข้อ 2,5
(รู้สึกว่าข้อ 16 จะมีโพสต์คำตอบที่ถูกต้องแล้ว แต่ยังไม่วิธีทำแบบเป็นทางการน่ะครับ)

[[Tong]_1412]

ตอบคุณ Mathophile สำหรับข้อ 2 นะครับ

พิจารณา 2x($2^{\frac{p-1}{2}}-1$)= (k+1)(k-1) ถ้า k เป็นจำนวนนับใด ๆ
1. ถ้า k เป็นจำนวนคู่ (k+1)(k-1) จะเป็นจำนวน คี่คูณกันซึ่งไม่เท่ากับจำนวนคู่แน่นอนยกเว้น k = 1
2. ถ้า k เป็นจำนวนคี่ (k+1)(k-1) จะกลายเป็น จำนวนคู่คูณกัน ซึ่งเท่ากับ 2x($2^{\frac{p-1}{2}}-1$)
ซึ่ง $2^{\frac{p-1}{2}}-1$ เป็นจำนวนคี่ ไม่มีโอกาสเป็นจำนวนคู่ได้เด็ดขาดคับ ยกเว้นเป็น 0 กรณีเดียว

นั่นก็คือมีกรณีที่เป็นไปได้เพียง k=1 เพียงกรณีเดียวครับ

[[Tong]_1412]

อ่อ คุณ Mathophile มีข้อ 4 วันที่สองฉบับเฉลยไหมครับ ถ้าไม่เป็นการรบกวนขอเฉลยลงบอร์ดได้ไหมครับ

[passer-by]

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

5. ชั้น ม.1 มีนักเรียนชาย 229 คนและนักเรียนหญิง 271 คน แบ่งเป็น 10 ห้อง ห้องละ 50 คน นักเรียนแต่ละห้องมีเลขที่ 1 ถึง 50 ครูต้องการจัดทีมวิ่งผลัดหนึ่งทีม โดยมีนักเรียนหญิง 1 คนและชาย 3 คน หรือนักเรียนหญิง 3 คนและชาย 1 คน และมีเงื่อนไขเพิ่มเติมว่านักเรียนสี่คนนี้มาจากสองห้อง ห้องละสองคนที่มีเลขที่ตรงกัน (เช่น นักเรียนเลขที่ 2 และ 15 จากห้อง ม.1/1 และ ม.1/3)
จงแสดงว่ามีวิธีตั้งทีมวิ่งผลัดเป็นจำนวนคี่

ขั้นแรก ผมมองเป็น BIPARTITE GRAPH ก่อนครัับ โดยสมมติให้ ซ้ายมือแทน จุดของเลขห้อง (1-10) และขวามือ แทนจุดของ เลขที่ (1-50)

ถ้าห้อง x เลขที่ y เป็นผู้หญิง ให้ลากเส้นเชื่อม ดังนั้นกราฟนี้จะมี 271 เส้นเชื่อม และการไม่มีเส้นเชื่อมมายังอีกฝั่ง ก็บ่งบอกให้้รู้ว่า เลขที่นั้นเป็นเพศชาย

พิจารณา subgraph 4 จุดยอด โดย 2 จุดมาจากซ้าย และอีก 2 จุดมาจากขวา แล้วแตกออกมา 5 กรณี คือไม่มีเส้นเชื่อมเลย , มี 1 เส้น , มี 2เส้น ไปจนกระทั่งมี 4 เส้น แล้วนับดูครับว่า แต่ละกรณีมีกี่ subgraph ที่เป็นไปได้ สมมติว่านับได้ $ a_0, a_1 ,\cdots a_4 $ ตามลำดับ

ต่อไปเราจะนับผลรวมของ (จำนวนเส้น คูณ จำนวน subgraph ที่สัมพันธ์กััน) หรือแทนด้วย $\sum_{k=0}^4 k\cdot a_k $

นับแบบที่่่ 1 จาก summation โดยตรง จะได้ $ a_1 + 2a_2 + 3a_3 + 4a_4 $

นับแบบที่ 2 : เนื่่องจาก 1 เส้นเชื่่อม จะถูกนับ (50-1)(10-1) ครั้ง เท่ากับว่า 271 เส้น จะถูกนับ 271(49)(9) ซึ่งเป็นเลขคี่ี่

ดังนั้น $ a_1 + 2a_2 + 3a_3 + 4a_4 $ เป็นเลขคี่ และส่งผลให้ $ a_1+ a_3 $ เป็นเลขคี่ และเท่ากับจำนวนวิธีตั้งทีมวิ่งผลัดพอดี

สาเหตุเพราะว่า $a_1$ คือจำนวน subgraph ดังกล่าวที่มี 1 เส้นเชื่อม (เทียบเท่ากับ หญิง 1 ชาย 3) และ $a_3$ คือจำนวน subgraph ดังกล่าวที่มี 3 เส้นเชื่อม (เทียบเท่ากับ หญิง 3 ชาย 1)

ป.ล. ข้อ 2 ตอนที่ 2 นี่มันคุ้นๆจัง แต่นึกไม่ออก ไม่แน่ใจว่าต้องใช้ contradiction หรือเปล่า