ช่วยคิดด้วยครับ

[Tony]

จงหาสูตรของ (2ยกกำลัง m -1, 2ยกกำลัง n- 1 ) พร้อมทั้งพิสูจน์

[nooonuii]

คำตอบในรูปทั่วไปคือ (a^m-1,aⁿ-1) = a^(m,n) - 1 ครับ การพิสูจน์ค่อนข้างยาวแต่ไม่ยากครับ เลียนแบบ Euclidean Algorithm ถ้ามีหนังสือ เสริมความรู้มุ่งสู่คณิตศาสตร์โอลิมปิก ของ อาจารย์ดำรงค์ ทิพย์โยธา ก็ดีเลยครับ จะอยู่ตอนท้ายๆเล่ม เป็นชุดปัญหาจากง่ายไปยากครับ

[gon]

อ้า. นึกออกแล้วครับ. ว่าเคยตอบไปตรงหน้านี้ ไม่รู้ใช้ได้เปล่า หวังว่าไม่ผิดนะ Tmo

[Tony]

ขอบคุณมากครับ พี่gonและ พี่noonuii

แต่ผมมีคำถามอีกข้อหนึ่งคือ
จงหาสูตรของ (2^m - 1 , 2^n + 1) พร้อมทั้งพิสูจน์
(จงยกตัวอย่าง m, n ที่ทำให้ (2^m-1, 2^n+1)=1และน1)
คล้ายกับข้อแรกครับแต่เปลี่ยนเครื่องหมาย

คือที่ผมคิดไว้นั้นลองแทนค่าดูก่อน

=1
m=1,nฮN
m=2,n=2t tฮN
.
.
.
น1
m=2 n=3
m=4 n=3

แต่ยังหาข้อสรุปไม่ได้

พยายามหา ห.ร.ม. แบบยูคลิคก็ทำไม่ได้(ไม่รู้ทำถูกมั้ย)
ใครที่หาได้ช่วยบอกมาด้วยครับ

ขอบคุณมากครับ

[nooonuii]

น่าจะมีสองคำตอบครับ คือ 1 กับ 2 แต่อาจจะต้องแยกกรณีกันวุ่นวาย น่าจะมีวิธีคิดแจ๋วๆนะ

[warut]

อาศัยการแยกตัวประกอบโดยใช้ "cyclotomic polynomials" ทำให้ผมเชื่อว่า
คำตอบเป็นดังนี้ครับ

ให้ n = 2^rs โดยที่ s เป็นจำนวนคี่และ r เป็นจำนวนเต็มที่มากกว่าหรือเท่ากับ 0
จะได้ว่า (2^m - 1, 2ⁿ + 1) จะเท่ากับ 1 ถ้า 2^r+1 หาร m ได้ไม่ลงตัว
และจะเท่ากับ 2^(m,n) + 1 ถ้า 2^r+1 หาร m ลงตัว

สำหรับการพิสูจน์ผมขอละไว้เป็นการบ้านให้คนอื่นทำละกัน

[Tony]

เรขาคณิต
>> กระดาษซีรีส์เอคือกระดาษูปสี่เหลี่ยมผืนผ้าที่มีสมบัติว่า เมื่อแบ่งครึ่งด้วยเส้นตรงที่ขนานกับด้านกว้างแล้วจะได้กระดาษรูปสี่เหลี่ยมผืนผ้าสองรูป ที่คล้ายกับรูปสี่เหลี่ยมผืนผ้าเดิม ถ้าเส้นแทยงมุม DB ของกระดาษรูปสี่เหลียยมผืนผ้า ABCDถูกแบ่งเป็นสามส่วนที่มีความยาวเท่ากัน โดยเส้นขนาน L1 และ L2 ซึ่งผ่านจุด A และ C และตั้งฉากกับDB แล้วจงแสดงว่า กระดาษ ดังกล่าวเป็นกระดาษซีรีส์เอ

[Tony]

ทฤษฎีจำนวน
>> ในโรงเรียนแห่งหนึ่งมีล็อกเกอร์ 200 ลอกเกอร์ สำหรับนักเรียน 200 คน นักเรียน 200 คนมาตรวจล็อกเกอร์ โดยนักเรียนคนแรกตรงไปเปิดล็อกเกอร์ทุกบาน นักเรียนคนที่ 2 ตรวจล็อกเกอร์เลขคู่ถ้าล็อกเกอร์เปิดอยู่ก็จะปิด นักเรียนคนที่3 ไปตรวจล็อกเกอร์ที่ 3 ,6 ,... โดยเว้นทีละ 3 ถ้าพบล็อกเกอร์ที่เปิดอยู่ก็จะปิด และถ้าพบที่ปิดอยู่ก็จะเปิด หลังจากนั้นนักเรียนคนที่4 ตรวจล็อกเกอร์ที่ 4, 8, ... และทำเช่นเดียวกับคนที่ 3 ทำเช่นนี้ไปเรื่อยๆจนครบ 200 คน จงหาว่ามีล็อกเกอร์ที่เปิดอยู่กี่บาน

[gon]

ข้อทฤษฎีจำนวน จำได้ว่าเห็นมาหลายรอบมาก ๆ แล้วครับ. แล้วที่เล่นไปถึง 1000 ลอกเกอร์เลยมั้ง แต่ไม่เคยคิดจริง ๆ สักทีเลย เมื่อครู่ลองคิดดูบ้างแต่คิดว่าคงไม่ใช่แนวคิดที่ดีมากนัก ต้องลองไปคิดต่อดูอีกหน่อย หรือ ใครจะเสนอแนวคิดที่ง่ายกว่านี้ก็เอาเลยนะครับ. ผมคิดว่ามีง่ายกว่านี้

ที่ลอง ๆ คิดดู เราสามารถรู้ได้ง่าย ๆ ว่าลอกเกอร์หมายเลขไหน สุดท้ายแล้วเปิดหรือปิดได้จาก จำนวนตัวประกอบที่เป็นบวกของจำนวนนั้น ถ้าได้คี่ก็แสดงว่าลอกเกอร์นั้นเปิดอยู่ ถ้าได้คู่ก็ปิด เช่น ตัวประกอบของ 6 มี 4 จำนวน คือ 1, 2, 3, 6 แสดงว่าลอกเกอร์หมายเลข 6 จะปิด หรือ อย่าง 120 = (2³)(3)(5) ซึ่งจะมีตัวประกอบที่เป็นบวกอยู่ทั้งหมด (3+1)(1+1)(1+1) = 16 จำนวน แสดงว่าก็ปิดอีกเช่นกัน

และ จะเห็นได้ว่าลอกเกอร์หมายเลข 1 ต้องเปิดแน่นอน บางทีมันอาจจะเกี่ยวกับ Euler phi function ซึ่งอาจจะได้ความจริงง่าย ๆ บางอย่างว่า จำนวนตัวประกอบของมันจะเป็นจำนวนคู่ เมื่อใดบ้าง ....

[warut]

อ้าว...ผมเพิ่งจะเห็นนะเนี่ยว่ามีโจทย์ทฤษฎีจำนวนน่าสนใจมากอยู่ตรงนี้ข้อนึง และผม
ก็ไม่เคยเห็นที่อื่นมาก่อนด้วยสิ

เอ่อ...ว่าแต่ข้อที่แล้วที่ผมตอบไปถูกผิดประการใดคุณ Tony ช่วยแจ้งให้ทราบด้วย
จะเป็นพระคุณยิ่งครับ

สำหรับโจทย์ข้อใหม่นี้คำตอบสำหรับกรณี n ล็อกเกอร์ก็คือ \(\lfloor\sqrt n\rfloor\)
ดังนั้นถ้า n = 200 จะได้คำตอบคือมีล็อกเกอร์เปิดอยู่เท่ากับ \(\lfloor\sqrt{200}\rfloor\) = 14 ล็อกเกอร์

สำหรับรายละเอียดที่มาของสูตรผมจะมาโพสต์ภายหลังครับ หรือใครมีเวลาว่างพิมพ์
ก็ช่วยอธิบายไปก่อนได้เลย ที่บอกได้ตอนนี้คือคุณ gon เริ่มไปถูกทางแล้วครับ (แต่ไม่
เกี่ยวกับ Euler's f function นะ) แต่ยังคงต้องไปต่ออีกนิดหน่อยจึงจะไปถึง
คำตอบข้างบน

[Tony]

ถึงคุณ warut นะครับ
พอดีผมไม่รู้เรื่อง"cyclotomic polynomials"(ช่วยชี้แจงด้วยนะครับ หรือเรื่องนี้เรียนในไหนครับ ขอบพระคุณอย่างสูง)

แต่ผมลองแทนค่าดูแล้วก็น่าจะถูกต้อง

และขอบคุญพี่ gon มากครับ
ผมก็คิดคล้ายๆแบบนี้เหมือนกัน
เช่น 1=1 เปิด
2=1*2 เปิด-ปิด
3=1*3 เปิด-ปิด
4=1*2*2 เปิด-ปิด-เปิด
.
.
.
ยังไม่รู้ว่าจนถึง 200 จะเปิดเท่าไร

[warut]

ที่มาของสูตรเป็นดังนี้ครับ

ให้ d(m) แทนจำนวนของตัวประกอบที่เป็นบวกทั้งหมดของ m

เพื่อที่จะหาว่าในล็อกเกอร์ n ล็อกเกอร์นั้นมีล็อกเกอร์ใดเปิดอยู่บ้าง เราสามารถทำได้
โดยหาว่ามีจำนวนนับ m ที่อยู่ในช่วง [1, n] ทั้งหมดกี่ตัวที่ d(m) เป็นจำนวนคี่

ถ้า m = \(p_1^{r_1}p_2^{r_2}\dots p_k^{r_k}\) > 1
โดยที่ p₁, p₂, ... , p_k เป็นจำนวนเฉพาะที่ต่างกันและ r₁, r₂, ... , r_k เป็นจำนวนเต็มบวก
(นั่นคือเขียน m ในรูปของ "prime factorization") แล้วเราจะได้ว่า
d(m) = (r₁ + 1)(r₂ + 1)...(r_k + 1)

จะเห็นว่า d(m) จะเป็นเลขคี่ก็ต่อเมื่อ r₁, r₂, ... , r_k เป็นเลขคู่ทั้งหมด
ซึ่ง r₁, r₂, ... , r_k จะเป็นเลขคู่หมดทุกตัวก็ต่อเมื่อ m เป็นเลขกำลังสองสมบูรณ์

ดังนั้นคำตอบที่เราต้องการก็คือจำนวนของเลขกำลังสองสมบูรณ์ทั้งหมดที่อยู่ในช่วง
[1, n] ซึ่งมีค่าเท่ากับ \(\lfloor\sqrt n \rfloor\) เมื่อ ๋ ๛ แทนสัญลักษณ์ของ floor function (หรือ
greatest integer function นั่นเอง)

[nooonuii]

อ่า สรุปว่าสูตรอยู่ในรูป floor function ไม่ใช่ ceiling function ใช่มั้ยครับ

[R-Tummykung de Lamar]

ดังนั้นถ้า n = 200 จะได้คำตอบคือมีล็อกเกอร์เปิดอยู่เท่ากับ \(\lfloor\sqrt{200}\rfloor\) = 14 ล็อกเกอร์

น่าจะเป็น floor มากกว่าครับ๋๛

[Tony]

เข้าใจแล้วครับ
ขอบคุณมากครับ