צפרדע יושבת על צומת (כלומר נקודה ששיעוריה הם מספרים שלמים) במישור קרטזי. בקפיצה ראשונה היא יכולה לקפוץ לכל צומת אחרת. בקפיצות הבאות היא חייבת לשמור כל הזמן על אותו וקטור (כלומר אותו כיוון ואותו אורך; למשל, אם היא קפצה מ-(3,7) ל-(10,6) אז הקפיצה הבאה תהיה ל-(17,5) ואחריה (24,4) וכן הלאה) המטרה היא לגלות היכן ממוקמת הצפרדע. המשחק הולך בצורה כזאת: בכל פעם עליך לנחש נקודה מסוימת. אם טעית, הצפרדע קופצת פעם אחת, ואחר כך אתה מנסה שוב למצוא את הנקודה, ושוב הצפרדע קופצת, וכן הלאה. נקודת ההתחלה ווקטור הקפיצה אינם ידועים. האם אפשר לגלות תמיד, במספר סופי של ניסיונות, היכן הצפרדע?
| רמז
|
| נסו לפתור קודם עבור המקרה החד-ממדי
|
|
| פתרון
|
| פתרון עבור המקרה החד-ממדי: נסמן את נקודה ההתחלה של הצפרדע ב-x, את גודל הקפיצה ב-a, ואת מספר השלב ב-t. בכל שלב, מיקום הצפרדע הוא x+ta. t ידוע, ולפיכך יש למצוא את x ואת a. כידוע, קבוצת המספרים הטבעיים וקבוצת הזוגות של מספרים שלמים הן שקולות, ועל כן נוכל "להצמיד" לכל שלב זוג (x,a) באופן שנכסה את כל הזוגות. לכן בכל תור יש לחשב את x+ta המתאים, ולנחש באותו מקום, וכיוון שההתאמה היא על, מובטח שנגיע בשלב מסוים לנקודה הנכונה.
קל להכליל את הפתרון למקרה הדו-ממדי: הפעם יש ארבעה משתנים x,y,a,b כאשר (x,y) היא נקודת ההתחלה ו-(a,b) הוא וקטור הקפיצה. כיוון שקיימת התאמה גם בין קבוצת הטבעיים לרביעיות של שלמים, הפתרון יעבוד גם פה.
|
|