הנה הסיבה שמתמטיקאים כל כך מתעניינים בחיתוך עוגות

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

אבל זה גם בגלל שהרבה מהעבודה של פרוקצ'יה מתמקדת בחקר הכללים המתמטיים לחלוקת דברים. אחת הדרכים לעשות זאת היא לחשוב בצורה מופשטת על קינוח. כבר יותר מ-75 שנה, הוא וחוקרים אחרים שמנסים למסד את ההוגנות שואלים את השאלה הפשוטה והמתעתעת: אילו שיטות לחיתוך עוגה מבטיחות שכל מי שמגיע למסיבה יהיה מרוצה ממה שהוא מקבל?

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

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

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

בשנות ה-40, מתמטיקאים החלו להתעניין ברצינות בגישה מתמטית להוגנות, תוך שימוש בחיתוך עוגה כנקודת גישה. הם התחילו לחקור איך לחלוק בצורה הוגנת בין שלושה אנשים, מכיוון ש-I-cut-you-choose הוא משחק של שני שחקנים. זה הוביל לחיפוש אחר דרכים להרחיב את האלגוריתמים האלה למספרים גדולים באופן שרירותי של אנשים, ולשאול שאלות יותר ניואנסיות, כמו מהי הגינות בדיוק, ואיך מוכיחים זאת?

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

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

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

מתכונים לחיתוך עוגה הוגן

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

בסיפור עתיק יומין זה, פרומתאוס משרה את האסטרטגיה הקלאסית של אני-חותך-אתה-בוחר - הגרסה הפשוטה ביותר של חיתוך עוגה - בהטעיה. אבל כאשר I-cut-you-choose מבוצע מתוך חתירה להוגנות, זה אמור להבטיח את שביעות רצונם של כל המעורבים.

התוצאה היא פרופורציונלית, כלומר כל שחקן מרגיש שהנתח שלו מייצג נתח הוגן מהסך הכל. אז עבור שני שחקנים, שחקן יעריך את הפרוסה שלו ב-1/2; עבור שלושה, חלק הוגן יהיה 1/3. (ועבור מספר n שרירותי של אוכלי עוגה, נתח הוגן יהיה 1/n.) אם העוגה זהה לכל אורכה, המידתיות שקולה לכך שכל הפרוסות יהיו באותו גודל.

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

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

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

הוגו שטיינהאוס מאוניברסיטת ורשה היה אחד המתמטיקאים הראשונים שצללו לתוך המורכבות הזו. במהלך מלחמת העולם השנייה, כששאלות של חלוקה הוגנת של הקרקע התנהלו בקנה מידה גדול ואלים, שטיינהאוס פיתחאסטרטגיית I-cut-you-choose שונהלשלושה שחקנים. היא נקראה שיטת המפריד הבודד.

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

אבל אם בוב או קרלה מסתייגים מאותה יצירה, אז היצירה הזו עוברת לאליס (שהעריכה את כל החלקים באותה מידה). שני החלקים הנותרים (שבוב וקרלה חייבים להעריך ב-2/3 או יותר מהסכום הכולל) משולבים מחדש ומחולקים בין בוב וקרלה באמצעות I-cut-you-choose.

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

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

לאחר מכן מאחדים את החיתוך מחדש עם העוגה שנותרה, והתהליך מתחיל שוב עם השחקנים הנותרים. כשנותרים רק שני שחקנים, הם משתמשים ב-I-cut-you-choose.

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

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

האם חיתוך עוגה יכול להיות נקי מקנאה?

מאז הופעת הבכורה של שיטת המצטמצמת אחרונה, חיתוך העוגה הניע גוף קטן אך אדיר של מתמטיקה רצינית.

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

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

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

אולם במשך עשרות שנים נוספות, פתרון חיתוך עוגות נטול קנאה לכל מספר שרירותי של אוכלים נותר חמקמק. בסוף שנות ה-80, בתוכנית הטלוויזיה שלו PBSלכל המטרות המעשיות: מבוא למתמטיקה עכשווית, המתמטיקאי סול גרפונקלהציג את בעיית חיתוך העוגה הבלתי פתורהושאלות נלוות של חלוקה הוגנת.

אבל הבעיה לא תישאר ללא פתרון לעוד הרבה זמן. בשנת 1995, ברמס ב-NYU ואלן ד. טיילור מיוניון קולג' ב-Schenectady, ניו יורק, המציאונוהל חדש שחותך עוגה לארבעה אנשיםעִם. "זה נחשב לסוג של פריצת דרך", אומר ברמס. הוא נבנה על גישת ה"גזם" של קונווי וסלפרידג', והפעיל נוהל דומה על כל הזוגות האפשריים של אוכלי עוגות. ברמס וטיילור תיארו כיצד ניתן להרחיב את ההליך לכל מספר אנשים.

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

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

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

האם חיתוך עוגה הוא אינסופי?

פרוקצ'ה מעולם לא יצאה ללמוד חיתוך עוגות. בשנת 2008 הוא לימד קורס על היסודות המתמטיים של בינה מלאכותית. יום אחד, כשהלך הביתה לאחר שנשא הרצאה על הקצאת משאבים ומודל רוברטסון-ווב, הוא הבין איך הוא יכול למצוא גבול תחתון - מספר מינימלי של צעדים, כולל חתכים - לחיתוך עוגה ללא קנאה לכל מספר של אנשים. הגבול התחתון שמצא היה איפשהו סביב n² מדרגות, כאשר n הוא מספר אוכלי העוגה.

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

כשפרוקצ'יה המשיכה בשטח, הוא החל לחשוב יותר על אלגוריתמים שימושיים שיכולים להביא תובנות מחיתוך העוגה - ותיאוריית החלוקה ההוגנת בכלל - לשימוש טוב. דוגמה אחת: חלוקת שכר דירה.

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

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

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

חיתוך עוגה עבור n אנשים, דיווחו עזיז ומקנזי, עשוי לדרוש עד n^n^n^n^n^n פעולות. זה מספר לא הגיוני לחלוטין. המספר המרבי של צעדים עבור חמישה אנשים יהיה בסביבות 2 על 10^2,180. זה אומר שחמישה אנשים שחותכים את העוגה מיליארדי פעמים בשנייה במשך 100 טריליון שנה אולי בקושי מתחילים.

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

בעיית חיתוך העוגה נמשכת

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

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

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

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

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

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

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

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

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

"אני מתעניין בזה עכשיו לא רק בגלל שהוא יפה במתמטיקה", אומר טאו, "אבל אני עדיין מאמין שיש הרבה מה לעשות".