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

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

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

החידה הולכת ככה:

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

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

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

מהי הדרך היעילה לאיתור אותן אסטרטגיות? מהו ערך התוחלת המינימלי?
מצעדנו המרעים 161523
התחל בקומה ה50 והתקדם בשיטת אריה במדבר (בכל זריקה תצמצם את התחום הרלוונטי בחצי).
מספיק עם חידות של בדלנות מדעית 161524
מה זה כל החידות המתמטקאיות האלו? זה ממש לא פייר השאלות האלו שמענינות אולי רק כמה סטודנטים לפיזיקה מהטכניון
מצעדנו המרעים 161580
1. עם כדור בודד האסטרטגיה היחידה היא להתחיל מקומה 1 ולעלות בכל פעם קומה אחת.
2. עם 100 כדורים (או מספר לא מוגבל של כדורים) כבר הוצעה שיטת אריה במדבר - היא אכן היעילה ביותר.
3. עם שני כדורים, האסטרטגיה המיטבית היא להתחיל מקומה 14, אם נשבר לעבור לקומה 1 ולעלות קומה אחת בכל פעם, אם לא נשבר לעבור לקומה 27, אם נשבר לעבור לקומה 15 ולעלות קומה אחת בכל פעם, אם לא לעבור לקומה 39, וכך הלאה לקומות 50, 60, 69, 77, 84, 90, 95, 99, 100, כאשר אם בקומה מסוימת הכדור נשבר יורדים לקומה אחת מעל הקומה האחרונה בה הכדור לא נשבר וממשיכים משם בזהירות - קומה אחת בכל פעם.
במקרה הגרוע ביותר צריך 14 זריקות.
עבור בנין בן N קומות צריך להתחיל מהקומה ה
1/2(sqrt(1+8N)-1)
מעוגל כלפי מעלה וזה גם מספר ההטלות המקסימלי שידרש במקרה הגרוע ביותר.
הקשה חיפש את התוחלת המינימלית, לא חסם מינימלי על מספר הזריקות 161582
הקשה חיפש את התוחלת המינימלית, לא חסם מינימלי על מספר הזריקות 161586
לשם הפשטות, נניח שהבנין הוא בן 105 קומות וכן שההסתברות לקומה הקריטית להיות X היא אחידה. (1/105)
אין אף קומה קריטית שניתן לגלות בזריקה יחידה.
יש קומה קריטית אחת שניתן לגלות ב2 זריקות. (1)
יש שתי קומות קריטיות שניתן לגלות ב3 זריקות. (2 ו15)
יש שלוש קומות קריטיות שניתן לגלות ב4 זריקות. (3, 16 ו 28)
וכך הלאה כלומר התוחלת היא הסכום
1/105(1*2 + 2*3 + 3*4 + ... 15*14)=10.67
לא מדהים, בהשוואה ל7 זריקות בשיטת אריה במדבר, אבל נדמה לי שזאת התוחלת המינימלית עם 2 כדורים.
אני אשן על זה ואם אני אמצא הוכחה פשוטה או דרך יותר מוצלחת, אני מבטיח לשתף.
הקשה חיפש את התוחלת המינימלית, לא חסם מינימלי על מספר הזריקות 161613
יש לי טעות בחישוב התוחלת - האיבר האחרון בסכום הוא 14*14 שבא אחרי 13*14.
התוחלת היא קצת יותר מ 10.5.
הקשה חיפש את התוחלת המינימלית, לא חסם מינימלי על מספר הזריקות 161672
לצרכי המחשה, נסה להשוות זאת לתוחלת המתקבלת עבור האסטרטגיה בה שומטים את הכדור הראשון מהקומות 10, 20, 30, ...
כמובן שזו אינה יכולה להיות האסטרטגיה האופטימלית (מבחינת התוחלת) כי אם הכדור שרד את הנפילה מהקומה ה- 90, אין זה מעשה נבון להמשיך ישר לקומה ה- 100.
אתה צודק 161686
בשיטה הזאת יש קומה קריטית אחת שניתן למצוא בשתי זריקות, (1) שתי קומות קריטיות שניתן למצוא ב 3 זריקות, (2, 11) וכך הלאה עד 8 קומות קריטיות שניתן למצוא ב9 זריקות. (8, 17, 26 .. 71)
ב10 זריקות ניתן למצוא 11 קומות (9, 10, 18, 27 .. 81, 91)
ב11 זריקות ניתן למצוא 10 קומות (19, 20, 28 .. 82, 92)
ב12 זריקות ניתן למצוא 9 קומות (29, 30, 38, 47 .. 83, 93)
וכך הלאה עד שב18 זריקות מוצאים את הקומות 89, 90, ו99 וב19 זריקות את קומה 100.
התוחלת (בהנחה של התפלגות אחידה) היא טובה בהרבה - בערך 8.8.
אתה צודק 161728
אם הבנתי נכון, "ספירת המלאי" שרשמת מתיחסת לאסטרטגיה לפיה אחרי הקומה ה- 90 עוברים ל- 91 , 92, וכן הלאה. הלא כן?
התוחלת שיצאה לי עבור אסטרטגיה זו היא 10.81 . יתכן שטעיתי, אבל הפער בין התוצאות שלנו משמעותי (מבחינת השאלה שבדיון). בכל אופן, גם תוצאה זו כבר די קרובה לתוחלת של פתרון-החסם-המינימלי.

נניח שאני רוצה לכתוב תכנית מחשב שתמצא את האסטרטגיה האופטימלית. את מציאת המספר הכולל של אסטרטגיות אפשריות אני משאיר לחכמי הקומבינטוריקה והסיבוכיות (משהו יפה, עם נוסחת סטירלינג נניח, או פונקציות גמא, או סתם פונקציה היפרגאומטרית, יתקבל בברכה :) ). האם יש אפשרות ליעל את התהליך כך שלא יהיה צורך להתעסק עם אסטרטגיות שאינן "מבטיחות"?
אתה צודק 161865
אם אתה כבר יודע את התשובה לכל מספר קומות עד 99, אתה מוצא את האסטרטגיה האופטימלית ע"י חישוב פשוט שבודק רק את האפשרויות לזריקה הראשונה. בדרך זו אתה "ממשיך" את האסטרטגיה האופטימלית לבניין יותר נמוך (במקרה זה, עם 87 קומות) לאסטרטגיה אופטימלית ל-‏100 קומות. זה יעיל מאוד, ובוודאי לא מתעסק עם אסטרטגיות לא מבטיחות - זה בערך "חמדני".
מצעדנו המרעים 161640
ההנחה הסמויה בכל הפתרונות שהוצגו עד כה היא שהתפלגות התשובה הנכונה היא אחידה בין כל הקומות. אם נניח שמדובר בחידה פיזיקלית, הרי שמהירות הנפילה לא עולה לינארית עם מס' הקומה, ולכן הנחה זו שגויה.
מצעדנו המרעים 161641
נדמה לי שמספיק להניח שהמהירות לא יורדת כאשר עולים.
תלוי מה זורקים 167379
קראתי בזמנו מחקר על חתולים שנפלו מחלונות בניו יורק ונפלו על משטחים קשים. (בטון/אספלט) המחקר בדק את שעורי התמותה כפונקציה של הגובה. הגבהים נעו בין קומה 1 לקומה 30 ומשהו.
על מנת להגיע לתוצאות סבירות, לא הובאו בחשבון המקרים בהם החתול שרד את הנפילה אך נפצע ובעליו בקשו מהוטרינר להרדימו כדי לחסוך בהוצאות. (כאשר החתול נפגע באורח קשה והורדם מטעמים הומניטרים, הוא נחשב כאילו נהרג בנפילה)
התוצאות היו מוזרות, בלשון המעטה. הקומה הקטלנית ביותר היתה קומה 6. עקומת המות עלתה עד אליה וירדה אחריה ומעבר לקומה 12 (נדמה לי, אולי זה היה 1x אחר) התיצבה על פחות מ10 אחוז.
תלוי מה זורקים 167382
מדהים, גם אני ראיתי את המחקר הזה‏1. אכן היה PEAK בקומה 6, אבל היה גם חתול ששרד איזה 20 קומות רק עם שן סדוקה.
כשקראתי את המאמר ( איזה נייצר או סיינס עתיק אאלט) חשבתי שכנראה שהסטטיסטיקה מוטה על ידי זה שרק חתולים חיים מגיעים לבית החולים‏3.

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

1 אם יש לי פיצול אישיות, אני מאוד אשמח אם אתה האישיות האחרת שלי.‏2

2 זה אמור להיות מחמאה, אבל אולי זה לא ברור.

3 אם החתול שרד את הנפילה והחזיק מעמד עד שהגיע לבית החולים, כנראה הפגיעה לא קטלנית.
תלוי מה זורקים 167384
עד כמה שאני זוכר, החתול שנפל מהקומה הגבוהה ביותר (כאמור, 30 ומשהו) נשאר בחיים.
אין לי מושג איך אספו את הנתונים.
תלוי מה זורקים 167407
לא ידעתי שערכו מחקר כזה (זרקו חתולים מחלונות?!), אבל קראתי בספר אחד משהו שמסביר את התוצאה- מגובה מסויים ומעלה יש לחתול זמן להתארגן לנפילה. והיתה שם סדרת תצלומי סטילס שהראתה איך הוא מסתובב באוויר ממצב של גב-כלפי-מטה למצב של כפות-רגליים-כלפי-מטה, שומר על מצב זה, ועל רגליים כפופות בברכיים, ונוחת על כפותיו המרופדות.
תלוי מה זורקים 167408
אה-אה, הבנתי. לא זרקו אותם בכוונה... שיוו...
הנה זה 167450
כולל תמונה. מתברר שלא זכרתי נכון- הרגליים דווקא מתיישרות לקראת הנחיתה.
לא להאמין אבל יש פה חישובים מתימטיים של העניין. הייתי מניחה שזו בדיחה, אילולא היכרותי הוירטואלית עם מדעני האייל...
הנה זה 167505
ויש שם גם קישור למאמר על החתולים שנופלים מבנינים, והמחבר הוא לא אשר ממיודענו ג'ארד דיאמונד.
הנה זה 167754
אולי תכיר אותו גם לנו?
הנה זה 167771
את לועגת לי או שאת סנילית?
תגובה 121178
:)
הנה זה 167780
סנילית (וגם מתביישת, כי עוד לא פתחתי את הספר שלו).
הנה זה 167849
כדאי לך. למרות שאי אפשר לקרוא לו ''סוחף'' או ''עוצר נשימה'', זהו ספר מעניין וחכם מאוד.
מצעדנו המרעים 161859
הדרך היעילה לאיתור האסטרטגיות היא בדיוק כמו בחידת הקלפים - "תכנות דינמי" או פשוט פתרון באינדוקציה. גם כאן דומני שאין פתרון סגור לערך התוחלת המינימלי, ועבור 100 קומות ושני כדורים הוא יוצא 10.3 עם זריקה ראשונה מהקומה ה-‏13.

חולשה קטנה של השאלה הזו לעומת השאלה המקורית הוא שהיא תלויה בהנחה על ההתפלגות (ברור שהתשובה משתנה אם ההתפלגות איננה אחידה - למי ששאל, כדאי לחשוב על כדור אחד ושלוש קומות). דרך אגב, התשובה הנומרית לעיל מניחה שלכל קומה יש סיכוי של 1/100 להיות הקומה הקריטית, ובפרט הכדורים בטוח נשברים בזריקה מהקומה האחרונה.

אינני חושב שיש פתרון אלגנטי יותר עבור מספר כדורים כללי. עבור שני כדורים האסטרטגיה היא תמיד כמו לחידה המקורית, לדעתי: לרשום את מספר הקומות (פחות אחד, כי אין טעם לזרוק מהקומה האחרונה) כסכום 2+1+...+m ולזרוק מהקומה ה-m, אח"כ לעלות m-1 קומות, וכו' עם תיקונים קטנים כאשר המספר איננו משולשי. למשל

99=1+2+3+4+5+6+7+8+8+9+10+11+12+13

מתאר את האסטרטגיה ל-‏100 קומות. ערך התוחלת הוא (שוב!) בערך שורש n.
מצעדנו המרעים 161974
שוב אני צועד בעקבותיך. גם לי יצא 10.3 כתוחלת, אבל יש משהו מוזר (כנראה טעות שלי):
בהנתן שני כדורים, ככל שיש יותר קומות צריך להתחיל לזרוק מקומה גבוהה יותר. זה נראה הגיוני, אבל יש יוצא דופן: המקרה של 26 קומות. עבור 25 קומות, צריך לזרוק מקומה 6. גם עבור 27 קומות צריך להתחיל מ- 6. אבל כשיש 26 קומות, השיטה ממליצה לנסות קודם כל את קומה 7.

טעות?
מצעדנו המרעים 161993
לא נראה לי שיש לך טעות, רק משהו קצת מוזר במימוש: יש הרבה פעמים (תמיד?) ניוון באיזור הקומה האופטימלית, ואם אינני טועה ב-‏26 קומות אפשר להתחיל או ב-‏6 או ב-‏7 עם אותה תוחלת, 76/13.

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

חזרה לעמוד הראשי המאמר המלא

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