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

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

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

זהו למעשה מקרה פרטי של מושג כללי יותר מקינמטיקה בסיסית – תנועה במהירות קבועה. גם תנועה במהירות קבועה מאופיינת על ידי שני פרמטרים: המיקום בעת תחילת התנועה, ומהירות התנועה. כאן x הוא המיקום ו-k הוא המהירות. משוואת התנועה במקרה זה היא $latex 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, לכל סכום, מאפשר לעבור באופן סדרתי על האיברים שנותנים סכום זה.

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

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

9 תגובות על הפוסט “חידת צפרדע – הפתרון

  1. ובכן, בהנחה ב-t מציין את מספר הבדיקה, צריך לבדוק את x+60kt
    באופן כללי, תמיד צריך לבדוק את "המקום שבו הצפרדע נמצאת עכשיו בהנחה שאנחנו בודקים כרגע את האפשרות הנכונה"

  2. קיימת גם דרך לפתור את החידה בעזרת התאמה כאשר אתה מפריד את הבדיקה לפי מקום התחלתי ועבור כל אפשרות רץ על כל אפשרות של גודל הקפיצה של הצפרדע (הדרך שאתה פסלת).
    ראשית נארגן לנו את התורים באופן הבא:
    ניקח את התור הראשון (t=0), אחריו ניקח דילוג אחד ונעבור לרגע t=2. כעת ניקח שני דילוגים לתור t=5, שלושה דילוגים לתור t=9 וכן הלאה…
    נשתמש בתורים אלו על מנת לבדוק את כל אין סוף האפשרויות הקיימות אם הצפרדע התחילה בנקודה 0.
    התורים שנשארו לנו מסודרים בטור חשבוני עולה. מכל קבוצה ניקח את התור הראשון על מנת לבדוק את כל אין סוף האפשרויות עבור אם הצפרדע התחילה בנקודה 1.
    עדיין נשארו לנו אין סוף תורים בצד המאורגנים בטור חשבוני עולה הזהה למצב הקודם וככה נמשיך ונבדוק טורים עד שנגיע לצפרדע.

    זה הפיתרון שאני מצאתי לחידה. קצת יותר מסובך מהפיתרון שניתן אך מספק בהחלט 😉

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

  4. אני לא מבין איך זה יכול להיות פתרון בכלל ?
    דבר ראשון אם הצפרדע הולכת בכיוון שאתה לא בודק אתה בחיים לא תמצא אותה.
    הקצב בדיקה בטח שכן משנה, אם היא עושה 100 קפיצות בדקה ואתה עושה בדיקה אחת בשעה, הסיכוי שתמצא אותה הוא אפס.

    הדרך היחידה הריאליסטית למצוא אותה הוא רק אם אתה דוגם ממש יותר מהר מהקפיצות שלה.

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

    הטענה שלך על קצב הבדיקה היא כמובן שגויה. אני מקבל את הרושם שלא באמת ניסית להבין למה הפתרון עובד.

  6. שאלו אותי את אותה השאלה וממש התרשמתי מהפתרון – הפעם כשהצפרדע מתחילה במיקום כלשהו על ציר הממשיים, המהירות שלה ממשית, ויש לה עובי ממשי כלשהו – האם אפשר לתפוס אותה?

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

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

כתיבת תגובה

האימייל לא יוצג באתר.