רוס, ג'ואי וצ'נדלר רוצים לשכור דירת שותפים בניו־יורק [1]. אלא שכל חדר שונה, ולכל אחד מהם העדפות אחרות: רוס חייב חדר גדול ומרווח לספרי הדינוזאורים הרבים שלו; לצ'נדלר לא חשוב גודל החדר, אלא רק שיהיה קרוב לאמבטיה כדי שיוכל לשטוף בקלות את ברווז המחמד שלו; וג'ואי מוכן לישון בכל מקום, העיקר שלא יאלץ לחלוק מזון. מלבד השאלה איך הם הצליחו למצוא כזאת דירה מרווחת בלב העיר היקרה בעולם [2], עולה השאלה: מהי הדרך הטובה ביותר לקבוע איזה חדר יקבל כל אחד מן החברים וכמה ישלם תמורתו, ועדיין להבטיח שכולם יהיו מרוצים? כאן נכנסת לתמונה הלֶמָה של שפרנר.

לֶמָה (Lemma) במתמטיקה היא משפט עזר, כלומר משפט העוזר לנו להוכיח משפטים אחרים [3]. משפט כזה הוא הלֶמָה של שפרנר, משפט העוסק בצביעת קודקודי משולשים בצבעים שונים שפרסם עמנואל שפרנר (Emmanuel Sperner) ב־1928 [4].

הדרך הטובה ביותר להסביר היא בעזרת משחק, מה נדרש? קחו דף נייר ושלושה עפרונות צבעוניים. ציירו משולש גדול וצִבעו כל קודקוד שלו בצבע אחר. לאחר מכן חלקו את המשולש שציירתם למשולשים פנימיים קטנים (פעולה זו נקראת Triangulation) לאחר מכן חלקו כרצונכם את המשולש שציירתם למשולשים פנימיים קטנים [5]. רק שימו לב כי החלק המשותף לשני משולשים צמודים חייב להיות קודקוד או צלע. נדרוש גם שקודקוד שנמצא על צלע של המשולש החיצוני ייצבע בצבע אחד הקודקודים. אם קודקוד מונח על צלע שקודקודיה צבועים באדום ובצהוב, אי אפשר לצבוע את הקודקוד של המשולש הפנימי בכחול. צִבעו לפי החוקים ונסו להגיע למספר נמוך ככל האפשר של משולשים ססגוניים. כלומר משולשים ששלושת קודקודיהם צבועים בצבעים שונים (כמו המשולש החיצוני הגדול במשחק שלנו). כמה משולשים ססגוניים התקבלו?

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

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

המטרה שלנו היא למצוא נקודה בתוך המשולש שתהיה מקובלת על שלושת החברים ומתאימה להעדפותיהם. הסכום לא חייב להתחלק באופן שווה, כיוון שהחדרים אינם זהים, וכל אחד מן החברים מעדיף חדר שונה. כדי למצוא נקודה כזו נשאל מספר מועט של שאלות מנחות לפי מיקום הקודקודים ביחס לצלעות: האם תהיה מוכן לשלם על החדר הקטן 1,000 דולר בחודש? האם תהיה מוכן לשלם על החדר הגדול 3,000 דולר בחודש? וכדומה. על פי התשובות קובעים את צבעי הקודקודים. מכיוון שצביעת קודקודי המשולש עונה על תנאי הלֶמה של שפרנר, חייב להיות לפחות משולש פנימי ססגוני אחד! כל משולש ססגוני מייצג מקרה שבו יהיו כל שלושת השוכרים מרוצים גם מן החדר הנבחר וגם מן המחיר שהם נדרשים לשלם עבורו. לדוגמה, אם באחד המשולשים רוס אמור לשלם 2,000 דולר על החדר הגדול, הסכום שהוא יהיה מוכן לשלם יתקרב לכך ויעמוד על 1,900 – 2,100 דולר, גם אם הוא היה בהפסקה. ככל שמספר המשולשים הקטנים יהיה רב יותר, כך נקבל דיוק גבוה יותר.

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

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

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

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

נבחן את האפשרויות:

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

צלע ססגונית אחת – לא תיתכן אפשרות כזאת .מדוע? נסו להוכיח זאת.

שתי צלעות ססגוניות – ייתכנו רק אם יש שני צבעים בקודקודי המשולש.

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

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

מקורות:

[1] חלוקת שכירות הוגנת על ידי הלֶמה של שפרנר

[2] הסדרה חברים – Pitch meeting

[3] הגדרת לֶמָה במתמטיקה

[4] הלמה של שפרנר

Trilinear Coordinates [5]

[6] קישור ליישומון (אפליקציה) המחלק את שכר הדירה על פי עקרון זה

[7] חיתוך עוגות: Two-player envy-free multi-cake division