Skocimis

0015

ให้ A<B<CA < B < C แทนตำแหน่งของจิงโจ้ทั้งสามตัวตามโจทย์

ขั้นแรก เราจะให้เหตุผลว่ามีวิธีที่จิงโจ้สามารถกระโดดได้ C−B−1C - B - 1 ตา โดย

  1. จิงโจ้ตัวแรกกระโดดจาก AA ไป B+1B+1
  2. จิงโจ้ตัวที่สองกระโดดจาก BB ไป B+2B+2
  3. จิงโจ้ตัวแรกกระโดดจาก B+1B+1 ไป B+3B+3
  4. ไปเรื่อย ๆ จนไม่สามารถกระโดดต่อได้ จะได้ C−B−1C - B - 1 ตา พอดี

ด้วยเหตุผลเดียวกัน มีวิธีที่จิงโจ้สามารถกระโดดได้ B−A−1B - A - 1 ตา โดย

  1. จิงโจ้ตัวที่สามกระโดดจาก CC ไป A+1A+1
  2. จิงโจ้ตัวที่สองกระโดดจาก AA ไป A+2A+2
  3. จิงโจ้ตัวที่สามกระโดดจาก A+1A+1 ไป A+3A+3
  4. ไปเรื่อย ๆ จนไม่สามารถกระโดดต่อได้ จะได้ B−A−1B - A - 1 ตา พอดี

ถึงตรงนี้ คำตอบจะเป็นอย่างน้อย max(B−A−1,C−B−1)\text{max}(B-A-1, C-B-1). เราสามารถพิสูจน์ต่อได้ว่าจิงโจ้จะเล่นมากกว่านั้นไม่ได้โดยใช้หลักการ mathematical induction

บทพิสูจน์: ค่อนข้างชัดเจนว่าในกรณีที่ max(B−A−1,C−B−1)=1\text{max}(B-A-1, C-B-1) = 1 จิงโจ้จะเล่นได้อย่างมากแค่ 1 ตา เราจึงสมมติว่าจิงโจ้เล่นได้มากสุด max(B−A−1,C−B−1)\text{max}(B-A-1, C-B-1) ตาเสมอเมื่อ max(B−A−1,C−B−1)≤n\text{max}(B-A-1, C-B-1) \le n สำหรับจำนวนเต็ม nn จำนวนหนึ่ง เพื่อพิสูจน์ เราจะต้องแสดงว่าเมื่อ max(B−A−1,C−B−1)=n+1\text{max}(B-A-1, C-B-1) = n+1 จิงโจ้จะเล่นได้มากสุด n+1n+1 ตาเท่านั้น

เมื่อ max(B−A−1,C−B−1)=n+1\text{max}(B-A-1, C-B-1) = n+1 ในตาแรก ไม่จิงโจ้ตัวแรกก็ตัวที่สามต้องกระโดด สมมติให้เป็นตัวแรก จิงโจ้จะต้องกระโดดไประหว่างอีกสองตัว นั่นคือกระโดดไปที่ A′A' เมื่อ B<A′<CB < A' < C. เรารู้ว่า max(A′−B−1,C−A′−1)≤n\text{max}(A'-B-1, C-A'-1) \le n ดังนั้นจิงโจ้จะกระโดดได้อีกไม่เกิน nn ครั้ง เมื่อรวมกับที่จิงโจ้กระโดดในตาแรกจะเป็น n+1n+1 ครั้ง

ดังนั้นคำตอบคือ max(B−A−1,C−B−1)\text{max}(B-A-1, C-B-1)