אדם נכנס לבניין שבו 15 קומות וברשותו 2 כדורי בדולח. ידוע לו שהכדורים מתנפצים כשזורקים אותם אל הקרקע החל מקומה מסוימת ומעלה, אך קומה זו לא ידועה לו.
האם תוכלו לעזור לו במציאת הקומה הזו תוך 5 זריקות לכל היותר?
הערות: 1. ייתכן שהכדורים יתנפצו כבר בזריקה מהקומה הראשונה וייתכן שלא יתנפצו אפילו בזריקה מהקומה העליונה; 2. כדור שנזרק ולא התנפץ ניתן לשימוש חוזר.
רמז (אם אתם זקוקים לו):
אם מאפשרים 5 זריקות אזי הזריקה הראשונה יכולה להיות מקומה 5 לכל היותר.
פתרון:
נסמן את 2 הכדורים ב-א' ו-ב'. נכנה בשם "קומת ההתנפצות" את הקומה שהחל ממנה ומעלה הכדורים מתנפצים. מובן שכדי לא "לבזבז" זריקות, נשאף לזרוק את הכדורים מהקומות הגבוהות ביותר שתהיינה אפשריות בכל שלב.
אם מאפשרים 5 זריקות אזי הזריקה הראשונה יכולה להיות מקומה 5 לכל היותר. זאת משום שאם נזרוק את א' מקומה 6 והוא יתנפץ, לא נוכל להבטיח עמידה במשימה, כי ייתכן שנזדקק ל-5 זריקות של ב' (מקומה 1 עד קומה 5) כאשר לרשותנו יעמדו רק 4 זריקות.
שיקול דומה ידריך אותנו אם א' לא יתנפץ בזריקה הראשונה מקומה 5. במקרה זה יישארו לנו 2 הכדורים ו-4 זריקות ונוכל לבצע את הזריקה השנייה של א' מקומה 9 לכל היותר. זאת משום שאם נזרוק את א' מקומה 10 והוא יתנפץ, לא נוכל להבטיח עמידה במשימה, כי ייתכן שנזדקק ל-4 זריקות של ב' (מקומה 6 עד קומה 9) כאשר לרשותנו יעמדו רק 3 זריקות.
באופן דומה ניתן להסיק שאם א' לא יתנפץ גם בזריקה השנייה מקומה 9, אזי נבצע את הזריקה השלישית של א' מקומה 12 וכך נמשיך הלאה באופן הבא: מספר הקומות שנעלה בכל זריקה יהיה שווה למספר הזריקות שיישארו לנו באותו שלב. כלומר, אם מאפשרים 5 זריקות אזי מספרי הקומות שמהם נזרוק את הכדורים יהיו 5, 9, 12, 14, 15. ככל שעולים בקומת הזריקה ואין התנפצות, ההפרשים בין הקומות הולכים וקטנים: בהתחלה 5, אחר כך 4, אחר כך 3, אחר כך 2 ולבסוף 1.
כללי הזריקות הם, אפוא, (א) הזריקה הראשונה של א' היא מקומה 5; (ב) כל עוד א' לא מתנפץ, ממשיכים לזרוק אותו מקומות 9, 12, 14 וכו'; (ג) אם א' מתנפץ באיזשהו שלב, אזי זורקים את ב' מכל הקומות, החל מקומה אחת מעל הזריקה הקודמת של א' (שלא התנפצה) ועד לקומה אחת מתחת לקומה שבה א' התנפץ.
הטבלה הבאה מראה כיצד תתבצענה הזריקות. ניתן לראות שבכל המקרים מספר הזריקות של א' ושל ב' ביחד אינו עולה על 5.
טבלה: הסימון "קה" פירושו קומת ההתנפצות. הסימון "א5 כן" פירושו שכדור א' נזרק מקומה 5 והתנפץ, והסימון "ב1 לא" פירושו שכדור ב' נזרק מקומה 1 ולא התנפץ.
| זריקה 1 | זריקה 2 | זריקה 3 | זריקה 4 | זריקה 5 | קה | מס' הזריקות |
| א' | מתנפץ | בזריקה | הראשונה | |||
| א5 כן | ב1 כן | 1 | 2 | |||
| א5 כן | ב1 לא | ב2 כן | 2 | 3 | ||
| א5 כן | ב1 לא | ב2 לא | ב3 כן | 3 | 4 | |
| א5 כן | ב1 לא | ב2 לא | ב3 לא | ב4 כן | 4 | 5 |
| א5 כן | ב1 לא | ב2 לא | ב3 לא | ב4 לא | 5 | 5 |
| א' | מתנפץ | בזריקה | השנייה | |||
| א5 לא | א9 כן | ב6 כן | 6 | 3 | ||
| א5 לא | א9 כן | ב6 לא | ב7 כן | 7 | 4 | |
| א5 לא | א9 כן | ב6 לא | ב7 לא | ב8 כן | 8 | 5 |
| א5 לא | א9 כן | ב6 לא | ב7 לא | ב8 לא | 9 | 5 |
| א' | מתנפץ | בזריקה | השלישית | |||
| א5 לא | א9 לא | א12 כן | ב10 כן | 10 | 4 | |
| א5 לא | א9 לא | א12 כן | ב10 לא | ב11 כן | 11 | 5 |
| א5 לא | א9 לא | א12 כן | ב10 לא | ב11 לא | 12 | 5 |
| א' | מתנפץ | בזריקה | הרביעית | |||
| א5 לא | א9 לא | א12 לא | א14 כן | ב13 כן | 13 | 5 |
| א5 לא | א9 לא | א12 לא | א14 כן | ב13 לא | 14 | 5 |
| א' | מתנפץ | בזריקה | החמישית | |||
| א5 לא | א9 לא | א12 לא | א14 לא | א15 כן | 15 | 5 |
| א' | לא | מתנפץ | כלל | |||
| א5 לא | א9 לא | א12 לא | א14 לא | א15 לא | אין קה | 5 |
למעוניינים בהרחבה
אפשר להכליל את הפתרון למספר כלשהו של קומות. ראינו שאם מאפשרים X זריקות, אזי הזריקה הראשונה יכולה להיות מקומה X לכל היותר. כמו כן ראינו שככל שעולים בקומת הזריקה ואין התנפצות, ההפרשים בין הקומות שמהן זורקים הולכים וקטנים ב-1, כלומר ההפרשים מהווים סדרה חשבונית שאיבריה הולכים וקטנים ב-1. לפי נוסחת הסכום של סדרה חשבונית הסכום שלה הוא ½ כפול X כפול (1+X). החידה הופכת לשאלה עבור איזה X סכום זה הוא גדול או שווה למספר הקומות. כך מקבלים שאם יש קומה אחת, מספיקה זריקה אחת (טריוויאלי), אם יש 10 קומות מספיקות 4 זריקות, אם יש 15 קומות מספיקות 5 זריקות (זהו המקרה בחידה הנוכחית), אם יש 50 קומות מספיקות 10 זריקות ואם יש 100 קומות מספיקות 14 זריקות.
3 תגובות
וואוו
3 פעמים קראתי עד שהבנתי
אתגר אינטלקטואלי
מעניין
אכן אתגר. רק מהטבלה אפשר לקבל סחרחורת.
קצת כבד