Theppitak's blog

My personal blog.

29 กรกฎาคม 2547

โจทย์ติดแสตมป์

พอดีไปเจอโจทย์ในหนังสือ ว่าให้พิสูจน์ว่า:

  • ถ้ามีแสตมป์ 3 บาท และ 7 บาท จำนวนไม่จำกัด จะสามารถติดแสตมป์ราคาตั้งแต่ 12 บาทขึ้นไป ได้ทุกราคาที่เป็นจำนวนเต็ม
  • ถ้ามีแสตมป์ 4 บาท และ 9 บาท จำนวนไม่จำกัด จะสามารถติดแสตมป์ราคาตั้งแต่ 24 บาทขึ้นไป ได้ทุกราคาที่เป็นจำนวนเต็ม

ก็พิสูจน์ได้ไม่ยาก แต่ทำให้เกิดความสงสัยว่า ถ้าโจทย์เป็นอย่างนี้ล่ะ?

มีแสตมป์ราคา n และ m บาท จำนวนไม่จำกัด โดยที่ n และ m เป็นจำนวนเต็มที่ relative prime ซึ่งกันและกัน (กล่าวคือ gcd(n,m) = 1) ราคาต่ำสุดที่จะสามารถติดแสตมป์ได้ทุกราคาคือเท่าใด?

นั่งคิดไปคิดมา ยังไม่ทันออก พอดีว่าน้องชายกลับมาเยี่ยมบ้าน เลยเอามาคุยเล่นกัน ปรากฏว่ามัน solve ออกภายในไม่ถึง 20 นาที -_-!

ใครคิดออกแล้วลองดู Goldbach's conjecture ต่อละกัน ปัญหาสะท้านโลกเชียวนะนั่น

2 ความเห็น:

  • 30 กรกฎาคม 2547 16:47 , Blogger fat dog father แถลง…

    ผมไม่ค่อยเก่งเลขน่ะครับ เลยพิสูจน์โจทย์ติดแสตมป์เสียเวลาไป 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 , Blogger 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 วัน)

<< กลับหน้าแรก

hacker emblem