USAMO 2005

[gools]

1.Determine all composite positive integers \(n\) for which it is
possible to arrange all divisors of \(n\) that are greater than 1 in
a circle so that no two adjacent divisors are relatively prime.

2.Prove that the
system
\[\begin{array}{rcl}
x^6+x^3+x^3y+y & = 147^{157} \\
x^3+x^3y+y^2+y+z^9 & = 157^{147}
\end{array}
\]
has no solutions in integers \(x\), \(y\), and \(z\).

3. Let \(ABC\) be an acute-angled triangle, and let \(P\) and \(Q\) be two
points on side \(BC\). Construct point \(C_1\) in such a way that
convex quadrilateral \(APBC_1\) is cyclic, \(QC_1
\parallel CA\), and \(C_1\) and \(Q\) lie on opposite sides of line
\(AB\). Construct point \(B_1\) in such a way that convex
quadrilateral \(APCB_1\) is cyclic, \(QB_1 \parallel BA\), and \(B_1\)
and \(Q\) lie on opposite sides of line \(AC\). Prove that points
\(B_1, C_1,P\), and \(Q\) lie on a circle.

[nongtum]

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

2. We assume first that there are integers x,y,z which satisfy following equations system:
(eq1) \(x^6+x^3+x^{3}y+y=(x^{3}+1)(x^{3}+y)=147^{157}=(7^{2}.3)^{157}\)
(eq2) \(x^3+x^{3}y+y^2+y+z^9=(y+1)(x^{3}+y)+z^9=157^{147}\).

Since the product of two odd numbers are odd, we have \(x^{3}+1\) and \(x^{3}+y\) as odd numbers,
that is \(x^3\) is even and, from our assumption, x is even. Also y and z are odd.

We use then the fact that \(x^3\equiv0\pmod4\), \(y\equiv\pm1\pmod4\) and \(z\equiv\pm1\pmod4\) to verify each case as follows
(following calculations are in mod 4):

equation 2:
$z\equiv1\pmod4$, $y\equiv1\pmod4$ yields $2\cdot1+1\equiv1$ (wrong)
$z\equiv1\pmod4$, $y\equiv-1\pmod4$ yields $(-1)\cdot0+1\equiv1$ (right)
$z\equiv-1\pmod4$, $y\equiv1\pmod4$ yields $2\cdot1-1\equiv1$ (right)
$z\equiv-1\pmod4$, $y\equiv-1\pmod4$ yields $2\cdot0-1\equiv1$ (wrong),

then set the right 'answer sets' in equation 1:
\(1\cdot(\pm1)\equiv(-1)^{157}\equiv-1\),
which give us \(y\equiv-1\pmod4\).

From equation 1 we can also assume that \(x^3+1={7^{\alpha_{1}}.3^{\beta_{1}}}\) and \(x^3+y={7^{\alpha_{2}}.3^{\beta_{2}}}\), where all exponents are integers.

We calculate each factor again in mod 4, which yields:
\(x^3+1\equiv(-1)\cdot{\alpha_{1}}+(-1).{\beta_{1}}=-{\alpha_{1}}-{\beta_{1}}\equiv1\),
and \(x^3+y\equiv\ (-1)\cdot{\alpha_{2}}+(-1).{\beta_{2}}=-{\alpha_{2}}-{\beta_{2}}\equiv-1\).
That means \({\alpha_{1}}+{\beta_{1}}+{\alpha_{2}}+{\beta_{2}}\equiv0\ne-1=157\cdot3\pmod4\),
which yield the desired contradiction, hence complete the proof. (๕๕๕ ซะเมื่อไหร่ )

-------------------------------------
Phew... คงมีวิธีที่ง่ายกว่านี้นะ เพราะอาจคำนวณเศษผิดได้ง่ายมากๆ
Edit: มาแก้ TeX syntax ครับ กระทู้นี้ตอนผมเข้ามาที่นี่ใหม่ๆเลยนะนั่น

[warut]

ผมก็สนใจข้อ 2 เหมือนกันครับ แต่พยายามคิดเท่าไหร่ก็ไม่ออกสักที ก็พอดีคุณ nongtum
มาตอบ แต่ไม่รู้เป็นไงมีตัวแปลกๆปนอยู่เต็มไปหมด อ่านยากมากเลยครับ แต่ผมก็พยายาม
ติดตามวิธีพิสูจน์ไปเรื่อยๆ ก็เข้าใจและเห็นด้วยมาตลอด แต่ตอนสุดท้ายนี่สิครับผมไม่แน่ใจ
ว่าคุณ nongtum เขียนอย่างนี้รึเปล่า\[x^3+1\equiv
(-1)\cdot\alpha_1+(-1)\cdot\beta_1\pmod4\]ถ้าใช่ผมว่าตรงนี้ไม่น่าจะถูกนะครับ จาก \(x^3+1=7^{\alpha_1}\cdot3^{\beta_1}\) เราควรจะได้ว่า\[x^3+1\equiv
(-1)^{\alpha_1+\beta_1}\pmod4\]มากกว่านะครับ ซึ่งถ้าที่ผมคิดต่อไปไม่ผิด นี่จะยังไม่เพียงพอที่จะพิสูจน์โจทย์ข้อนี้ได้ครับ

[gon]

จะเล่น Usamo กันแล้วหรือครับ. ดูผ่าน ๆ โจทย์ข้อ 2. ดูแล้วเข้าใจง่ายสุดเลยนะครับ. ไม่ปวดหัวดี แต่ไม่รู้ถ้าคิดแล้วจะปวดหัวหรือเปล่า เดี๋ยวว่าง ๆ ผม จะลองคิดบ้างครับ.

[nongtum]

ข้อความเดิมของคุณ warut:
ผมก็สนใจข้อ 2 เหมือนกันครับ แต่พยายามคิดเท่าไหร่ก็ไม่ออกสักที ก็พอดีคุณ nongtum
มาตอบ แต่ไม่รู้เป็นไงมีตัวแปลกๆปนอยู่เต็มไปหมด อ่านยากมากเลยครับ แต่ผมก็พยายาม
ติดตามวิธีพิสูจน์ไปเรื่อยๆ ก็เข้าใจและเห็นด้วยมาตลอด แต่ตอนสุดท้ายนี่สิครับผมไม่แน่ใจ
ว่าคุณ nongtum เขียนอย่างนี้รึเปล่า\[x^3+1\equiv
(-1)\cdot\alpha_1+(-1)\cdot\beta_1\pmod4\]ถ้าใช่ผมว่าตรงนี้ไม่น่าจะถูกนะครับ จาก \(x^3+1=7^{\alpha_1}\cdot3^{\beta_1}\) เราควรจะได้ว่า\[x^3+1\equiv
(-1)^{\alpha_1+\beta_1}\pmod4\]มากกว่านะครับ ซึ่งถ้าที่ผมคิดต่อไปไม่ผิด นี่จะยังไม่เพียงพอที่จะพิสูจน์โจทย์ข้อนี้ได้ครับ

ขอบคุณมากครับสำหรับตำท้วงติง ตอนนี้เลยยังคิดไม่ออกเหมือนกัน คือคิดไปคิดมาทำท่าว่าจะไม่จบแค่ mod 8 เอาซะอย่างงั้น แต่ยังเชื่อว่าสามารถแก้ไดด้วยวิธีที่พิมพ์ให้ดู เอาเป็นว่าผมจะมาแก้อีกทีตอน'คิดเอง'ออกละกันครับ ขอหลบไปปั่นการบ้านที่กำลังท่วมหัวก่อน

อย่าอ่านหากยังอยากทำข้อสองด้วยตัวเอง

เห็นเฉลยทางเนตแล้วครับ

แน่ใจนะว่าอยากดู

รู้สึกว่าจะใช้ fermat theorem ในการพิสูจน์ว่าไม่มีสมการแบบนั้นบน mod 19 และ mod 13 (2 Solutions) ครับ หาได้ง่ายๆทาง google ครับ (นิสัยเสียนิดๆ)

________________________________
I love spoilers.

[warut]

ข้อความเดิมของคุณ gools:
2.Prove that the system
\[\begin{array}{rcl}
x^6+x^3+x^3y+y & = & 147^{157} \\
x^3+x^3y+y^2+y+z^9 & = & 157^{147}
\end{array}
\]
has no solutions in integers \(x\), \(y\), and \(z\).

ผมลองทำตาม hint ที่คุณ nongtum ให้มาคือใช้ modulo 13 ดังนั้นสมภาคทั้งหมดข้างล่างนี้เป็น mod 13 นะครับ นั่นทำให้สมการทั้งสองกลายเป็น $$\begin{array}{lrcl} (1) & x^6+x^3+x^3y+y & \equiv & 4 \\ (2) & x^3+x^3y+y^2+y+z^9 & \equiv & 1 \end{array}$$ เนื่องจาก $x^3\equiv 0, \pm1, \pm5$ และ $x^6\equiv 0, \pm1$ ดังนั้น $z^9= z^6z^3 \equiv 0, \pm1, \pm5$

กรณีที่ 1: $x^3\equiv0$
จาก $(1)$ เราจะได้ $y\equiv4$ แทนค่าลงใน $(2)$ จะได้ $z^9\equiv-6$ ดังนั้นจึงไม่มีคำตอบในกรณีนี้

กรณีที่ 2: $x^3\equiv1$
จาก $(1)$ เราจะได้ $y\equiv1$ แทนค่าลงใน $(2)$ จะได้ $z^9\equiv-3$ ดังนั้นจึงไม่มีคำตอบในกรณีนี้

กรณีที่ 3: $x^3\equiv-1$
เราจะพบว่าไม่มี $y$ ที่สอดคล้องกับ $(1)$ จึงไม่มีคำตอบในกรณีนี้

กรณีที่ 4: $x^3\equiv5$
จาก $(1)$ เราจะได้ $y\equiv0$ แทนค่าลงใน $(2)$ จะได้ $z^9\equiv-4$ ดังนั้นจึงไม่มีคำตอบในกรณีนี้

กรณีที่ 5: $x^3\equiv-5$
จาก $(1)$ เราจะได้ $y\equiv4$ แทนค่าลงใน $(2)$ จะได้ $z^9\equiv6$ ดังนั้นจึงไม่มีคำตอบในกรณีนี้เช่นกัน

เราจึงสรุปได้ว่า ระบบสมการของโจทย์ข้อนี้ ไม่มีคำตอบเป็นจำนวนเต็มครับ

ป.ล. ผมไม่ได้ลอง search หาเฉลยของข้อนี้นะครับ แต่คิดว่าน่าจะคล้ายกับที่ผมทำ เพราะส่วนที่ยากที่สุดน่าจะเป็นการหา modulus ที่เหมาะสม ซึ่งผมลองให้คอมพ์หา prime moduli ที่ใช้ได้ ก็เจอเพียง 13 กับ 19 ตามที่คุณ nongtum บอกไว้ใน hint นั่นแหละครับ