 |
|
 |
||
|
||||
 |
כעת, כשכל החידות הממלכתיות נפתרו, הגיעה שעתם של אוכלי הנבלות... השאלה שלי דומה ברוחה לחידת הקלפים של גלעד ברזילי. גילוי נאות: איני מכיר פתרון המניח את הדעת. מדובר בחידה ידועה מאד שמן הסתם רובכם נתקלתם בה. גם הפתרונות מוכרים וידועים, לכאורה. מדוע לכאורה? אה, על זה בדיוק רציתי לדבר אתכם. החידה הולכת ככה: נתונים כדורים העשויים מאיזשהו חומר, הנשברים אם שומטים אותם מגובה מסוים (או יותר). רוצים לברר מהי הקומה הנמוכה ביותר, בבניין בן מאה קומות, שאם שומטים ממרפסתה כדור כנ"ל, הוא נשבר. הפתרון המבוקש הוא האסטרטגיה האופטימלית לשמיטת כדורים מהמרפסות השונות, כך שנגלה מהי אותה קומה במספר מינימלי של "הפלות", אם יש לנו: א. כדור אחד. ב. מאה כדורים. ג. שני כדורים. למי שטרם נתקל בחידה זו (וגם למי שנתקל-אבל-שכח), מומלץ לעצור לרגע את הקריאה ולהרהר בענין. לגבי האחרים, כאן העסק רק מתחיל. "פתרון בית הספר" של סעיף ג', הוא זה המבטיח חסם מינימלי על מספר הזריקות הכולל. בהרהור נוסף, נראה שיש להעדיף את האסטרטגיה (או האסטרטגיות) שערך התוחלת שלהן מינימלי. מהי הדרך היעילה לאיתור אותן אסטרטגיות? מהו ערך התוחלת המינימלי? |
 |
 |
 |
|
|
|
||
|
||||
|
התחל בקומה ה50 והתקדם בשיטת אריה במדבר (בכל זריקה תצמצם את התחום הרלוונטי בחצי). | |
|
|
|
|
|
||
|
||||
|
מה זה כל החידות המתמטקאיות האלו? זה ממש לא פייר השאלות האלו שמענינות אולי רק כמה סטודנטים לפיזיקה מהטכניון | |
|
|
|
|
|
||
|
||||
|
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) מעוגל כלפי מעלה וזה גם מספר ההטלות המקסימלי שידרש במקרה הגרוע ביותר.
|
|
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
לשם הפשטות, נניח שהבנין הוא בן 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 כדורים. אני אשן על זה ואם אני אמצא הוכחה פשוטה או דרך יותר מוצלחת, אני מבטיח לשתף. |
|
|
|
|
|
|
||
|
||||
|
יש לי טעות בחישוב התוחלת - האיבר האחרון בסכום הוא 14*14 שבא אחרי 13*14. התוחלת היא קצת יותר מ 10.5. |
|
|
|
|
|
|
||
|
||||
|
לצרכי המחשה, נסה להשוות זאת לתוחלת המתקבלת עבור האסטרטגיה בה שומטים את הכדור הראשון מהקומות 10, 20, 30, ... כמובן שזו אינה יכולה להיות האסטרטגיה האופטימלית (מבחינת התוחלת) כי אם הכדור שרד את הנפילה מהקומה ה- 90, אין זה מעשה נבון להמשיך ישר לקומה ה- 100. |
|
|
|
|
|
|
||
|
||||
|
בשיטה הזאת יש קומה קריטית אחת שניתן למצוא בשתי זריקות, (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. |
|
|
|
|
|
|
||
|
||||
|
אם הבנתי נכון, "ספירת המלאי" שרשמת מתיחסת לאסטרטגיה לפיה אחרי הקומה ה- 90 עוברים ל- 91 , 92, וכן הלאה. הלא כן? התוחלת שיצאה לי עבור אסטרטגיה זו היא 10.81 . יתכן שטעיתי, אבל הפער בין התוצאות שלנו משמעותי (מבחינת השאלה שבדיון). בכל אופן, גם תוצאה זו כבר די קרובה לתוחלת של פתרון-החסם-המינימלי. נניח שאני רוצה לכתוב תכנית מחשב שתמצא את האסטרטגיה האופטימלית. את מציאת המספר הכולל של אסטרטגיות אפשריות אני משאיר לחכמי הקומבינטוריקה והסיבוכיות (משהו יפה, עם נוסחת סטירלינג נניח, או פונקציות גמא, או סתם פונקציה היפרגאומטרית, יתקבל בברכה :) ). האם יש אפשרות ליעל את התהליך כך שלא יהיה צורך להתעסק עם אסטרטגיות שאינן "מבטיחות"? |
|
|
|
|
|
|
||
|
||||
|
אם אתה כבר יודע את התשובה לכל מספר קומות עד 99, אתה מוצא את האסטרטגיה האופטימלית ע"י חישוב פשוט שבודק רק את האפשרויות לזריקה הראשונה. בדרך זו אתה "ממשיך" את האסטרטגיה האופטימלית לבניין יותר נמוך (במקרה זה, עם 87 קומות) לאסטרטגיה אופטימלית ל-100 קומות. זה יעיל מאוד, ובוודאי לא מתעסק עם אסטרטגיות לא מבטיחות - זה בערך "חמדני". | |
|
|
|
|
|
||
|
||||
|
ההנחה הסמויה בכל הפתרונות שהוצגו עד כה היא שהתפלגות התשובה הנכונה היא אחידה בין כל הקומות. אם נניח שמדובר בחידה פיזיקלית, הרי שמהירות הנפילה לא עולה לינארית עם מס' הקומה, ולכן הנחה זו שגויה. | |
|
|
|
|
|
||
|
||||
|
נדמה לי שמספיק להניח שהמהירות לא יורדת כאשר עולים. | |
|
|
|
|
|
||
|
||||
|
קראתי בזמנו מחקר על חתולים שנפלו מחלונות בניו יורק ונפלו על משטחים קשים. (בטון/אספלט) המחקר בדק את שעורי התמותה כפונקציה של הגובה. הגבהים נעו בין קומה 1 לקומה 30 ומשהו. על מנת להגיע לתוצאות סבירות, לא הובאו בחשבון המקרים בהם החתול שרד את הנפילה אך נפצע ובעליו בקשו מהוטרינר להרדימו כדי לחסוך בהוצאות. (כאשר החתול נפגע באורח קשה והורדם מטעמים הומניטרים, הוא נחשב כאילו נהרג בנפילה) התוצאות היו מוזרות, בלשון המעטה. הקומה הקטלנית ביותר היתה קומה 6. עקומת המות עלתה עד אליה וירדה אחריה ומעבר לקומה 12 (נדמה לי, אולי זה היה 1x אחר) התיצבה על פחות מ10 אחוז. |
|
|
|
|
|
|
||
|
||||
|
מדהים, גם אני ראיתי את המחקר הזה1. אכן היה PEAK בקומה 6, אבל היה גם חתול ששרד איזה 20 קומות רק עם שן סדוקה. כשקראתי את המאמר ( איזה נייצר או סיינס עתיק אאלט) חשבתי שכנראה שהסטטיסטיקה מוטה על ידי זה שרק חתולים חיים מגיעים לבית החולים3. ובאסוציאציה פרועה- ראיתי גם מחקר שגילה שמספר החסידות שניצפו בגרמניה מאז שנות החמישים יורד במתאם חזק לירידת הילודה שם. 1 אם יש לי פיצול אישיות, אני מאוד אשמח אם אתה האישיות האחרת שלי.2 2 זה אמור להיות מחמאה, אבל אולי זה לא ברור. 3 אם החתול שרד את הנפילה והחזיק מעמד עד שהגיע לבית החולים, כנראה הפגיעה לא קטלנית. |
|
|
|
|
|
|
||
|
||||
|
עד כמה שאני זוכר, החתול שנפל מהקומה הגבוהה ביותר (כאמור, 30 ומשהו) נשאר בחיים. אין לי מושג איך אספו את הנתונים. |
|
|
|
|
|
|
||
|
||||
|
לא ידעתי שערכו מחקר כזה (זרקו חתולים מחלונות?!), אבל קראתי בספר אחד משהו שמסביר את התוצאה- מגובה מסויים ומעלה יש לחתול זמן להתארגן לנפילה. והיתה שם סדרת תצלומי סטילס שהראתה איך הוא מסתובב באוויר ממצב של גב-כלפי-מטה למצב של כפות-רגליים-כלפי-מטה, שומר על מצב זה, ועל רגליים כפופות בברכיים, ונוחת על כפותיו המרופדות. | |
|
|
|
|
|
||
|
||||
|
אה-אה, הבנתי. לא זרקו אותם בכוונה... שיוו... | |
|
|
|
|
|
||
|
||||
|
כולל תמונה. מתברר שלא זכרתי נכון- הרגליים דווקא מתיישרות לקראת הנחיתה. לא להאמין אבל יש פה חישובים מתימטיים של העניין. הייתי מניחה שזו בדיחה, אילולא היכרותי הוירטואלית עם מדעני האייל... |
|
|
|
|
|
|
||
|
||||
|
ויש שם גם קישור למאמר על החתולים שנופלים מבנינים, והמחבר הוא לא אשר ממיודענו ג'ארד דיאמונד. | |
|
|
|
|
|
||
|
||||
|
את לועגת לי או שאת סנילית? תגובה 121178 :) |
|
|
|
|
|
|
||
|
||||
|
סנילית (וגם מתביישת, כי עוד לא פתחתי את הספר שלו). | |
|
|
|
|
|
||
|
||||
|
כדאי לך. למרות שאי אפשר לקרוא לו ''סוחף'' או ''עוצר נשימה'', זהו ספר מעניין וחכם מאוד. | |
|
|
|
|
|
||
|
||||
|
הדרך היעילה לאיתור האסטרטגיות היא בדיוק כמו בחידת הקלפים - "תכנות דינמי" או פשוט פתרון באינדוקציה. גם כאן דומני שאין פתרון סגור לערך התוחלת המינימלי, ועבור 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. |
|
|
|
|
|
|
||
|
||||
|
שוב אני צועד בעקבותיך. גם לי יצא 10.3 כתוחלת, אבל יש משהו מוזר (כנראה טעות שלי): בהנתן שני כדורים, ככל שיש יותר קומות צריך להתחיל לזרוק מקומה גבוהה יותר. זה נראה הגיוני, אבל יש יוצא דופן: המקרה של 26 קומות. עבור 25 קומות, צריך לזרוק מקומה 6. גם עבור 27 קומות צריך להתחיל מ- 6. אבל כשיש 26 קומות, השיטה ממליצה לנסות קודם כל את קומה 7. טעות? |
|
|
|
|
|
|
||
|
||||
|
לא נראה לי שיש לך טעות, רק משהו קצת מוזר במימוש: יש הרבה פעמים (תמיד?) ניוון באיזור הקומה האופטימלית, ואם אינני טועה ב-26 קומות אפשר להתחיל או ב-6 או ב-7 עם אותה תוחלת, 76/13. האם מימשת בסביבה חישובית עם נקודה צפה...? |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |