חידת צפרדע

בשבוע הקרוב לא אהיה כאן עקב נסיעה לחו”ל. בינתיים, אעשה כמעשה הארדי ואצהיר שעלה בידי להוכיח את השערת רימן ואציג את ההוכחה מייד עם שובי, ובנוסף אציג חידה לא קשה אך חביבה מאוד:

יש לנו צפרדע שנמצאת במקום כלשהו על גבי ציר המספרים הטבעיים (כלומר, המיקום שלה הוא מספר טבעי כלשהו). החל מרגע מסויים ניתנת מכה בגונג, והמשחק מתחיל: בכל סיבוב הצפרדע קופצת k צעדים ימינה על הציר (כלומר, עוברת מהמספר x שבו שהתה קודם למספר x+k), ומייד אחרי שקפצה, אני בודק את אחד מהמספרים שעל הציר, על פי בחירתי. אם הצפרדע נמצאת שם, הרי ש”תפסתי אותה” וניצחתי; אחרת, ממשיכים לתור הבא.

לא ידוע לי איפה הצפרדע הייתה בתחילת המשחק, ולא ידוע לי מהו ה-k של גודל הקפיצה שלה (אבל ידוע שהיא תמיד קופצת k צעדים ימינה). החידה: צריך למצוא אלגוריתם כלשהו שמבטיח לי שתמיד אצליח לתפוס את הצפרדע אחרי מספר סופי של צעדים.

בהצלחה!