Number Theory Marathon

[nooonuii]

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

[nongtum]

ช่วงนี้เว็บบอร์ดเงียบไปกับช่วงสอบแน่ๆเลย เอาเป็นว่ามาวางระเบิดไว้อีกข้อดีกว่า

17. จำนวนเฉพาะสองจำนวนต่างกันอยู่ 100 หากเราจับเลขสองตัวนี้มาต่อกัน(concatenate) เราจะได้จำนวนเฉพาะอีกตัว จงหาจำนวนเหล่านี้

[warut]

ข้อความเดิมของคุณ nooonuii:
16. จงพิสูจน์ว่ามีจำนวนเต็มบวก n ซึ่งทำให้ 2ⁿ ขึ้นต้นด้วย 2548 เมื่อเขียนเป็นเลขฐานสิบ

ยังคิดไม่ออกครับ แต่ให้คอมพิวเตอร์ลองหาดูเจอเพียบเลย

n = 10977, 13113, 24278, 26414, 37579, 39715, 41851, 53016, 55152, 66317, ...

เช่น\[2^{10977}\approx2548.3695\times10^{3301}\]

[gools]

ข้อต่อไปครับ
ให้ \(n\) เป็นจำนวนนับ \((3+\sqrt{7})^n\) เป็นจำนวนคู่หรือคี่

[nooonuii]

ข้อความเดิมของคุณ gools:
ข้อต่อไปครับ
ให้ \(n\) เป็นจำนวนนับ \((3+\sqrt{7})^n\) เป็นจำนวนคู่หรือคี่

โจทย์ไม่ครบหรือเปล่าครับ ดูยังไงก็ไม่น่าจะเป็นจำนวนตรรกยะ

[gools]

ขอโทษทีครับ คำถามจริงๆคือ

ให้ \(n\) เป็นจำนวนนับ \(\lceil(3+\sqrt{7})^n\rceil\) เป็นจำนวนคู่หรือคี่

[tunococ]

แทน n = 1 ได้เลขคู่ครับ

วิธีพิสูจน์สำหรับจำนวนนับใด ๆ ของผม มันอาจจะดูสิ้นเปลืองไปหน่อย ช่วยดูด้วยนะครับ

กำหนดให้
\[f(n) = (3 + \sqrt{7})^n + (3 - \sqrt{7})^n\]
เราจะรู้ว่า
\[f(n + 2) = 6 f(n + 1) - 2 f(n)\]

แทนค่า n = 0 และ n = 1 จะรู้ว่า
\[f(0) = 2\]\[f(1) = 6\]
จาก induction \(\rightarrow f(n)\) จะเป็นจำนวนคู่แน่นอน ถ้า \(n \in \mathbf{Z}^+\)

จาก...
\[(3 - \sqrt{7})^n < 1 \qquad ; n \in \mathbf{Z}^+\]
และ
\[f(n) = (3 + \sqrt{7})^n + (3 - \sqrt{7})^n \in \mathbf{Z} \qquad ; n \in \mathbf{Z}^+\]
ก็เลยรู้ว่า
\[f(n) = \lceil (3 + \sqrt{7})^n \rceil \qquad ; n \in \mathbf{Z}^+\]
สรุปแล้วก็คือ
\[\forall n \in \mathbf{Z}^+ \left[2 \mid \lceil (3 + \sqrt{7})^n \rceil\right]\]
หรือ ถ้าคิดกรณีทั่วไปมากขึ้นอีกนิด (จาก recurrence relation อันข้างบน) จะได้ว่า
\[2^{\lfloor n/2 \rfloor + 1} \mid \lceil (3 + \sqrt{7})^n \rceil\]

[tunococ]

เอาโจทย์มาให้ครับ

กำหนดให้
\[\begin{eqnarray}
a_1 & = & 1 \\
a_2 & = & 2 \\
2 \mid a_n a_{n+1} \rightarrow a_{n+2} & = & 5a_{n+1} - 3a_n \\
2 \mid (a_n a_{n+1} + 1) \rightarrow a_{n+2} & = & a_{n+1} - a_n
\end{eqnarray}\]
จงพิสูจน์ว่า
1. ลำดับ \(\{a_n\}\) มีจำนวนของค่าที่เป็นบวกและลบอยู่ไม่จำกัด
2. ไม่มี 0 อยู่ในลำดับนี้
3. ถ้า \(n = 2^k - 1\) เมื่อ \(k \in (\mathbf{Z}^+ - \{1\})\) แล้ว \(7 \mid a_n\)

[warut]

ข้อความเดิมของคุณ nongtum:
17. จำนวนเฉพาะสองจำนวนต่างกันอยู่ 100 หากเราจับเลขสองตัวนี้มาต่อกัน(concatenate) เราจะได้จำนวนเฉพาะอีกตัว จงหาจำนวนเหล่านี้

ทำไมข้อนี้ไม่มีคนทำเลยล่ะ ผมว่ามันง่ายกว่าข้ออื่นๆตั้งเยอะนา

ให้จำนวนเฉพาะสองตัวนั้นเป็น p กับ p + 100

กรณีที่ 1
p = 3 ดังนั้น p + 100 = 103 เป็นจำนวนเฉพาะ จับ 2 ตัวมาต่อกัน ต่อแบบแรกได้ 1033 เป็นจำนวนเฉพาะ ต่ออีกแบบได้ 3103 = 29 * 107 ไม่ใช่จำนวนเฉพาะ

กรณีที่ 2
\(2<p\equiv-1\pmod3\) ดังนั้น \(p+100\equiv0\pmod3\) ไม่ใช่จำนวนเฉพาะ

กรณีที่ 3
\(p\equiv1\pmod3\) เราจึงได้ว่า \(p+100\equiv2\pmod3\) ดังนั้นเลขที่เกิดจากการต่อกันจะหารด้วย 3 ลงตัว จึงไม่ใช่จำนวนเฉพาะ (ตรงนี้ใช้หลักที่ว่า \(n\equiv d(n)\pmod3\) เมื่อ d(n) คือผลบวกของเลขโดดของ n)

[warut]

ข้อความเดิมของคุณ tunococ:
กำหนดให้
\[\begin{eqnarray}
a_1 & = & 1 \\
a_2 & = & 2 \\
2 \mid a_n a_{n+1} \rightarrow a_{n+2} & = & 5a_{n+1} - 3a_n \\
2 \mid (a_n a_{n+1} + 1) \rightarrow a_{n+2} & = & a_{n+1} - a_n
\end{eqnarray}\]
จงพิสูจน์ว่า
1. ลำดับ \(\{a_n\}\) มีจำนวนของค่าที่เป็นบวกและลบอยู่ไม่จำกัด
2. ไม่มี 0 อยู่ในลำดับนี้
3. ถ้า \(n = 2^k - 1\) เมื่อ \(k \in (\mathbf{Z}^+ - \{1\})\) แล้ว \(7 \mid a_n\)

โห...โจทย์ข้อนี้ยากจริงๆ คุณ tunococ เอามาจากไหนอ่ะ ยังไงก็ช่วยเฉลยให้หน่อยนะครับ

เท่าที่ผมสังเกตเจอหลังจากคิดเลขอย่างหนักคือ\[a_{3n}=2a_{3n-3}-9a_{3n-6}\]ดังนั้น\[a_{3n}
=-3^{n+1}\cos\left((n+1)\cos^{-1}\frac{1}{3}\right)\]ซึ่งจากสูตรนี้ทำให้เราสามารถตอบคำถามข้อ 1 ได้ครับ

[tunococ]

ข้อแรก ผมก็คิดคล้าย ๆ หยั่งงี้แหละครับ

แต่ ทำไมมันถึงตอบข้อ 2 ได้ล่ะครับ?

(ข้อ 2 ผมคิดที่ mod 3 น่ะครับ มันจะได้ลำดับ 1 2 1 2 1 2...)

[nongtum]

กระทู้เงียบไปเลย ขอปล่อยระเบิดอีกลูกละกันครับ

20. จงหาจำนวนเต็มบวก x,y,z ทั้งหมดที่ทำให้ 4^x+4^y+4^z เป็นจำนวนจัตุรัส

[passer-by]

ข้อความเดิมของคุณ nooonuii:
16. จงพิสูจน์ว่ามีจำนวนเต็มบวก n ซึ่งทำให้ 2ⁿ ขึ้นต้นด้วย 2548 เมื่อเขียนเป็นเลขฐานสิบ

วิธีทำข้อนี้อย่างยากใช้ฟังก์ชันการหมุนวงกลมหนึ่งหน่วยด้วยมุมอตรรกยะครับ

ไม่ได้จะมาตั้งคำถามใหม่หรอกครับ แต่ติดใจข้อนี้เป็นพิเศษ

เพราะเมื่อไม่นานมานี้ ก็เพิ่งไปเจอ คำถามสไตล์นี้ มาเหมือนกัน แต่อยู่ในหัวข้อ combinatorics โจทย์มีอยู่ว่า
Prove that 2004 occurs in first four digit of 2ⁿ for infinitely many n

แล้วเขาก็ hint แค่ว่า log2 เป็นจำนวนอตรรกยะ

ตอนนี้ เหลือแต่ พิสูจน์ว่า มี infinitely many n ที่ทำให้

{log 2004} < nlog2 -๋nlog2๛ <{log2005}

(เมื่อ {x} แทน fractional part ของ x)

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

P.S. ทำไมการบ้านวิชา Dynamical system ถึงมีคำถามข้อนี้ได้ งงจัง ดูไม่น่าจะไปด้วยกันได้

[warut]

ลองอ่าน paper นี้ ดู เน้นที่ตรง Lemma 2 น่ะครับ

[passer-by]

หลังจากอ่าน proof ของ lemma 2 จาก paper ที่คุณ warut ให้ link ไว้ ตอนนี้ก็ get ทุกอย่าง แล้วครับ

จริงๆ ถ้าไม่สังเกต ผมก็ไม่รู้สึกนะเนี่ย ว่าปัญหาที่ผมไปเจอจะเป็นปัญหา combinatorics เพราะ ส่วนที่เอา combinatorics (pigeonhole principle) ไปใช้พิสูจน์ใน lemma 2 ดังกล่าว มันนิดเดียวจริงๆ ส่วนประเด็นหลัก อยู่ที่ การ มองช่วง [0,1] ให้เป็นวงกลมเส้นรอบวง 1 หน่วย แล้วหมุนทีละ 2px radian เมื่อ x เป็น จำนวนอตรรกยะ

แต่ก็ยังอยากรู้อยู่ดี ว่า การบ้านวิชา dynamical system ของคุณ nooonuii ทำไมมีคำถามประมาณนี้ด้วย เพราะ ถ้าคนไม่เคยเรียนวิชานี้มาก่อน (อย่างผม) เห็นชื่อวิชา แล้วจะรู้สึกถึง พวก nonlinear system/ differential equation อะไรทำนองนี้น่ะครับ

อ้อ ! เกือบลืม......ขอบคุณ คุณ warut สำหรับ paper มากๆ ครับ