Number Theory Marathon

[tunococ]

ช่วยดูให้ด้วยนะครับ ไม่ค่อยแน่ใจ แล้วก็รู้สึกว่าวิธีไม่ค่อยดีด้วย

เนื่องจาก \(7^4 > 1599\) เลยรู้ว่า \(a_i \in \{1, 2, 3, 4, 5, 6\}\) จึงแปลงโจทย์ได้เป็น

\[
A + 16B + 81C + 256D + 625E + 1296F = 1599
\]
\[
A + B + C + D + E + F = 14
\]
โดยที่ \(A, B, C, D, E, F\) เป็นจำนวนเต็มบวกหรือ 0

พอเอาอันบนลบอันล่าง ก็จะได้

\[
15B + 80C + 255D + 624E + 1295F = 1585
\]

ตอนนี้จะสรุปได้ว่า \(E = 0\) และ \(F = 0\) หรือ \(1\)

เอา \(E\) ออก แล้วหารด้วย 5 จะได้
\[
3B + 16C + 51D + 259F = 317
\]
\[
3(B + 17D) = 317 - 16C - 259F
\]

สมมติว่า \(F = 0\) ก่อน จะได้ว่า
\[
3(B + 17D) = 317 - 16C
\]
เพื่อให้ \(3 | 317 - 16C\) จะได้ว่า C ที่เป็นไปได้คือ 2, 5, 8, 11 หรือ 14 แทนแต่ละค่าลงไปในสมการ จะได้ว่า
\[
B + 17D = 95, 79, 63, 47, 31
\]
นำไปรวมกับ \(A + B + C + D = 14\) จะรู้ว่าไม่ได้คำตอบ เพราะ \(B + D \ge 15\) ทุกกรณี
(95 = (5)17 + 10, 79 = (4)17 + 11, 63 = (3)17 + 12, 47 = (2)17 + 13, 31 = (1)17 + 14)

แล้วลองพิจารณาเมื่อ \(F = 1\) บ้าง จะเห็นว่า
\[
3(B + 17D) = 58 - 16C
\]
ค่า C ที่เป็นไปได้มีเพียงค่าเดียวคือ \(C = 1\) ซึ่งเมื่อแทนลงไป จะได้ว่า
\[
B + 17D = 14
\]
ทำให้ \(B = 14\) ในขณะที่ \(C = F = 1\) ดังนั้น เมื่อรวมกับสมการ \(A + B + C + D + F = 14\) จะไม่มีคำตอบ

สรุปว่าไม่มีคำตอบครับ ... วิธีนี้ใช้แต่แรงงานอ่า อยากได้วิธีที่ดีกว่านี้อะคับ

[tunococ]

ที่ไม่มีคนมาเล่นต่อ เป็นเพราะผมไม่ได้ตั้งคำถามรึเปล่าอะ ... คิดคำถามไม่ค่อยเป็นซะด้วย

เอาอันนี้ละกัน โจทย์ง่าย ๆ ได้จากเพื่อน

12. กำหนดฟังก์ชัน \(A(x) = 2x \ mod \ (2n + 1)\) (a mod b = เศษจากการหาร a ด้วย b ซึ่งมีค่าตั้งแต่ 0 ถึง b - 1)

1. จงแสดงว่า \(A(x)\) เป็น permutation บนเซต \(\{1, 2, 3, ..., 2n\}\)
2. ให้ \(A^n(x) = A(A(A(...(x)))\) (composition \(n\) ครั้ง) จงพิสูจน์ว่า ถ้า \(A^m(1) = 1\) แล้ว \(A^m(x) = x\) สำหรับทุก \(x \in \{1, 2, 3, ..., 2n\}\)

Edit: ใส่เลขข้อ

[nooonuii]

ข้อความเดิมของคุณ tunococ:
ที่ไม่มีคนมาเล่นต่อ เป็นเพราะผมไม่ได้ตั้งคำถามรึเปล่าอะ ... คิดคำถามไม่ค่อยเป็นซะด้วย

เอาอันนี้ละกัน โจทย์ง่าย ๆ ได้จากเพื่อน

กำหนดฟังก์ชัน \(A(x) = 2x \ mod \ (2n + 1)\) (a mod b = เศษจากการหาร a ด้วย b ซึ่งมีค่าตั้งแต่ 0 ถึง b - 1)

1. จงแสดงว่า \(A(x)\) เป็น permutation บนเซต \(\{1, 2, 3, ..., 2n\}\)
2. ให้ \(A^n(x) = A(A(A(...(x)))\) (composition \(n\) ครั้ง) จงพิสูจน์ว่า ถ้า \(A^m(1) = 1\) แล้ว \(A^m(x) = x\) สำหรับทุก \(x \in \{1, 2, 3, ..., 2n\}\)

ขอเล่นด้วยคนครับ
ก่อนอื่นผมว่าโดเมนของ A(x) เป็นเซต {0,1,...,2n} ก็ได้ ซึ่งผมขอใช้เซตนี้เป็นโดเมนของ A(x) นะครับ

1. นิยาม B(x) = (n+1)x (mod 2n+1)
จะได้ว่า BoA(x) = x (mod 2n+1) สำหรับ x = 0,1,...,2n
ดังนั้น A(x) เป็นฟังก์ชันหนึ่งต่อหนึ่งบนเซต {0,1,2,...,2n}
แต่ A(x) นิยามบนเซตจำกัด จึงได้ว่า A(x) เป็นฟังก์ชันทั่วถึงด้วย
นั่นคือ A(x) เป็น permutation

2. A^m(x) = 2^mx (mod 2n+1)
จากเงื่อนไขจะได้ว่า 2^m = 1 (mod 2n+1)
ดังนั้น A^m(x) = 2^mx = x (mod 2n+1)


รอเจ้าของโจทย์มาตรวจก่อนครับ เดี๋ยวมาโพสข้อต่อไป

[tunococ]

ถูกแล้วล่ะครับ

อ้อ แล้วที่ผมกำหนดโดเมนเป็น \(\{1, 2, 3, ..., 2n\}\) น่ะ เพราะว่าจริง ๆ มันมีโจทย์อีกข้อด้วย :P แต่ไม่ได้ถามเพราะมันเป็นโจทย์ algorithm น่ะครับ จริง ๆ A เป็น permutation บนโดเมน \(\{0, 1, 2, ..., 2n\}\) อย่างที่ว่าแหละครับ

[nooonuii]

มาแล้วครับโจทย์ของผม ไม่ยากครับ แถมแอบๆไปทางพีชคณิตมากกว่า

13. ให้ n เป็นจำนวนนับ และ p(x) = x² + ax + b เมื่อ a,b เป็นจำนวนเต็ม
จงพิสูจน์ว่ามีจำนวนเต็ม k ซึ่งทำให้
\[ \Large{p(n)p(n+1) = p(k)} \]

Edit: ใส่เลขข้อ

[nongtum]

ข้อความเดิมของคุณ nooonuii:

ให้ n เป็นจำนวนนับ และ p(x) = x² + ax + b เมื่อ a,b เป็นจำนวนเต็ม
จงพิสูจน์ว่ามีจำนวนเต็ม k ซึ่งทำให้
\[ \Large{p(n)p(n+1) = p(k)} \]

เป็นการเพียงพอที่จะแสดงว่า \(4p(n)p(n+1)+a^2-4b\) เป็นกำลังสองสมบูรณ์ (ซึ่งกำลังสองที่ว่ามีค่าเท่ากับ (2k+a)²)
จากรูปด้านล่าง เราจะได้ k=n²+an+n+b เป็นจำนวนเต็มที่ต้องการหา

ปล. คงไม่ต้องบอกนะครับว่าคิดยังไง เพราะข้อนี้ลองทดด้วยมือมาสองวันแล้วแยก factor ไม่ออก

[nongtum]

เกือบลืมตั้งคำถามข้อต่อไป

14. จงหาจำนวนนับ k ทั้งหมดที่ทำให้ 1^k+9^k+10^k=5^k+6^k+11^k

[nooonuii]

ข้อความเดิมของคุณ nooonuii:

ให้ n เป็นจำนวนนับ และ p(x) = x² + ax + b เมื่อ a,b เป็นจำนวนเต็ม
จงพิสูจน์ว่ามีจำนวนเต็ม k ซึ่งทำให้
\[ \Large{p(n)p(n+1) = p(k)} \]

คุณ Nongtum ความพยายามเป็นเลิศจริงๆครับ

My Solution

ให้ Q(x) = P(n+x) = x² + (2n+a)x + (n²+an+b)
ดังนั้น P(n)P(n+1) = Q(0)Q(1) = [n²+an+b][1 + (2n+a) + (n²+an+b)] = Q(n²+an+b) = P(n+(n²+an+b))

[tunococ]

โจทย์ของ nongtum ตอบว่า 2 กับ 4 ครับ

ผมคิดโดยแทนค่าทั้งหมดที่เป็นไปได้น่ะครับ แล้วมันได้แค่ 2 กับ 4

วิธีหาค่าที่เป็นไปได้ 2 เซตของผม เอามา intersect กัน คือ

1. คิดที่ mod 3 จะรู้ว่า k ต้องเป็นเลขคู่

2. หา upperbound ของ k

เนื่องจาก \(1^k < 5^k + 6^k\) อยู่แล้ว ต้องการหาค่า n ที่ทำให้ \(9^n + 10^n < 11^n\) เพื่อจะสรุปว่าฝั่งซ้าย น้อยกว่าฝั่งกว่า เมื่อ \(k \ge n\)

ลองแทนค่าเอาจะเห็นว่า \(n = 5\) เป็นค่า \(n\) ที่น้อยที่สุด ดังนั้น ค่า k มากที่สุดที่เป็นคำตอบได้คือ 4 คำตอบที่เป็นไปได้ก็เลยมีแค่ 2 กับ 4 เท่านั้น โชคดีที่มันใช้ได้ทั้งคู่

ถ้าไม่แทนค่าเอา จะคิดเอาก็ได้ครับ วิธีขี้เกียจหน่อยก็จะให้ค่า n = 8 ซึ่งก็ไม่มากเกินแรงเครื่องคิดเลขจิ้มครับ เพราะตัวที่ต้องทดลองเพิ่มมีตัวเดียวคือ k = 6 (ทดลองที่ mod 6 ก็จะเห็นว่าไม่ได้)

วิธีขี้เกียจของผมก็คือ

\[
\begin{eqnarray}
9^n + 10^n \le 10^n + 10^n = 2 \times 10^n & < & 11^n \\
\log 2 + n \log 10 & < & n \log 11 \\
\frac{\log 2}{\log 11 - 1} & < & n \\
7 & < & n
\end{eqnarray}
\]
ไม่รู้จะถามอะไรต่อดีอะ ...

[warut]

ข้อความเดิมของคุณ gools:
11. จงหาจำนวนคำตอบที่เป็นจำนวนเต็มบวกของสมการ
\[a_1^4+a_2^4+...+a_{14}^4=1,599\]

ถ้า a เป็นจำนวนคู่ แล้ว \(a^4\equiv0\pmod{16}\)
ถ้า a เป็นจำนวนคี่ แล้ว \(a^4\equiv1\pmod{16}\)
ดังนั้น least residue modulo 16 ของ \(a_1^4+a_2^4+...+a_{14}^4\) จึงมีค่าอยู่ระหว่าง 0 ถึง 14
แต่ least residue modulo 16 ของ 1599 มีค่าเท่ากับ 15 ดังนั้นสมการนี้จึงไม่มีคำตอบครับ

Edit: ใส่เลขข้อ

[tunococ]

เย่ ๆ มีคนมาตอบวิธีดี ๆ ให้แล้ว ขอบคุณครับ

[nongtum]

กระทู้นี้เงียบสนิท(ข้อ 14 ถูกแล้วครับ) เอาเป็นว่าขอตั้งคำถามอีกข้อละกัน

15. จำนวน \(1991^{1991}+1992^{1992}+1993^{1993}+1994^{1994}+1995^{1995}+1996^{1996} \) เป็นจำนวนจัตุรัสหรือไม่

[nooonuii]

ข้อความเดิมของคุณ nongtum:
กระทู้นี้เงียบสนิท(ข้อ 14 ถูกแล้วครับ) เอาเป็นว่าขอตั้งคำถามอีกข้อละกัน

15. จำนวน \(1991^{1991}+1992^{1992}+1993^{1993}+1994^{1994}+1995^{1995}+1996^{1996} \) เป็นจำนวนจัตุรัสหรือไม่

My Solution

ไม่เป็นครับ เพราะสมการ x² = -1 ไม่มีคำตอบใน Z₄

[nooonuii]

โจทย์ข้อนี้ผมไม่แน่ใจว่าจะใช้ความรู้ทฤษฎีจำนวนพื้นฐานแก้ได้รึเปล่าครับ ยังไม่เคยลองเหมือนกัน ข้อนี้เป็นการบ้านวิชา Dynamical Systems ที่ผมกำลังเรียนอยู่ครับ

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

[nongtum]

ข้อ 16 ของคุณ nooonuii ผมขอเสนอ'แนวคิด'ดังนี้ครับ ไม่รู้ว่าจะพอไหวไหม...

หากมี n ที่ว่าจริง จะต้องมีจำนวนเต็มบวก d ที่ทำให้ \(2548\cdot10^d<2^n<2549\cdot10^d\) เนื่องจาก \(\log_22549-\log_22548\approx0.0006...\) จะได้ว่า \(1-(เลขหลังจุดทศนิยมของ\log_{2}(2548\cdot10^d))<0.0006\) ซึ่งสามารถแก้ได้หลายแบบ ทั้งแทนค่าแล้วดูค่า d ที่ใกล้กับจำนวนเต็มหรือวิธีอื่นๆซึ่งจะไม่กล่าวในที่นี้ (โจทย์ถามแค่ว่ามีหรือไม่ ไม่ได้ถามว่าหาอย่างไร)

หมายเหตุ: เท่าที่ลองใช้คอมคิด พบว่า d>300 ส่วนที่ว่าจะมี d ที่สอดคล้องเงื่อนไขมากกว่าหนึ่งตัวหรือไม่ไม่ได้คิดครับ(แต่คาดว่ามีมากกว่าหนึ่งแน่ๆ)