אם באיטרציה i נשבר הכדור צריך לבדוק x-i קומות וכבר בצענו i קפיצות אזי מספר הבדיקות המקס' הינו X-i+i = X X+(X-1)+(X-2)+... ~100 {מס' הגורמים הינו X } x^2-(x+1)*x/2 ~100 x^2-x-200 = 0 x1,2 = (1 +/- ~28)/2 ערך שלם תחתון (חיובי) = 14

תבנו פונקציה שמתארת את המתרחש(מספר הקומות). תגזרו אותה ותמצאו את המינימום וזהו. אני מאשש ש 2-19 זה האופטימלי.

2-19? 19 זה אומר לזרוק מקומה 100 עד 10 בקפיצות של 10 +9 עבור קפיצות של 1? יותר מידי... הבחור שאמר חיפוש בינארי צודק, קוראים לזה גם אריה במדבר, כאשר אם תחלק את טווח החיפוש שלך ב-2 כל הזמן אתה תקבל את התוצאה האופטימלית במינימום נסיונות מאחר ויש לך 100 קומות מספר הניסיונות שווה כאמור ללוגריתם טבעי של 2 של מספר הקומות ובעיגול מעלה זה 7.

לא הבנת את השאלה, תקרא אותה שוב..

בשלב הזה אנחנו כבר יודעים שהצעדים צריכים להיות סדרה חשבונית יורדת עם צעד בגודל 1 כדי שבכל מקרה מספר הצעדים יהיה קבוע. נניח שהמספר הזה הוא x. אז ברור שמתחילים מקומה x, אם לא נשבר עוברים לקומה 2x-1 וכו'. אנחנו יודעים שסכום הצעדים צריך להסתכם ב-100 (כיוון שמדובר בשלמים המינימלי שגדול מ-100). נניח שיש לנו n איברים בסדרה הזו אבל נקבל סכום סדרה חשבונית - nx-n(n+1)/2=100 אבל מה זה ה-n הזה? כדי לקבל את ה-x המינ-מקס נרצה שה-n הזה יהיה שווה ל-x (ככה הסדרה תגמר בצעד של 1 והגענו ל-x המינימלי שיכול ל"פרוס" את הבניין). ועכשיו מדובר בפתרון משוואה ריבועית ועיגול כלפי מעלה.

תודה רבה על השקעה אך לצערי הרב לא חידשתי לי כלום השאלה הגדולה למה דווקא 14 ?!