עקרון הכיסאות המוזיקליים

בגיליון הקודם סיפרנו על עקרון שובך היונים: אם יש יותר יונים מתאים, שתיים מהן תצטרכנה להצטופף באותו תא. עיקרון פשוט עוד יותר הוא בכיוון ההפוך: אם יש פחות יונים מאשר תאים, לפחות תא אחד יישאר ריק. כפי שאם יש פחות כיסאות מאנשים במשחק הכיסאות המוזיקליים יהיה אדם ללא כיסא (את השם “עקרון הכיסאות המוזיקליים” הציע המתמטיקאי דן עמיר).  או, שאם קונים \(99\) שלגונים ל-ִ\(100\) ילדים, יהיה ילד שלא יקבל שלגון. פשוט? ובכן, כמו במקרה של עקרון שובך היונים, תלוי איך משתמשים בזה. הנה משפט שנראה פשוט, אבל איני מכיר לו שום הוכחה פשוטה.

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

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

1-CH 2-CH

אבל אם \(5\) קטעים יעברו בין \(4\) נקודות (כך שיש יותר קטעים מנקודות) שניים מביניהם יהיו “זרים” (לא נפגשים). למשל:

3-CH

כאן יש יותר קטעים מנקודות – \(5\) קטעים כנגד \(4\) נקודות. המשפט אומר שבמקרה כזה יש שני קטעים שאינם נפגשים. ואומנם כך הוא – הקטע \(AD\) אינו פוגש את הקטע \(BC\).

בציור יש שני קטעים שאינם נפגשים – \(AD\) ו-\(BC\). (גם \(AC\) ו-\(BD\) אינם נפגשים). אבל זוהי רק דוגמה, ואילו אנו רוצים להוכיח זאת בצורה כללית. ההוכחה האלגנטית הבאה, של המתמטיקאי הישראלי מיכה פֶּרְלֶס, משתמשת בעקרון הכיסאות המוזיקליים.

פרלס אוהב לתאר את הוכחתו במונחים של כינים שמטילות ביצים על שערות. בכל נקודה עומדת כינה. לכל קטע (“שערה”) שהכינה רואה באותה נקודה, הכינה מסתכלת לאורך הקטע, ומטילה עליו ביצה, בסמוך לנקודה שבה היא יושבת, בתנאי הבא: שכאשר היא מסתכלת מן הקצה הזה בכיוון ימין מן הקטע, היא אינה רואה קטע אחר שיוצא מאותה נקודה. “ראייה” היא בזווית קטנה או שווה ל-\(180\) מעלות, ו”לא לראות” פירושו שעד לקטע הבא יש זווית גדולה מ-\(180\) מעלות. למשל, בדוגמה שלנו הכינה העומדת ב-\(A\) תטיל ביצה על הקטע \(AD\), משום שכשהיא מסתכלת בכיוון \(D\) היא אינה רואה מימינה קטע שיוצא מ-\(A\). הכינה העומדת ב-\(B\) תטיל ביצה על ,\(BC\) הכינה העומדת ב-\(C\) תטיל ביצה על \(CA\), והכינה שעומדת ב-\(D\) תטיל ביצה על \(BD\). בקצה \(D\) של הקטע \(AD\), לעומת זאת, לא תוטל ביצה, משום שהכינה העומדת ב-\(D\) רואה מימינו של \(AD\) את הקטע \(DB\).

4-CH

 הכינה העומדת ב-\(A\) מטילה ביצה על הקטע \(AD\), משום שכשהיא מביטה מימין ל-\(D\) היא אינה רואה קטע – עליה להסתובב ביותר מ-\(180\) מעלות עד לקטע הבא, \(AC\).

ההבחנה המכרעת היא זו: כל כינה מטילה לכל היותר ביצה אחת.

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

5-CH

ליד כל נקודה הוטלה ביצה אחת. מכיוון שיש \(5\) קטעים ורק \(4\) נקודות, יש קטע, \(AB\), שעליו לא הוטלה ביצה.

עתה נוכל להפעיל את עקרון הכיסאות המוזיקליים. כיוון שליד כל נקודה יש לכל היותר ביצה אחת, מספר הביצים אינו עולה על מספר הנקודות. על פי הנתון, יש יותר קטעים מאשר נקודות, ולכן גם יותר קטעים מאשר ביצים (בדוגמה יש \(5\) קטעים, ו-\(4\) סימונים). כשנפעיל את עקרון הכיסאות המוזיקליים נקבל שיש קטע (שאותו נציין, נאמר, כ-\(XY\)) שבאף אחד מקצותיו לא הוטלה ביצה (זהו ה”ילד שלא קיבל שלגון”). העובדה שהקטע לא סומן בביצה בקצה \(X\) משמעה שאפשר לראות מימינו, בנקודה \(X\), קטע \(XU\) מן הקטעים הנתונים; העובדה שהוא לא סומן בצד של \(Y\) פירושה שבנקודה \(Y\) יש קטע \(YV\) שנמצא מימינו של \(XY\). אבל אז הקטעים \(XU\) ו-\(YV\) אינם נפגשים!

6-CH

על הקטע \(XY\) לא הוטלה ביצה. הסיבה: הכינה ב-\(X\) רואה מימין ל-\(XY\) את הקטע \(XU\), והכינה ב-\(Y\) רואה מימין ל-\(XY\) את הקטע \(YV\). הקטעים \(XU\) ו-\(YV\) אינם נפגשים, והם אם כן זוג הקטעים המבוקש.

בדוגמה שלעיל, על הקטע \(AB\) לא הוטלה ביצה. בקצה \(A\) אין ביצה, משום ש-\(AD\) נמצא מימינו של \(AB\), כאשר מסתכלים מכיוון הנקודה \(A\); בקצה \(B\) אין ביצה, משום ש-\(BC\) נמצא מימינו של \(AB\) כשמסתכלים מן הקצה \(C\). ואכן, \(AD\) ו-\(BC\) אינם נפגשים.