סדרת המסעדן העצלן

פנקייק חתוך לשבע חתיכות בשלושה חיתוכים ישרים

סדרת המסעדן העצלן (באנגלית: Lazy caterer's sequence) או המספרים המצולעיים המרכזיים (באנגלית: Central polygonal numbers) מתארים את המספר המרבי של חתיכות של מעגל שניתן ליצור עם מספר נתון של חיתוכים ישרים. לדוגמה, שלושה חיתוכים של מעגל ייצרו שש חתיכות עם כולם נפגשים בנקודה מסוימת בתוכו, אך שבע אם לא.

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

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

הסדרה ונוסחה

מספר החתיכות המקסימלי (p) שניתן לקבל מ-n חיתוכים ישרים (כאשר $n \geq 0$ ) נתון על ידי הנוסחה $p = \frac{n^{2} + n + 2}{2}$ , אותה ניתן לבטא באמצעות מקדמים בינומיים בצורה $p = 1 + (\binom{n + 1}{2}) = (\binom{n}{0}) + (\binom{n}{1}) + (\binom{n}{2})$ .

האיבר ה-n-י בסדרת המסעדן העצל הוא אחד ועוד המספר המשולשי ה-n-י, ולכן העמודה השלישית במשולש ברנוליתבנית:ביאור ( $k = 2$ ) מייצגת סדרה זו עבור $n \geq 2$ .

בנוסף ניתן לקבל את הסדרה מסכום שלושת האיברים הראשונים בכל שורה במשולש פסקל, או האיבר הראשון בכל שורה במשולש פלויד תבנית:אנ.תבנית:ביאור ההפרש בין האיבר ה-n-י בסדרה לבין האיבר שלפניו הוא n.

לפיכך, סדרה זו (תבנית:OEIS), המתחילה ב- $n = 0$ , היא:

1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211...

המקבילה התלת־ממדית של בעיית המסעדן העצלן היא מספרי העוגה תבנית:אנ, בה ההפרש בין האיבר ה-n-י לבין האיבר שלפניו הוא המספר ה-n בסדרת המסעדן העצלן.

הוכחה

נסמן ב- $p = f (n)$ את מספר הפרוסות המרבי שנוצר מ- $n$ חיתוכים ישרים.

כדי להשיג את המספר המרבי של פרוסות, החיתוך ה-n-י צריך לחצות את כל שאר החיתוכים הקודמים בתוך המעגל מבלי לחצות שום מפגש בין שניים כאלו. לפיכך, הקו ה-n-י עצמו נחתך ב- $n - 1$ מקומות, ויוצר n חתיכות נוספות. לפיכך, המספר הכולל של הפרוסות לאחר $n$ חיתוכים הוא $f (n) = n + f (n - 1)$ .

נוסחת נסיגה זו ניתנת לפתירה. אם נרחיב את $f (n - 1)$ לפי נוסחה זו נקבל $f (n) = n + (n - 1) + f (n - 2)$

וברקורסיה נרחיב את הביטויים עד שהביטוי האחרון יצטמצם ל- $f (0)$ , כלומר $f (n) = n + (n - 1) + (n - 2) + \dots + 1 + f (0)$ .

מכיוון ש- $f (0) = 1$ (לפני כל החיתוכים קיימת פרוסה יחידה, המעגל השלם), ניתן לכתוב את המשוואה בצורה $f (n) = 1 + (1 + 2 + 3 + \dots + n)$ , וביטוי זה ניתן לפישוט באמצעות הנוסחה לסכום סדרה חשבונית:

f (n) = 1 + \frac{n (n + 1)}{2} = \frac{n^{2} + n + 2}{2}

.

קישורים חיצוניים

ביאורים

תבנית:ביאורים

סדרת המסעדן העצלן

תוכן עניינים

הסדרה ונוסחה

הוכחה

קישורים חיצוניים

ביאורים

תפריט ניווט

סדרת המסעדן העצלן

הסדרה ונוסחה

הוכחה

קישורים חיצוניים

ביאורים

תפריט ניווט

חיפוש