อ้างอิง:
ข้อความเดิมเขียนโดยคุณ warut
โจทย์ข้อนี้ดีอย่าง คือสามารถใช้กำลังเข้าหักหาญเอาคำตอบได้ ไม่เหมือนกับข้อ 59-60 แต่โจทย์ที่ brute force ได้ก็มีข้อเสียคือ เรามักไม่สนใจว่าจะทำได้หรือไม่ แต่ไปสนใจว่าจะหาวิธีทำสวยๆได้ยังไง Carl Pomerance (number theorist ที่มีชื่อเสียงมากที่สุดคนนึงในยุคปัจจุบัน) เคยเขียนเล่าให้ฟังว่า เขาเคยได้รับโจทย์ในการแข่งขันข้อนึง เป็นโจทย์ให้แยกตัวประกอบจำนวนเต็ม ซึ่งถ้าใช้ trial division ธรรมดาก็คงทำได้แล้วล่ะ แต่ในเมื่อโจทย์ออกมาในลักษณะอย่างนี้ เขาคิดว่ามันต้องมีวิธีฉลาดๆในการทำแน่ จึงเสียเวลามองหาวิธีอยู่นาน จนกระทั่งเวลาใกล้หมด ก็ยังทำไม่ได้ เลยตัดสินใจกลับมาใช้ trial division แต่ก็สายเกินไปแล้ว...
สำหรับวิธีใช้กำลังที่ผมว่านั้น คือทำตรงๆดังนี้ครับ
จากที่โจทย์ให้ เราจะได้ว่า $$x_{n+2} = 2x_{n+1} +3y_{n+1} = 2x_{n+1} +3(x_n+2y_n) = 2x_{n+1} +3x_n +6y_n$$ เมื่อรวมกับ $x_{n+1}=2x_n+3y_n$ เราจึงได้ว่า $$x_{n+2} = 4x_{n+1} -x_n$$ โดยที่ $x_1=2$ และ $x_2=7$
แก้ difference equation อันนี้ เราได้ $$x_n= \frac12 (a^n + a^{-n}) $$ เมื่อ $a=2+\sqrt3$
จาก $$x_{2n+1}= 2(K_n^2+(K_n+1)^2) = (2K_n+1)^2+1$$ และ $$x_{2n+1}-1 = \frac12 (a^{2n+1} + a^{-(2n+1)} - 2) = \frac12 (a^{n+1/2} - a^{-(n+1/2)} )^2$$ ดังนั้น $$K_n= \frac{(1+\sqrt3)}{4} a^n + \frac{(1-\sqrt3)}{4} a^{-n} -\frac12 $$ เพราะ $\sqrt a= \dfrac{1+\sqrt3}{\sqrt2} $
คำนวณย้อนกลับหา linear recurrence relation เราจะพบว่า $$K_{n+2} =4K_{n+1} -K_n +1$$ โดยที่ $K_0=0$ และ $K_1=2$
โดย induction เรารู้ว่า $K_{n+1}>K_n$ ดังนั้น $\{K_n\}_{n\ge1}$ จึงเป็นลำดับของจำนวนเต็มบวก ตามที่โจทย์ต้องการครับ
สำหรับวิธีทำเจ๋งๆของข้อนี้ หรือวิธีทำของข้อที่เหลือ (ข้อ 64. ดูท่าทางน่าสนใจมาก) คงต้องปล่อยให้เป็นหน้าที่ของคนอื่นๆแล้วล่ะครับ  |
คุณ warut ใช้วิธีเดียวกับผมเลยครับ
แต่ผมคำนวณผิดที่ไหนซักแห่งก็เลยเลิกคิดไปแล้ว
ผมหา $x_n,y_n$ โดยตั้งสมการแบบนี้ครับ
$\pmatrix{x_{n+1}\\ y_{n+1}} = \pmatrix{2 & 3 \\ 1 & 2}\pmatrix{x_n \\ y_n}$
$~~~~~~~~~~~=\pmatrix{2 & 3 \\ 1 & 2}^n\pmatrix{x_1 \\ y_1}$
จากนั้นก็ใช้ linear algebra ล้วนๆ
ป.ล. คุณ warut หายยุ่งแล้วใช่มั้ยครับ
เห็นโจทย์ทฤษฎีจำนวนยากๆทีไรคิดถึงคุณ warut ทุกทีเลย
