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

לפי כללי המשחק אסור לזרוק גזר פעמיים ברציפות לכיוון אותו סלע.

והשאלה:

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

 שבוע טוב,

סקובידו

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

24 תגובות

  • Chaim

    פתרון

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

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

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

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

  • מומחה מצוות מכון דוידסוןפזיה

    מצוין! וחידה נוספת

    ועכשיו אותה חידה רק עם 2 שינוים:
    1. אינך רואה את הארנבת ואת כיוון קפיצתה.
    2. הארנבת קופצת אחרי שהירייה פוגעת במטרתה.
    מה יהיה האלגוריתם לפגיעה בטוחה?

  • רמי

    פתרון לחידה הנוספת

    נסמן את הסלעים מימין לשמאל במספרים 1 עד 6.
    בכל שלב נזרוק גזר לסלע שמספרו מופיע בשורת המספרים הבאה : 3-> 2-> 4-> 5-> 4-> 3-> 2-> 6 ->5 ->4-> 3 -> 2

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

  • Chaim

    המוטיבציה מאחורי הפתרון

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

    אהבתי מאוד את הדיון אשמח להמשיך אתכם לחידות הבאות

  • רמי

    הסבר

    יש שני שלבים בפתרון :
    בשלב א' (1->5->4->3->2) התייחסות לארנבת שמיקומה היה בתחילת התהליך על סלע זוגי (למעט סלע 1). הארנבת לא תוכל להימלט ותפגע גם אם תבחר במסלול הטוב ביותר/הארוך ביותר.
    בשלב ב' (6->5->4->3->2) התייחסות לארנבת שמיקומה היה בתחילת התהליך על סלע אי זוגי . וסיכוייה לא להפגע אפסיים גם כאן.

    הארנבת משנה כל שלב את זוגיות מיקומה.
    למשל לאחר מהלך ראשון, אם הארנבת היתה על סלע זוגי, היא תעבור לסלע אי זוגי.
    הסלע האי-זוגי הגדול ביותר הוא 5. אם נזרוק גזר ל 5 , והארנבת היתה שם, היא תפגע. אם היתה ב 3 אזי תעבור ל 4 או ל 2. זריקה ל 4 תפגע בה, אחרת היא תעבור ל 3 או 1, וכך הלאה ...

  • רמי

    פתרון קצר יותר לחידה הנוספת

    פתרון באורך 10 :
    1->5->4->3->2->6->5->4->3->2

  • רמי

    פתרון החידה הנוספת המוכללת

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

    פתרון החידה הנוספת המוכללת:
    נסמן את הסלעים המסודרים בשורה מימין לשמאל במספרים מ 1 ועד R.
    נזרוק גזרים בכל שלב אל הסלע הממוספר על פי הסדר הבא :
    גזר ראשון לסלע 1
    גזר שני לסלע 1-R
    גזר 3 לסלע 2-R
    :
    גזר 1-R לסלע 2
    גזר R לסלע R
    גזר 1+R לסלע 1-R
    גזר 2+R לסלע 2-R
    :
    גזר 2R-2 לסלע 2

    כלומר זרקנו 2*(R-1) גזרים לפגיעה בטוחה בארנבת.

  • רמי

    פתרון קצר יותר לחידה הנוספת המוכללת

    סיבוב ראשון:
    גזר ראשון לסלע 1-R
    גזר 2 לסלע 2-R
    :
    גזר 2-R לסלע 2
    וסיבוב שני:
    גזר R-1 לסלע R-1
    גזר R לסלע 2-R
    גזר 1+R לסלע 3-R
    :
    גזר 2R-4 לסלע 2

    כלומר זרקנו 2*(R-2) גזרים לפגיעה בטוחה בארנבת.

  • עטרה

    לא עובד

    נראה לי שהאלגוריתם נכשל, כאשר R זוגי, והמסלול של הארנבת הוא
    2-1-2-1-2-1-2-1-...

  • רמי

    נכון. יש הבדל בין R זוגי ל R אי זוגי.

    עבור R זוגי:
    בשלב א', נזרוק גזרים מסלע R-1 ועד 2
    בשלב ב', נזרוק גזרים מסלע R ועד 2

    עבור R אי זוגי:
    בשלב א', נזרוק גזרים מסלע R-1 ועד 2
    בשלב ב', נזרוק גזרים מסלע R-1 ועד 2

    תודה על הבדיקה לעומק!!

  • Chaim

    אוכיח שאין לזה פתרון

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

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

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

  • מומחה מצוות מכון דוידסוןפזיה

    דווקא יש אסטרטגיה מנצחת

    נסה לחשוב שוב

  • Chaim

    חסר פרט מאוד חשוב בחידה

    חסר נתון:
    היכן עומדת האנבת בתחילת המשחק

  • Chaim

    אופס

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

  • עטרה

    חידת המשך 2

    נניח שגם יונתן וגם הארנבת פועלים באופן אקראי.

    א. מהם המסלולים עבור הארנבת, שבהם הסיכוי שתיפגע הוא הכי נמוך?
    ב. מהם המסלולים עבור יונתן, שבהם הסיכוי שיפגע בארנבת הוא הכי נמוך?
    ג. מהם המסלולים עבור יונתן, שבהם הסיכוי שיפגע בארנבת הוא בדיוק 0.5?
    ד. מה משותף לכל המסלולים הנ"ל?
    ה. מהם המסלולים עבור יונתן, שבהם הסיכוי שיפגע בארנבת הוא הכי גבוה?

  • רמי

    תשובות לחידת המשך 2

    א. המסלולים הכוללים סלעים 1 ו2 בלבד או 5 ו-6 בלבד. כלומר אם הארנבת תדלג בין 1 ל 2, או בין 5 ל 6, הסיכוי האקראי לפגוע בה הכי נמוך.
    ב. כנ"ל. המסלולים הצדדיים שכוללים סלעים 1 ו-2 בלבד או 5 ו-6 בלבד.
    ד. לא מצאתי מסלול של הארנבת שהסיכוי שיונתן יפגע בה הוא 0.5 !
    ה. המסלולים הפנימיים בהם הארנבת מקפצת על הסלעים 2,3,4 ו-5 בלבד.

  • עטרה

    טעות שלי

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

  • רמי

    השאלה לתשובה

    תהא Qm ההסתברות הממוצעת לסלע m שארנבת המדלגת בין הסלעים בצורה אקראית תקפוץ אליו.
    יהא Pn ההסתברות הממוצעת שלסלע n יזרק גזר, כשזריקת הגזרים היא בצורה אקראית אך לא לסלע שזה עתה ספג גזר.
    באילו קבוצות סלעים סמוכים ההסתברות למפגש ארנבת וגזר נמוכה?
    באילו קבוצות סלעים סמוכים ההסתברות למפגש ארנבת וגזר גבוהה?
    אילו מסלולים מתאימים לקבוצות הסלעים הנ"ל?
    מה ההסתברות לפגיעה אקראית בארנבת עם הגזר?

  • עטרה

    חידת המשך 1

    כמה מסלולים אפשריים יש עבור הארנבת, בלי קשר ליונתן?

  • רמי

    איך את מגדירה מסלול?

    - האם מעבר מצד לצד? [מתחילה מהסלע הימני ביותר עד הגיעה לשמאלי ביותר]
    - האם קפיצה על כל הסלעים? [סיום מסלול לאחר שהארנבת קיפצה מעל כל אחד מהסלעים לפחות פעם אחת]
    - האם עד חזרה לנקודת המוצא? [אם מתחילה מסלע N , ברגע שתקפוץ אליו שוב המסלול מסתיים]
    - האם מוגדר כהלכה? [אם קיים אלגוריתם המגדיר את המסלול. למשל "קפיצות רק שמאלה". מסיימת המסלול בהגיעה לסלע השמאלי ביותר.]
    :
    :
    - או משהו אחר.

  • עטרה

    הגדרת מסלול

    מסלול באורך N עבור הארנבת, הוא סדרה של N מהלכים, כך שכל מהלך הוא בין סלעים סמוכים.
    התכוונתי לשאול, כמה מסלולים באורך 6 יש עבור הארנבת?

  • רמי

    מספר מסלולים

    נסמן את R הסלעים ממספר 1 ועד R .
    נגדיר פונקציה (Paths(R,L של מספר המסלולים השונים עבור R סלעים ו L מהלכים.
    נגדיר פונקציה שניה (RocksP(R,L,N שתתן את מספר המסלולים מסלע N .
    הניסוח הרקורסיבי של מספר המסלולים הכולל Paths:
    Paths(R,0)=R
    (Paths(R,1)=2*(R-1
    (( Paths(R,L)=2*(Paths(R,L-1)-RocksP(R,L-1,1

    הניסוח הרקורסיבי של RocksP :
    RocksP(R,1,1)=RocksP(R,1,R)=1
    RocksP(R,1,t)=RocksP(R,1,t)=2
    (RocksP(R,l,1)=RocksP(R,l,R)=RocksP(R,l-1,2
    RocksP(R,L,N)=RocksP(R,L-1,N-1)+RocksP(R,L-1,N+1)

    לכן בפרט : Paths(6,6)=188

  • עטרה

    תשובה יפה מאוד

    הערה קטנה: יש להוסיף תנאי עצירה עבור R=1.

  • רמי

    תודה

    אכן יש תנאי עצירה שלא פרטתי אותם קודם:
    Paths(0,k)=0 לכל k>=0
    Paths(1,k)=0 k>0
    RocksP(K,0,n)=1 לכל K >=n>0