Shortlist 6th TMO 2009 <MWIT> [full version]

[Noviceboy]

ยากจัง ผมจะทำให้ได้

[Amankris]

ไม่รู้ยังมีคนตามดูอยู่ไหมนะ

ข้อ 7 วันแรก (ข้อนี้ผมว่าหลงทางได้ง่ายที่สุดแล้ว = =')

ให้ $a,b,c\in\mathbf{R}$ กำหนด $S_n=a^n+b^n+c^n$ ทุกจำนวนนับ $n$
ถ้า $S_1,S_2,S_3$ เป็นจำนวนเต็มซึ่ง $6\mid5S_1-3S_2-2S_3$ แล้ว
จงแสดงว่า $S_n$ เป็นจำนวนเต็ม ทุกจำนวนนับ $n$

Solution

Step1. $ab+bc+ca\in\mathbf{Z}$

Proof

จาก $6\mid5S_1-3S_2-2S_3$ จะได้ว่า $2\mid S_1-S_2$

และ $2\mid S_1^2-S_1$ ดังนั้น $2\mid S_1^2-S_2$

นั่นคือ $ab+bc+ca=\dfrac{S_1^2-S_2}{2}\in\mathbf{Z}$

Step2. $abc\in\mathbf{Z}$

Proof

จาก $6\mid5S_1-3S_2-2S_3$ จะได้ว่า $2\mid S_1-3S_2$

และ $2\mid S_1^2-S_1$ ดังนั้น $2\mid S_1^2-3S_2$

นั่นคือ $2\mid S_1(S_1^2-3S_2)+2S_3$


จาก $6\mid5S_1-3S_2-2S_3$ จะได้ว่า $3\mid S_1+2S_3$

และ $3\mid S_1^3-S_1$ ดังนั้น $3\mid S_1^3+2S_3$

นั่นคือ $3\mid S_1(S_1^2-3S_2)+2S_3$


เพราะฉะนั้น $abc=\dfrac{S_1^3-3S_1S_2+2S_3}{6}\in\mathbf{Z}$

Step3. $S_n\in\mathbf{Z}$

Proof

จากเอกลักษณ์ $S_{n+3}=(a+b+c)S_{n+2}-(ab+bc+ca)S_{n+1}+(abc)S_n$ ทุกจำนวนนับ $n$

สามารถ Induction ได้โดยง่ายว่า $S_n\in\mathbf{Z}$

จาก $S_1,S_2,S_3\in\mathbf{Z}$

และ ถ้า $S_1,S_2,S_3,\cdots,S_k\in\mathbf{Z}$ เมื่อ $k\geq3$ แล้วจะได้ว่า

$S_{k+1}=(a+b+c)S_k-(ab+bc+ca)S_{k-1}+(abc)S_{k-2}\in\mathbf{Z}$

[-Math-Sci-]

รบกวน N6 ด้วยครับ พิสูจน์ p|a

[LightLucifer]

ลองใช้ inverse modulo ดูครับ

[-Math-Sci-]

ขอโทษครับ ไปอ่านมาแล้ว แต่ยัง งง ๆ อยุ่เลยครับว่าจะเอามาใช้ยังไง ??

จากลิ้งค์นี้ครับ http://en.wikipedia.org/wiki/Modular...cative_inverse

ใช่อันเดียวกันรึเปล่าครับ

[Amankris]

โอ๊ะ ยังมีคนข้ามาดูอยู่เหมือนกัน

ข้อ 10 วันแรก ข้อนี้ดูเหมือนยาก (แค่รายละเอียดเยอะหน่อย)

ให้ $p\geq5$ เป็นจำนวนเฉพาะ ถ้า $\dfrac{a}{b}$ เป็นเศษส่วนอย่างต่ำซึ่ง$$\frac{1}{2^2}+\frac{1}{4^2}+\frac{1}{6^2}+\cdots+\frac{1}{(p-1)^2}=\frac{a}{b}$$ แล้วจงแสดงว่า $p\mid a$

Solution

ให้ $A=\left\{1,2,3,\ldots,p-1\right\}$

นิยามลำดับ $a_k\in A$ โดย $a_k\equiv k^{p-2}(mod\ p),\forall k\in A$ จะได้ว่า $a_k\cdot k\equiv1(mod\ p)$

Claim 1. $\forall i\not=j\in A,a_i\not=a_j$

Hide

สมมติ $\exists i\not=j\in A,a_i=a_j$

โดยไม่เสียนัย ให้ $i>j$ พบว่า $0<i-j<p-2$

และ $i-j\equiv i(j\cdot a_j)-j\equiv j(i\cdot a_j-1)\equiv j(i\cdot a_i-1)\equiv 0(mod\ p)$

นั่นคือ $p\mid i-j$ ดังนั้น $p<p-2$ ซึ่งเป็นไปไม่ได้

ดังนั้น $\forall i\not=j\in A,a_i\not=a_j$

Claim 2. $\left\{a_1,a_2,a_3,\ldots,a_{p-1}\right\}=A$

Hide

จากนิยามได้ว่า $\left\{a_1,a_2,a_3,\ldots,a_{p-1}\right\}\subseteq A$

และจาก Claim 1. ได้ว่า $|\left\{a_1,a_2,a_3,\ldots,a_{p-1}\right\}|=|A|$ โดยที่ $A$ เป็นเซตจำกัด

ดังนั้น $\left\{a_1,a_2,a_3,\ldots,a_{p-1}\right\}=A$

Claim 3. $p\mid a_1^2+a_2^2+a_3^2+\ldots+a_{p-1}^2$

Hide

จาก Claim 2. ได้ว่า $a_1^2+a_2^2+a_3^2+\ldots+a_{p-1}^2=1^2+2^2+3^2+\ldots+(p-1)^2=\dfrac{(p-1)(p)(2p-1)}{6}$

จาก $p\geq5$ ดังนั้น $\gcd(p,6)=1$

นั่นคือ $p\mid a_1^2+a_2^2+a_3^2+\ldots+a_{p-1}^2$

Claim 4. $p\mid a_1^2+a_2^2+a_3^2+\ldots+a_{\frac{p-1}{2}}^2$

Hide

จาก $a_k\equiv a_k(p-k)a_{p-k}\equiv a_k(-k)a_{p-k}\equiv -a_{p-k}(mod\ p),\forall k\in A$

ดังนั้น $a_k^2\equiv a_{p-k}^2(mod\ p),\forall k\in A$

จะได้ว่า $\displaystyle \sum_{k=1}^{p-1}a_k^2=\sum_{k=1}^{\frac{p-1}{2}}a_k^2+\sum_{k=1}^{\frac{p-1}{2}}a_{\frac{p-1}{2}+k}^2=\sum_{k=1}^{\frac{p-1}{2}}a_k^2+\sum_{k=1}^{\frac{p-1}{2}}a_{p-k}^2\equiv2\sum_{k=1}^{\frac{p-1}{2}}a_k^2(mod\ p)$

จาก Claim 3. ได้ว่า $\displaystyle p\mid\sum_{k=1}^{p-1}a_k^2$ และจาก $p\geq5$ ได้ว่า $\gcd(p,2)=1$

ฉะนั้น $\displaystyle p\mid\sum_{k=1}^{\frac{p-1}{2}}a_k^2$

Claim 5. $p\mid a$

Hide

ให้ $n=\left(\dfrac{p-1}{2}\right)!$ และ จัดรูปสมการใหม่เป็น $$\frac{4an^2}{b}=\left(\frac{n}{1}\right)^2+\left(\frac{n}{2}\right)^2+\left(\frac{n}{3}\right)^2+\ldots+\left(\frac{n}{\frac{p-1}{2}}\right)^2$$
จะเห็นว่าพจน์ด้านขวามือทุกพจน์เป็นจำนวนนับ ดังนั้น $\dfrac{4an^2}{b}$ เป็นจำนวนนับ

ได้ว่า

$\displaystyle \frac{4an^2}{b}=\sum_{k=1}^{\frac{p-1}{2}}\left(\frac{n^2}{k^2}\right)\equiv\sum_{k=1}^{\frac{p-1}{2}}\left(\frac{n^2k^2a_k^2}{k^2}\right)\equiv\sum_{k=1}^{\frac{p-1}{2}}\left(n^2a_k^2\right)\equiv n^2\sum_{k=1}^{\frac{p-1}{2}}a_k^2\equiv0(mod\ p)\ \ \ \ \ $ (จาก Claim 4.)

แต่ $\gcd(p,4)=1$ และ $\gcd(p,n)=1$ ดังนั้น $p\mid a$

[-Math-Sci-]

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

โอ๊ะ ยังมีคนข้ามาดูอยู่เหมือนกัน

ข้อ 10 วันแรก ข้อนี้ดูเหมือนยาก (แค่รายละเอียดเยอะหน่อย)

Solution

ให้ $A=\left\{1,2,3,\ldots,p-1\right\}$

นิยามลำดับ $a_k\in A$ โดย $a_k\cdot k\equiv1(mod\ p),\forall k\in A$

Claim 1. $\forall i\not=j\in A,a_i\not=a_j$

Hide

สมมติ $\exists i\not=j\in A,a_i=a_j$

โดยไม่เสียนัย ให้ $i>j$ พบว่า $0<i-j<p-2$

และ $i-j\equiv i(j\cdot a_j)-j\equiv j(i\cdot a_j-1)\equiv j(i\cdot a_i-1)\equiv 0(mod\ p)$

นั่นคือ $p\mid i-j$ ดังนั้น $p<p-2$ ซึ่งเป็นไปไม่ได้

ดังนั้น $\forall i\not=j\in A,a_i\not=a_j$

Claim 2. $\left\{a_1,a_2,a_3,\ldots,a_{p-1}\right\}=A$

Hide

จากนิยามได้ว่า $\left\{a_1,a_2,a_3,\ldots,a_{p-1}\right\}\subseteq A$

และจาก Claim 1. ได้ว่า $|\left\{a_1,a_2,a_3,\ldots,a_{p-1}\right\}|=|A|$ โดยที่ $A$ เป็นเซตจำกัด

ดังนั้น $\left\{a_1,a_2,a_3,\ldots,a_{p-1}\right\}=A$

Claim 3. $p\mid a_1^2+a_2^2+a_3^2+\ldots+a_{p-1}^2$

Hide

จาก Claim 2. ได้ว่า $a_1^2+a_2^2+a_3^2+\ldots+a_{p-1}^2=1^2+2^2+3^2+\ldots+(p-1)^2=\dfrac{(p-1)(p)(2p-1)}{6}$

จาก $p\geq5$ ดังนั้น $\gcd(p,6)=1$

นั่นคือ $p\mid a_1^2+a_2^2+a_3^2+\ldots+a_{p-1}^2$

Claim 4. $p\mid a_1^2+a_2^2+a_3^2+\ldots+a_{\frac{p-1}{2}}^2$

Hide

จาก $a_k\equiv a_k(p-k)a_{p-k}\equiv a_k(-k)a_{p-k}\equiv -a_{p-k}(mod\ p),\forall k\in A$

ดังนั้น $a_k^2\equiv a_{p-k}^2(mod\ p),\forall k\in A$

จะได้ว่า $\displaystyle \sum_{k=1}^{p-1}a_k^2=\sum_{k=1}^{\frac{p-1}{2}}a_k^2+\sum_{k=1}^{\frac{p-1}{2}}a_{\frac{p-1}{2}+k}^2=\sum_{k=1}^{\frac{p-1}{2}}a_k^2+\sum_{k=1}^{\frac{p-1}{2}}a_{p-k}^2\equiv2\sum_{k=1}^{\frac{p-1}{2}}a_k^2(mod\ p)$

จาก Claim 3. ได้ว่า $\displaystyle p\mid\sum_{k=1}^{p-1}a_k^2$ และจาก $p\geq5$ ได้ว่า $\gcd(p,2)=1$

ฉะนั้น $\displaystyle p\mid\sum_{k=1}^{\frac{p-1}{2}}a_k^2(mod\ p)$

Claim 5. $p\mid a$

Hide

ให้ $n=\left(\dfrac{p-1}{2}\right)!$ และ จัดรูปสมการใหม่เป็น $$\frac{4an^2}{b}=\left(\frac{n}{1}\right)^2+\left(\frac{n}{2}\right)^2+\left(\frac{n}{3}\right)^2+\ldots+\left(\frac{n}{\frac{p-1}{2}}\right)^2$$
จะเห็นว่าพจน์ด้านขวามือทุกพจน์เป็นจำนวนนับ ดังนั้น $\dfrac{4an^2}{b}$ เป็นจำนวนนับ

ได้ว่า

$\displaystyle \frac{4an^2}{b}=\sum_{k=1}^{\frac{p-1}{2}}\left(\frac{n^2}{k^2}\right)\equiv\sum_{k=1}^{\frac{p-1}{2}}\left(\frac{n^2k^2a_k^2}{k^2}\right)\equiv\sum_{k=1}^{\frac{p-1}{2}}\left(n^2a_k^2\right)\equiv n^2\sum_{k=1}^{\frac{p-1}{2}}a_k^2\equiv0(mod\ p)\ \ \ \ \ $ (จาก Claim 4.)

แต่ $\gcd(p,4)=1$ และ $\gcd(p,n)=1$ ดังนั้น $p\mid a$

ขอบคุณมาก ๆ ครับ

คงต้องเอาไปทำความเข้าใจต่อ เพราะเท่าที่มอง ๆ ยังงง ๆ อยู่เลย อ๋อแล้ววิธีพวกนี้ก็อาศัยเจอบ่อย ๆ

หรือรูปแบบมันต้องทำแบบนี้ครับ ?

ขอบคุณมากนะครับ

[Amankris]

@#37
ไม่ค่อยเข้าใจคำถามนะ

แต่สำหรับข้อนี้ ไม่น่าจะมีวิธีที่แตกต่างจากนี้มากนักนะครับ

[LightLucifer]

ผมว่าข้อนี้หลักๆแล้วแนวคิดคือการใช้ CRS (Complete Residue System)
ลองข้อนี้ดูครับ
จงพิสูจน์ว่า $p>3$ เป็นจำนวนเฉพาะถ้า
$$\frac{1}{1^2}+\frac{1}{2^2}+...+\frac{1}{(p-1)^2}=\frac{m}{n}$$
แล้ว $p|m$
ลองทำดูครับ

[kongp]

โจทย์แบบนี้เรียกว่าอะไรดีครับ "Perceptual" ดีไหมดีไหมครับ เหมือนว่าเป็นฟอร์มที่คุ้นเคย โจทย์ abc เนี่ย เข้าใจว่าใช้ประมาณเวลานำไปใช้ประโยชน์จริงในเชิงวิศวกรรม สาขาวิทยาศาสตร์ก็ศึกษาสิ่งที่มีอยู่ในธรรมชาติกับในตำรา อันนี้ผมเห็นตำราในห้องสมุดอย่างที่จุฬามีเยอะ แต่จะให้เป็นสเต็ปการคำนวนใช้ในงานต่างๆ แล้วหายากหน่อย จริงไหมครับ?

[THE REGISTER]

ช่วยทำข้อ A3 A13 ให้่หน่อยครับ ขอบคุณมากครับ

[Amankris]

#41

A3
ลองแทนค่าตรงๆครับ แต่จะได้ไม่เท่ากับโจทย์

A13
Schur's inequality

[THE REGISTER]

ขอบคุณมากครับ

[DARK SWORD]

ช่วยเฉลยข้อ C8 และ N4 ให้หน่อยครับ
ส่วนข้อ C10ผมไม่เข้าใจโจทย์เลยครับ
ขอบคุณครับ

[LightLucifer]

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

ช่วยเฉลยข้อ C8 และ N4 ให้หน่อยครับ
ส่วนข้อ C10ผมไม่เข้าใจโจทย์เลยครับ
ขอบคุณครับ

N4
ผมไม่ค่อยมั่นใจนะ
สังเกตุว่าถ้า $a$ เป็นจำนวนประกอบแล้ว $M_a$ เป็นจำนวนประกอบ
แล้วก็เลือก $k=(m+1)!-1$