โจทย์ติดแสตมป์
พอดีไปเจอโจทย์ในหนังสือ ว่าให้พิสูจน์ว่า:
- ถ้ามีแสตมป์ 3 บาท และ 7 บาท จำนวนไม่จำกัด จะสามารถติดแสตมป์ราคาตั้งแต่ 12 บาทขึ้นไป ได้ทุกราคาที่เป็นจำนวนเต็ม
- ถ้ามีแสตมป์ 4 บาท และ 9 บาท จำนวนไม่จำกัด จะสามารถติดแสตมป์ราคาตั้งแต่ 24 บาทขึ้นไป ได้ทุกราคาที่เป็นจำนวนเต็ม
ก็พิสูจน์ได้ไม่ยาก แต่ทำให้เกิดความสงสัยว่า ถ้าโจทย์เป็นอย่างนี้ล่ะ?
มีแสตมป์ราคา n และ m บาท จำนวนไม่จำกัด โดยที่ n และ m เป็นจำนวนเต็มที่ relative prime ซึ่งกันและกัน (กล่าวคือ gcd(n,m) = 1) ราคาต่ำสุดที่จะสามารถติดแสตมป์ได้ทุกราคาคือเท่าใด?
นั่งคิดไปคิดมา ยังไม่ทันออก พอดีว่าน้องชายกลับมาเยี่ยมบ้าน เลยเอามาคุยเล่นกัน ปรากฏว่ามัน solve ออกภายในไม่ถึง 20 นาที -_-!
ใครคิดออกแล้วลองดู Goldbach's conjecture ต่อละกัน ปัญหาสะท้านโลกเชียวนะนั่น
บันทึกโดย Thep ณ
23:37
2 ความเห็น:
ณ 30 กรกฎาคม 2547 เวลา 16:47 ,
Beamer User แถลง…
ผมไม่ค่อยเก่งเลขน่ะครับ เลยพิสูจน์โจทย์ติดแสตมป์เสียเวลาไป 2-3 ชั่วโมง
เหมือนกัน และไม่รู้ว่ามีระเบียบแบบแผนพอหรือเปล่า ผมพิสูจน์ข้อแรกดังนี้
a = 0, 1, 2, 3, ..., Inf
เราสามารถเขียนลำดับนี้ใหม่ได้เป็น
a = 2n(3), 2n(3)+1, 2n(3)+2, (2n+1)(3), (2n+1)(3)+1, (2n+1)(3)+2, ..., Inf
เมื่อ n = 0, 1, 2, 3, ...
เนื่องจาก 7 = 2(3) + 1 ดังนั้นเราสามารถจัดลำดับข้างต้นในรูปของผลบวกระหว่าง
3 กับ 7 ได้ดังนี้
a = 2n(3), 2(n-1)(3)+7, 2(n-2)(3)+2(7), (2n+1)(3), (2n-1)(3)+7, (2n-3)(3)+2(7), ..., Inf
และเนื่องจากจำนวนแสตมป์เป็นลบไม่ได้ ค่าต่ำสุดของ n ในที่นี้ต้องเป็น 2
นั่นคือเลขต่ำสุดสำหรับโจทย์ข้อนี้คือ 2(2)(3) = 12 นั่นเอง
ซึ่งถ้าการพิสูจน์แบบนี้ยอมรับได้ ข้อสองก็พิสูจน์ได้ไม่ยาก และรวมไปถึง
คู่ลำดับ 5-11, 6-13, 7-15, ... ด้วยกระมัง
ส่วนโจทย์ข้อสามลืมไปแล้วว่า relative prime มันคืออะไร เลยทำไม่ได้
ยังไงช่วยชี้แนะด้วยน่ะครับ
ณ 30 กรกฎาคม 2547 เวลา 21:35 ,
Thep แถลง…
วิธีของพี่จอยน่าสนใจมากครับ ดู analytic ดี วิธีพิสูจน์สองข้อแรกผมใช้ induction อะครับ ซึ่งถึกเอาการถ้าตัวเลขใหญ่ๆ และนำไปสู่ข้อสามค่อนข้างยาก (น้องผมใช้อีก approach ไปเลย ซึ่งต้องนับถือจินตนาการของเขา ที่ทำให้ตรงสู่คำตอบทันที)
ตัวเลขที่เป็น relative prime ซึ่งกันและกัน ก็ไม่มีอะไรมากครับ แค่ ห.ร.ม. เป็น 1 เท่านั้นเอง เช่น 6 กับ 9 ถือว่าไม่ relative prime ซึ่งกันและกัน เพราะ gcd(6,9) = 3 แต่ 33 กับ 35 ถือว่า relative prime ซึ่งกันและกัน เพราะ gcd(33,35) = 1 ถึงแม้แต่ละตัวจะไม่ใช่เลข prime (ที่กำหนดอย่างนี้ เพราะถ้าราคาแสตมป์ย่อยมีตัวประกอบร่วม ผลบวกของมันก็จะเป็นจำนวนเท่าของ ห.ร.ม. ทำให้ผลรวมมันกระโดด ไม่ได้ทุกราคา)
แสดงความเห็น (มีการกลั่นกรองสำหรับ blog ที่เก่ากว่า 14 วัน)
<< กลับหน้าแรก