โจทย์โอลิมปิก 2549 รอบสอง

[tani]

กำหนดให้ a₁ = 1 , a₂ = 2548 โดยที่ a_n = 2549a_n-1 - 2006a_n-2 ทุก n ฮ N , n > 2
จงแสดงว่ามี a ที่ทำให้ 271 หาร a²⁵⁴⁹a₂₅₄₉ + a²⁰⁰⁶a₂₀₀₆ ลงตัว โดยที่ 271 หาร a ไม่ลงตัว

[tani]

ข้างล่างคือลิ้งค์ข้อสอบทั้งหมดครับ http://www.vcharkarn.com/include/vca...1a14c08b5b4810

[warut]

ข้อความเดิมของคุณ tani:
กำหนดให้ a₁ = 1 , a₂ = 2548 โดยที่ a_n = 2549a_n-1 - 2006a_n-2 ทุก n ฮ N , n > 2
จงแสดงว่ามี a ที่ทำให้ 271 หาร a²⁵⁴⁹a₂₅₄₉ + a²⁰⁰⁶a₂₀₀₆ โดยที่ 271 หาร a ไม่ลงตัว

จากโจทย์เราได้ว่า สำหรับ $n \in \mathbb N $ และ $n>2$ แล้ว $$ a_n \equiv 110a_{n-1} -109a_{n-2} \pmod{271} $$ และเราจะได้ว่า $$ \begin{array}{rcl} a_1 & \equiv & 1 \pmod{271} \\ a_2 & \equiv & 109 \pmod{271} \\ a_3 & \equiv & (110)(109)-(109)(1) \equiv 109^2 \pmod{271} \\ a_4 & \equiv & (110)(109^2)-(109)(109) \equiv 109^3 \pmod{271} \\ & \vdots & \\ \therefore \quad a_n & \equiv & 109^{n-1} \pmod{271} \quad \text{by induction} \end{array} $$ ดังนั้น ถ้า $ 271 \mid \alpha^{2549} a_{2549} + \alpha^{2006} a_{2006} $ และ $ 271 \! \not| \, \alpha $ แล้วเราจะได้ว่า $$ \begin{array}{ccl} 0 & \equiv & \alpha^{2549} a_{2549} + \alpha^{2006} a_{2006} \pmod{271} \\ & \equiv & \alpha^{2549} 109^{2548} + \alpha^{2006} 109^{2005} \pmod{271} \\ & \equiv & \alpha^{2006} 109^{2005} \left( (109\alpha)^{543} +1 \right) \pmod{271} \\ & \equiv & (109\alpha)^{543} +1 \pmod{271} \\ & \equiv & (109\alpha)^3 +1 \pmod{271} \end{array} $$ ตรงบรรทัดสุดท้ายนี่ใช้ Fermat's Little Theorem ครับ ($ \, 271 \! \not| \, x \, \Rightarrow \, x^{270} \equiv 1 \pmod{271} \, $)

ดังนั้นเราจะได้สิ่งที่โจทย์ต้องการในทันที ถ้าเราสามารถเลือก $\alpha$ ให้ $ 109 \alpha \equiv -1 \pmod{271} $ ได้ ซึ่งในกรณีนี้เราสามารถทำได้จริงครับ เพราะ $ \gcd (109,271) =1 $

ป.ล. โจทย์ข้อนี้สวยดีครับ

[tani]

ขอบคุณมากครับ โจทย์ข้อนี้เป็นโจทย์ที่ค้างคาใจมากเลยครับ เพราะ คิดว่าน่าจะทำได้แต่ตอนสอบคิดไม่ออกพอกลับมาบ้านก็เลยมาโพสต์ให้ช่วยนี้แหละครับ
วิธีทำของคุณ warut สวยมากเลยครับ

[gon]

ผมขอเสนอแนะวิธีเิพิ่มเฉพาะตอนส่วนแรกของคุณ warut นะครับ.

จาก $a_n \equiv 110a_{n-1} - 109a_{n-2}\pmod {271}$
ดังนั้น

$a_n - a_{n-1}\equiv 109(a_{n-1} - a_{n-2})\pmod {271}$
$\quad \quad \quad \quad \equiv 109(109)(a_{n-2} - a_{n-3}) \pmod{271}$
$\quad \quad \quad \quad \equiv 109^3(a_{n-3} - a_{n-4}) \pmod{271}$
$\quad \quad \quad \quad \vdots$
$\quad \quad \quad \quad \equiv109^{n-2}(a_2-a_1)\pmod{271}$
$\quad \quad \quad \quad \equiv109^{n-2}(2547)\pmod{271}$
$\quad \quad \quad \quad \equiv109^{n-2}(108)\pmod{271}$
$\quad \quad \quad \quad \equiv109^{n-2}(109-1)\pmod{271}$
$\quad \quad \quad \quad \equiv109^{n-1} - 109^{n-2}\pmod{271}$

$\Sigma(a_n - a_{n-1}) \equiv \Sigma(109^{n-1} - 109^{n-2})\pmod{271} $

ดังนั้น $a_n - a_2 \equiv (109^{n-1} - 109)\pmod{271}$
แต่ $a_2 = 2548 \equiv 109 \pmod{271}$ ดังนั้น $a_n \equiv 109^{n-1}\pmod{271}$

[passer-by]

ในบรรดา ข้อสอบ รอบ 2 ปีนี้ทั้ง 2 วัน ผมติดใจคำถามด้านล่างนี้มากที่สุดครับ

มี bijection $ f: N \rightarrow N $ ซึ่งสอดคล้องกับ เงื่อนไขด้านล่างพร้อมกันทั้ง 3 ข้อหรือไม่

(1) f(n+2006)= f(n)+2006 ทุกจำนวนนับ n

(2) f(f(n))= n+2 ทุก n= 1,2,...,2004

(3) f(2549) >2550


ตอนนี้ เท่าที่ผมคิดไว้ คือไม่น่าจะมี bijection ที่ต้องการ แต่ก็ยังไม่ 100 % ครับ

Extreme case เท่าที่ผมคิดออกตอนนี้ คือ

bijection $ f: N \rightarrow N-\{2 \} $ โดย

$ f(n)= \left \{\begin{array}{ll} n+3 & \text{n is odd} \\
n-1 & \text{n is even} \end{array}\right. $

ซึ่ง f นี้ สอดคล้องกับเงื่อนไข 3 ข้อที่ให้มา

ใครที่ยืนยันได้ว่าไม่มีฟังก์ชันดังกล่าวจริง หรือ หาตัวอย่างฟังก์ชันที่โจทย์ต้องการได้ ก็บอกกันด้วยนะคร้าบ

[[Cb : TkZ]]

f(2005)=2

$ f(n)= \left \{\begin{array}{ll} n+3 & \text{n is odd} \\ n-1 & \text{n is even} \end{array}\right. $

ได้มั้ยครับ

[Mr.high]

ผมคิดว่าแนวคิดของคุณ [Cb : TkZ] เป็นแนวคิดที่ดีนะครับ
แต่มีข้อเสียตรงที่ว่า ฟังก็ชันของคุณ passer-by ได้เซตไว้เพื่อ ให้มัน onto ดังนั้นถ้าเราเลื่อนตัวนึงก็ต้องเลื่อนให้หมดนะครับ ไม่งั้นเด๋วไม่ onto
นั่นคือ เราสร้างกรณีพิเศษขึ้นมาโดยให้ sequence ที่อยู่ในรูปของ a+2006k ทำการส่งค่าเลื่อนลงมา
ในที่นี้ผมให้ n= 2005+2006k
ทำการส่งค่า f(n) = n-2006+3
ส่วนฟังก์ัชันที่เหลือก็เหมือนเดิม
นั่นคือจะได้ว่าฟังก์ชันนี้คือ

ถ้า n ไม่อยู่ในรูปของ 2005+2006k

f(n) = n+3; n is odd
= n-1 ; n is even

ถ้า n อยู่ในรูปนั้น

f(n) = n+3 -2006;

คิดว่าฟังก์ขันนี้โอเคป่าวคับ

[[Cb : TkZ]]

ผมว่าน่าจะได้นะครับ
สรุปแล้วคือมันมีฟังก์ชันที่สอดคล้อง

แต่ในห้องสอบผมคิดไม่ออกเลยมั่วๆไปว่ามันไม่มีอะครับ


จะติดมั้ยล่ะเนี่ย พรุ่งนี้ประกาศผลแล้วอ่า

[tani]

ผลสอบ สสวท. รอบที่สองครับ http://www.ipst.ac.th/news/results_second_MATH_49.pdf

[gon]

ที่รู้จักตอนนี้ก็มีน้อง Tony กับ Tummy , 2 แล้วครับ มีใครติดอีกบ้างหรือเปล่า

[[Cb : TkZ]]

ผมก็แอบๆติดเหมือนกันอ่า
ฟลุ้คๆไป

[gon]

ข้อความเดิมของคุณ [Cb : TkZ]:
ผมก็แอบๆติดเหมือนกันอ่า
ฟลุ้คๆไป

ว้าวเหรียญทองคนแรกซะด้วย แบบนี้ไม่แอบติดแล้วครับ.