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

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

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

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

זוהי בעיה הקשורה בסידור ישרים, קיימים לה מקבילים מממדים גבוהים יותר: מספרי העוגה (Cake number) עבור מרחב תלת-ממדי ובעיות סידור על-מישורים (Arrangement of hyperplanes) עבור מרחבים ממימד גבוה מ-3.

הסדרה ונוסחה

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

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

בנוסף ניתן לקבל את הסדרה מסכום שלושת האיברים הראשונים בכל שורה במשולש פסקל, או האיבר הראשון בכל שורה במשולש פלויד (אנ').^[ב] ההפרש בין האיבר ה-n-י בסדרה לבין האיבר שלפניו הוא n.

לפיכך, סדרה זו (סדרה A000124 באתר 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)+\cdots +1+f(0)$ .

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

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

.

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

סדרה A000124 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים
סדרת המסעדן העצלן, באתר MathWorld (באנגלית)

ביאורים

^ משולש ברנולי הוא משולש בו האיבר בשורה ה- $n$ והעמודה ה- $k$ נתון על ידי $\sum _{p=0}^{k}{n \choose p}$
^ משולש פלויד הוא סידור של המספרים הטבעיים בשורות כך שאורך השורה הראשונה הוא 1 ולאחר מכן גדל ב-1 בכל פעם

[1] משולש ברנולי הוא משולש בו האיבר בשורה ה- $n$ והעמודה ה- $k$ נתון על ידי $\sum _{p=0}^{k}{n \choose p}$

[2] משולש פלויד הוא סידור של המספרים הטבעיים בשורות כך שאורך השורה הראשונה הוא 1 ולאחר מכן גדל ב-1 בכל פעם

[א]

[ב]