חידת צפרדע - הפתרון

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

אז מה היה לנו? צפרדע שמתחילה לנוע מהנקודה x ונעה k צעדים ימינה בכל צעד, כאשר x,k שניהם מספרים טבעיים. האבחנה הראשונה, ולטעמי החשובה והמרכזית בחידה, היא ששני הפרמטרים הללו - x,k - מאפיינים בצורה יחידה את המסלול שתעבור הצפרדע. אם אנחנו יודעים מהם, אנחנו יכולים לדעת איפה תהיה הצפרדע בכל רגע נתון.

זהו למעשה מקרה פרטי של מושג כללי יותר מקינמטיקה בסיסית - תנועה במהירות קבועה. גם תנועה במהירות קבועה מאופיינת על ידי שני פרמטרים: המיקום בעת תחילת התנועה, ומהירות התנועה. כאן x הוא המיקום ו-k הוא המהירות. משוואת התנועה במקרה זה היא \( f(t)=x+kt \) - כלומר, המיקום של הצפרדע בזמן t (כאשר t יכול לקבל רק ערכים טבעיים - הוא בעצם סופר את מספר הצעדים של הצפרדע) שווה למיקום ההתחלתי של הצפרדע ועוד המרחק שהספיקה לעבור (אם היא ביצעה צעד אחד, היא נעה k מספרים ימינה על הציר; אם היא ביצעה שני צעדים הרי שהיא זזה 2k צעדים וכן הלאה).

מכאן עולה שיטת ההתמודדות שלנו עם בעיית הצפרדע: בכל סיבוב “ננחש” ערכים אחרים עבור x,k. אם נזכור כמה נסיונות כושלים היו לנו עד עכשיו - כלומר, מהו t - נוכל לבדוק במדוייק עבור אותם ערכים של x,k האם צדקנו (כלומר, נבצע בדיקה במספר x+kt). בפסאודו קוד הדבר יראה ככה:

• t=0
• לכל (x,k) בצע:
  • t=t+1
  • אם הצפרדע נמצאת ב-x+kt, החזר "ניצחתי!"

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

כדי להיווכח שגישה נאיבית לא תעבוד, בואו נחשוב מה יקרה אם נשאיר את x קבוע ושווה ל-1 ונגדיל את k כל הזמן. מכיוון ש-k יכול לקבל כל ערך טבעי, גדול ככל שיהיה, אף פעם לא "נגיע לסוף" הערכים ש-k יכול לקבל, ולכן אף פעם לא נעבור למקרה של x=2. לכן הדרך הזו נידונה לכישלון. דרך נכונה אפשרית אחת הראיתי בפוסט קודם, כאשר הראיתי שהרציונליים הם בני מניה: לעבור על הזוגות על פי סכומם. כלומר, להתחיל מהזוג (1,1) כי הוא היחיד שסכומו 2, לעבור לזוגות (1,2) ו-(2,1), כי הם היחידים שסכומם 3, וכן הלאה. בשיטה הזו מובטח שנעבור על כל הזוגות. הנה פסאודו קוד שעושה משהו שכזה:

• לכל i בתחום{1..} בצע:
  • לכל j בתחום {1...i-1} בצע:
    • עשה משהו על (j,i-j).

כאן i רץ על כל הסכומים האפשריים, ואילו j, לכל סכום, מאפשר לעבור באופן סדרתי על האיברים שנותנים סכום זה.

כמובן, אין צורך בגישה כל כך קפדנית ומדוייקת; לטעמי, די לומר "ידוע שאוסף כל הזוגות של הטבעיים הוא בן מניה ולכן ניתן לעבור עליו בצורה סדרתית" וזהו. אחת מהנקודות החשובות בפוסטים הקודמים שלי שדיברו על חישוביות היא שניתן לייצג כל קבוצה בת מניה באמצעות מספרים טבעיים - ולכן גם לעבור סדרתית על כל איבריה. זו נקודה חשובה ביותר, ואני מקווה שחידת הצפרדע מסייעת לראות זאת.

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