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

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

אוקיי, ולמה כשיש שישה אנשים זה כן עובד? נתחיל שוב מצ'נדלר. יש לו חמישה חברים שמשתתפים במשחק, ולכן לפחות שלושה מהם שונאים אותו, או שלפחות שלושה מהם אוהבים אותו (הפעם זה לא בדיוק "או" מתמטי – במובהק רק אחת משתי האפשרויות תתרחש) – זו דוגמה נאה לשימוש בעקרון שובך היונים הכללי יותר שאומר שאם מחלקים \(n\) עצמים ל-\(m\) תאים יש בהכרח תא שמכיל לפחות \(\left\lceil \frac{n}{m}\right\rceil \) עצמים (הסימון הזה הוא לערך שלם עליון – המספר הטבעי הקרוב ביותר מלמעלה ל-\(\frac{n}{m}\)).

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

התרגיל הבא בתור הוא להראות שאם יש 9 אנשים, אז מובטח שתהיה שלישיית שונאים או רביעיית אוהבים (או לחילופין, תהיה שלישיית אוהבים או רביעיית שונאים – הסבירו לעצמכם למה זה לא אותו דבר כמו לומר שתהיה רביעיית אוהבים או רביעיית שונאים, מה שדורש כבר 18 אנשים), ונראה לי שהעיקרון כבר ברור. השאלה שאנו שואלים את עצמנו היא – האם זה תמיד עובד? האם לכל \(r,s\) קיים מספר חברים, שנסמן \(R\left(r,s\right)\), כך שבקבוצה עם לפחות \(R\left(r,s\right)\) אנשים מובטחת לנו קבוצה של \(r\) אוהבים או קבוצה של \(s\) שונאים? משפט רמזי אומר שהתשובה חיובית בכך שהוא נותן חסם עליון על \(R\left(r,s\right)\) לכל \(r,s\). מה שדיברנו עליו בתחילת הפוסט הוא בדיוק המקרה של \(R\left(3,3\right)\) וראינו כי \(R\left(3,3\right)=6\).

ההוכחה של המשפט היא באינדוקציה, ואינדוקציה קצת יותר מחוכמת מהרגיל במובן זה שהיא "דו ממדית". ראשית שמים לב לכך ש-\(R\left(1,s\right)=R\left(r,1\right)=1\) תמיד, באופן די טיפשי – קבוצה של אדם בודד היא תמיד קבוצה של אוהבים/שונאים "באופן ריק". למי שזה נשמע לו לא הגיוני בעליל, תחשבו על זה כך – קבוצת אנשים היא קבוצה של אוהבים או שונאים כל עוד לא הוכח אחרת; כדי להוכיח שקבוצה איננה קבוצת אוהבים צריך להביא זוג שונאים בתוכה, וכדי להוכיח שהיא לא קבוצת שונאים צריך להביא זוג אוהבים בתוכה. בקבוצה בעלת אדם אחד אי אפשר להביא זוג שכזה ממילא, ולכן הקבוצה נחשבת הן לקבוצת אוהבים והן לקבוצת שונאים בו זמנית. כן, זה מוזר וקשה לעיכול למדי למי שטרם נתקל בשיקולים שכאלו, אבל במתמטיקה הם נפוצים למדי ותקינים לחלוטין.

השלב הבא באינדוקציה הוא זה: אנחנו רוצים למצוא חסם עליון על \(R\left(r,s\right)\) בהינתן שאנחנו כבר יודעים חסמים עליונים על \(R\left(r-1,s\right)\) ו-\(R\left(r,s-1\right)\). החסם העליון יהיה פשוט למדי – נוכיח שמתקיים \(R\left(r,s\right)\le R\left(r-1,s\right)+R\left(r,s-1\right)\), וחסל.

אם כן, הבה ונתבונן על קבוצה בעלת \(R\left(r,s\right)\) אנשים. ניקח איש אחד, נקרא לו צ'נדלר, ונחלק את שאר האנשים לשתי קבוצות – חברי צ'נדר ואויבי צ'נדלר. אני מניח שאתם מבינים לאן אני הולך – הפתרון של המקרה הכללי יהיה הכללה פשוטה של המקרה של \(R\left(3,3\right)\). מה שאנחנו רוצים לראות הוא שיש לצ'נדלר מספיק חברים או מספיק אויבים כדי להפעיל אחת מהנחות האינדוקציה.

אם לצ'נדלר יש לפחות \(R\left(r-1,s\right)\) חברים, סיימנו – בקבוצה הזו או שיש \(s\) אויבים (ואז סיימנו) או שיש בה \(r-1\) חברים ואז יחד עם צ'נדלר נקבל קבוצה של \(r\) חברים וסיימנו. בדומה, אם יש לו לפחות \(R\left(r,s-1\right)\) אויבים סיימנו באותו האופן. למה לא ייתכן שאין לו לא מספיק חברים ולא מספיק אויבים?

כדי לא להתבלבל נכניס עוד כמה סימונים למשחק. \(A\) יהיה מספר החברים של צ'נדלר, \(B\) יהיה מספר האויבים שלנו, וראינו ש-\(A+B+1=R\left(r-1,s\right)+R\left(r,s-1\right)\) (הפלוס 1 הוא כי גם את צ'נדלר סופרים). אז אם \(A<R\left(r-1,s\right)\) וגם \(B<R\left(r,s-1\right)\) זה אומר ש-\(A+B\le R\left(r-1,s\right)+R\left(r,s-1\right)-2\), כלומר שלא ייתכן ש-\(A+B+1=R\left(r-1,s\right)+R\left(r,s-1\right)\) (למי שעדיין לא רואה את זה, \(a<b\) שקול לאמירה ש-\(a\le b-1\) אם \(a,b\) הם טבעיים; זו אבחנה מועילה מאוד לעתים).

זה מסיים את ההוכחה; עוד הרחבה לא מסובכת מטפלת במקרה יותר כללי, שבו זוג אנשים יכול להיות יותר מסתם חברים או אויבים, אלא יש \(s\) סוגים שונים אפשריים של קשרים ביניהם – ושוב, אפשר להראות שלכל סדרת מספרים \(r_{1},r_{1},\dots,r_{s}\) קיימת כמות אנשים שהחל ממנה, מובטח שעבור \(i\) כלשהו יש קבוצה של \(r_{i}\) אנשים שהקשרים ביניהם הם רק מסוג \(i\). בניסוח אינטואיטיבי יותר ופחות פורמלי – במבנים גדולים מספיק חייבות לצוץ תבניות מסויימות (זה, על רגל אחת, הרעיון של תורת רמזי; משפט רמזי מטפל בסוג ספציפי של תבניות – בלשון מתמטית, הוא מטפל בתת-גרפים מונוכרומטיים של גרף עם קשתות צבועות).

לסיום, הנה שאלה קטנה וחביבה. ראינו ש-\(R\left(3,3\right)=6\), כלומר שאם יש 6 אנשים מובטחת לנו שלישיית חברים או שלישיית שונאים, וש-5 אנשים אינם מספיקים. אפשר להראות גם ש-\(R\left(4,4\right)=18\). אם כן, מהו \(R\left(5,5\right)\)?

באופן מפתיע למדי, ממבט ראשון, התשובה אינה ידועה עד היום. משפט רמזי אמנם נותן חסם עליון פשוט על \(R\left(5,5\right)\), אבל לא עוזר למצוא את הערך המדויק שלו. בדי עמל הצליחו המתמטיקאים להראות ש-\(43\le R\left(5,5\right)\le49\), אבל זהו זה. הרי לכם בעיה פתוחה במתמטיקה שתיאוריה הוא אלמנטרי דיו כדי להיות מוסבר בפוסט קצר. אתם עשויים לתהות מה הקושי הגדול כל כך – האם לא ניתן לגייס מחשבים לעבודה ולעשות חיפוש ממצה כלשהו? נאמר, ניקח את כל הקבוצות האפשריות של יחסי אהבה/שנאה על 43 אנשים ונבדוק לכל אחת… כן, ובכן, תשכחו מזה. אם יש לנו 43 אנשים אז יש לנו \(\frac{43\cdot42}{2}=903\) זוגות בסך הכל. לכל אחד מהם אנחנו יכולים לבחור, באופן בלתי תלוי באחרים, ביחס אהבה/שנאה, כך שיש לנו כבר \(2^{903}\) קבוצות אפשריות. המספר \(2^{903}\) הוא גדול. ממש, ממש גדול. כמה גדול? גדול להחריד גם בהשוואה למספרים הגדולים שדיברתי עליהם בפוסט הזה. אז חיפוש ממצה הוא כיוון אבוד לחלוטין; הכרחי יהיה לעשות הרבה עבודת הכנה מתמטית תיאורטית כדי שתהיה תקווה להריץ איזה חיפוש מחשב שגם יתן את התוצאה הנכונה. ונניח שנצליח, האתגר הבא יהיה מציאת \(R\left(6,6\right)\). כדי להבין עד כמה הקפיצה הזו בקושי בין \(R\left(5,5\right)\) ו-\(R\left(6,6\right)\) תהיה משמעותית כדאי לתת את הבמה לרגע לג'ואל ספנסר שמצטט את ארדש:

Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5,5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6,6). In that case, he believes, we should attempt to destroy the aliens.

הציטוט הנפלא הזה לבדו שווה את כל הפוסט.

אני ממשיך את סדרת הפוסטים שלי על קומבינטוריקה ברמה תיכונית, והפעם אני רוצה לנקוט בגישה "מתמטית" לדברים שכבר גילינו. המתמטיקאי תמיד מנסה לבחון מחדש את ההנחות שלו ולהקל על הדרישות בכדי להכליל את התוצאות שלו, וזה גם מה שאני רוצה לעשות. הנוסחה המרכזית שגילינו עד כה הייתה כי \(\frac{n!}{k!\left(n-k\right)!}\), שאותו סימנו בקיצור \({n \choose k}\) וכינינו "מקדם הבינום"(מסיבות שהסברתי בפוסט קודם) הוא מספר הדרכים לבחור \(k\) מתוך \(n\) עצמים. אלא שכאן יש לי שתי הנחות סמויות: שהבחירה היא ללא החזרה, וללא חשיבות לסדר. בפוסט הזה אנסה להסביר מה זה אומר, ומה מקבלים כשמשחקים עם ההנחות הללו.

בואו נזכור מה \({n \choose k}\) אומר באמצעות דוגמה: בלוטו, אם נשכח לרגע מהמספר הנוסף, נבחרים שישה מספרים מתוך 49. הבחירה הזו היא ללא חשיבות לסדר: אם המכונה הגרילה קודם כל את 1 ואז את 2, זו אותה הסיטואציה מבחינתנו כמו זו שבה המכונה הגרילה קודם כל את 2 ורק אז את 1. די ברור שאם הייתה חשיבות לסדר, המשחק היה הופך לקשה פי כמה, כי לא היה מספיק לנחש מי יזכה; היה צריך לנחש גם באיזה סדר הם יופיעו.

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

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

ובכן, בחירה בלי החזרה ובלי חשיבות לסדר היא כמו שראינו \({n \choose k}\). לפעמים משתמשים גם בסימון המבלבל \(C_{n}^{k}\) וקוראים לזה "צירופים", אך זה הרבה פחות מקובל במתמטיקה ואני לא משתמש בסימונים הללו אף פעם.

נעבור לבחירה בלי החזרה אך עם חשיבות לסדר, מה שנקרא לעתים בעברית "חליפות"ומסומן ב-\(A_{n}^{k}\). הדרך לחשב את מספר האפשרויות לבחור בלי החזרה ועם חשיבות לסדר \(k\) מתוך \(n\) עצמים היא פשוטה למדי כי אפשר לחשוב עליה כתהליך דו-שלבי: קודם כל נבחר \(k\) עצמים מתוך ה-\(n\) בלי חשיבות לסדר, ואז נבחר את האופן שבו "מסדרים"אותם. כבר ראינו שיש \({n \choose k}\) אפשרויות לבחור את העצמים בלי חשיבות לסדר, ושבהינתן \(k\) עצמים יש \(k!\) דרכים לסדר אותם, כך שהתוצאה היא \({n \choose k}k!=\frac{n!}{k!\left(n-k\right)!}k!=\frac{n!}{\left(n-k\right)!}\). אפשר גם להגיע לתוצאה הזו בדרך ישירה: בהתחלה יש לנו \(n\) איברים לבחור מהם, אחר כך יש לנו \(n-1\) איברים, אחר כך \(n-2\) וכן הלאה… עד שבסופו של דבר יש לנו \(n-k\) איברים ואז אנחנו כבר לא בוחרים. נקבל את המכפלה \(n\cdot\left(n-1\right)\cdot\left(n-2\right)\cdots\left(n-k+1\right)\) (ה-\(+1\) בסוגר האחרון נובע מכך שהבחירה האחרונה מתבצעת רגע לפני שאנו נשארים עם \(n-k\) איברים) – לא קשה לראות שמכפלה זו אכן שווה ל-\(\frac{n!}{\left(n-k\right)!}\), אבל היא יותר מסורבלת לכתיבה. שימו לב, אגב, שאם היינו בוחרים \(k=n\) היינו מקבלים את התוצאה \(n!\) – כלומר, הכללנו גם את הרעיון של סידור \(n\) איברים בשורה.

אני רוצה להציג עוד נקודת מבט שתכליל הן את הצירופים והן את החליפות, ותיתן לנו עוד נוסחה מאוד פופולרית. בואו נחשוב לרגע שיש לנו \(n\) כדורים, ש-\(k\) מתוכם אדומים והיתר כחולים, ואנחנו שואלים את עצמו בכמה דרכים ניתן לסדר אותם בשורה. שימו לב שכל הכדורים מאותו צבע נראים לנו זהים – אם נחליף את המקומות של שני כדורים בעלי אותו צבע נקבל תוצאה שנראית לנו זהה לקודמת, ולכן אין צורך לספור אותה שוב. מה עושים? דרך אחת היא זו: ראשית נחשוב על כל הכדורים כעל אובייקטים שונים זה מזה, ואז יש \(n!\) דרכים שונות לסדר אותם בשורה. כעת צריך "לתקן"את הספירות הכפולות שביצענו, והדרך לעשות זאת היא לספור בכמה דרכים שונות ניתן לשנות את הסדר הפנימי בין הכדורים האדומים, ובכמה דרכים שונות ניתן לשנות את הסדר הפנימי בין הכדורים הכחולים, ולחלק בתוצאה זו. יש \(k\) כדורים אדומים ולכן \(k!\) סידורים פנימיים שלהם, ובאופן דומה יש \(\left(n-k\right)!\) סידורים פנימיים של הכדורים הכחולים, ולכן התוצאה היא \(\frac{n!}{k!\left(n-k!\right)}\) – בדיוק \({n \choose k}\) וזה לא כל כך מפתיע כי אפשר לחשוב על הסידור הנ"ל כעל "בחר \(k\) מקומות עבור הכדורים האדומים ושים את הכחולים ביתר". למעשה, הגישה הזו הייתה האופן שבו הוכחתי את הנוסחה עבור \({n \choose k}\) מלכתחילה.

כעת להכללה המבוקשת – מה קורה אם יש לי כדורים אדומים, ירוקים, צהובים וכחולים? ומה אם יש עוד צבעים? באופן כללי אפשר לחשוב על כך ש-\(n\) האיברים מתחלקים לקבוצות, כך שמספרי האיברים בקבוצות הם \(k_{1},k_{2},\dots,k_{t}\). קבוצה יכולה להכיל גם איבר בודד; לכן אנחנו יכולים להניח שה-\(k\)-ים מתארים את כל האיברים, כלומר מתקיים \(n=k_{1}+k_{2}+\dots+k_{t}\). על פי אותו הגיון שתיארתי קודם, מספר הסידורים האפשריים בשורה של האיברים הללו, כשאנחנו מתעלמים מהסידורים הפנימיים בין איברים מאותו צבע, הוא \(\frac{n!}{k_{1}!k_{2}!\cdots k_{t}!}\). שימו לב ש-\({n \choose k}\) מתאים למקרה בו יש לנו בדיוק שתי קבוצות, ואילו מספר החליפות, \(\frac{n!}{\left(n-k\right)!}\) מתאים בדיוק למקרה שבו יש לנו \(n-k\) עצמים זהים והיתר שונים זה מזה (כך שהנוסחה היא בעצם \(\frac{n!}{\left(n-k\right)!1!1!\cdots1!}\) ואין צורך לכתוב את ה-\(1\)-ים במכנה כי \(1!=1\)). למה הסיטואציה הזו אכן מתארת חליפות? כי ניתן לחשוב על כך שאנחנו מניחים על העצמים שלנו פתקים שבהם או שכתוב מספר כלשהו מ-\(1\) עד \(k\) (שמתארים את מספרם בבחירה) או שכתוב עליהם "לא נבחר", וכל פתקי ה"לא נבחר" זהים זה לזה ויש \(n-k\) מהם.

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

הנוסחה לבחירה עם החזרה ועם חשיבות לסדר היא תוצאה ישירה של עקרון הכפל. תהליך הבחירה שלנו הוא בן \(k\) שלבים; בכל שלב אנחנו בוחרים אחת מ-\(n\) אפשרויות שונות. יש לנו אם כן בסך הכל \(n\cdot n\cdots n=n^{k}\) אפשרויות שונות. קל להתבלבל ולשכוח מי במעריך החזקה ומי בבסיס (כלומר, האם זה \(k^{n}\) או \(n^{k}\)) ולכן אני ממליץ לנקוט בגישה הבאה: כמה מספרים דו ספרתיים יש, אם מרשים גם לאפס להופיע (כלומר, \(3\) הוא המספר ה"דו ספרתי" \(03\) וכדומה)? \(2^{10}\) או \(10^{2}\)? ובכן, \(2^{10}=1024\) כך שברור שיש כאן בעיה; לעומת זאת \(10^{2}\) מתאים בדיוק, וזה לא מפתיע כי מספר דו ספרתי מורכב מבחירה של אחת מ-10 הספרות האפשריות בתור ספרת האחדות, ואחת מ-10 הספרות האפשריות בתור ספרת העשרות.

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

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

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

בגישה הזו מה שאני "בוחר" הוא את המקומות שבהם אני רוצה לשים את המחיצות. על פניו כל רווח בין שני כדורים, או בין כדור והקיר, הוא מיקום חוקי. יש \(k\) כדורים ולכן \(k+1\) רווחים (ציירו שני כדורים ותראו את שלושת הרווחים: מימין לכדור הימני, משמאל לשמאלי, ובין שניהם). לכן יש לי בחירה של \(n-1\) איברים מתוך קבוצה של \(k+1\) איברים, בלי חשיבות לסדר ועם החזרה, כי אפשר לבחור באותו רווח כמה פעמים… היי, רגע, אז מה בעצם השגתי כאן? אני עדיין תקוע עם בעיה של בחירה עם החזרה ולא שיפרתי כלום!

אם לגלוש לרגע למתמטיקה יותר מתקדמת, כשכזה דבר קורה זה לא בהכרח סוף העולם. אפשר לחזור על אותו תהליך שוב ושוב ולראות האם זה הופך את הבעיה בהדרגה לפשוטה יותר. לרוע המזל, זה לא מה שקורה כאן – מבעיה של בחירת \(k\) מתוך \(n\) עברתי לבעיה של בחירת \(n-1\) מתוך \(k+1\), ואם אעשה את התעלול שוב אחזור לבעיה של בחירת \(k\) מתוך \(n\). צריך להוסיף עוד תעלול לתמונה, אם כך. והתעלול הזה פשוט – אני הולך לאסור על תאים ריקים.

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

נחזור לבעיית השמת המחיצות. אם אסור שיהיו תאים ריקים, זה אומר שאסור לשים שתי מחיצות בין אותו זוג כדורים, ואסור לשים מחיצה בין כדור ובין הקיר. מצד שני, יש לנו הפעם \(n+k\) כדורים, ולכן יש בסך הכל \(n+k-1\) רווחים שבהם ניתן לשים את \(n-1\) המחיצות. הפעם הבחירה היא בלי החזרות כי כאמור, אסור לשים שתי מחיצות בין אותו זוג כדורים – אסור לבחור פעמיים באותו רווח שבין כדורים. לכן יש לנו בחירה של \(n-1\) איברים מתוך \(n+k-1\) איברים, וזה בדיוק \({n+k-1 \choose n-1}\), ואת זה ניתן לכתוב גם כ-\({n+k-1 \choose k}\). בזאת מצאנו את הנוסחה לשיטת החלוקה הרביעית והאחרונה.

לפני שנסיים להפעם אני רוצה לתאר שימוש פשוט אחד בבחירה עם החזרה ובלי חשיבות לסדר, שבינתיים אולי נראית מפחידה ומסובכת ולא מועילה כלל. נביט במשוואה \(x_{1}+x_{2}+\dots+x_{n}=k\), כאשר \(k\) הוא מספר שלם והערכים שאנחנו מרשים למשתנים לקבל הם רק ערכים שלמים אי שליליים (משוואות כאלו צצות בפועל! בעולם האמיתי! תאמינו לי!). כמה פתרונות יש למשוואה הזו? בדיוק מספר האפשרויות לבחור \(k\) איברים מתוך \(n\), עם החזרה ובלי חשיבות לסדר. למה? אשאיר זאת כתרגיל לקורא.

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

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

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

קרוב לודאי שרבים מכם שואלים את עצמכם על הקומבינטוריקה בפרט את אותה שאלה שלעתים שואלים על המתמטיקה בכלל – למי אכפת? למי אכפת אם יש 113,332,442 צירופים אפשריים לפרוזן יוגורט בדוכן הקרוב, ולא סתם 113,332,441? מה המספר הזה נותן לנו בכלל? מה הטעם בכל זה?

ראשית כל יש לענות לכך שאכן, לרוב לא אכפת לנו מהמספרים המדוייקים. מה שמעניין, כאמור, הוא "קצב הגידול" של הבעיה, או סדר הגודל שלה. דוגמה קלאסית לכך היא הלוטו: חישוב ההסתברות לזכות בלוטו היא חישוב קומבינטורי פשוט (אנו רוצים לחשב את מספר כל התוצאות האפשריות שיכולות להתקבל בלוטו, ואם מספר זה הוא \(A\), אז ההסתברות לזכייה בלוטו היא \(\frac{1}{A}\), ובמילים – \(1\) ל-\(A\), למשל "1 לעשרה מיליון"). כאן המספר המדוייק באמת לא חשוב לנו, אבל חשוב לנו ההבדל שבין הסתברות של 1 ל-6 לזכות בלוטו כל שבוע (ואם הפרס לכל זוכה היה מיליון ש"ח, אז בהסתברות שכזו גם אני הייתי ממלא לוטו באדיקות), ובין הסתברות של 1 לכמה עשרות מיליונים (אני לא ממלא לוטו).

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

עם זאת, לפעמים אנחנו מתעניינים מאוד במספרים המדוייקים, עד לספרה האחרונה. סיבה מרכזית אחת לכך היא שמספרים מדוייקים מאפשרים לנו למצוא קשרים בין בעיות שנראות שונות מהותית. הנה דוגמה קלאסית: סדרה חוקית של סוגריים היא סדרת של סמלים שהם או \(")"\) (סוגר ימני) או \("("\) (סוגר שמאלי), כך שבשום שלב, בקריאה משמאל לימין של הסדרה, לא נוצר מצב שבו קראנו יותר סוגרים ימניים משמאליים (כלומר, לא "סגרנו" סוגריים שבכלל לא נפתחו). כך למשל הסדרה \(()(())\) היא חוקית ואילו \()(()\) אינה חוקית. לא קשה כל כך להראות שהסדרה \(a_{n}\) שבה \(a_{n}\) מייצג את מספר הסדרות החוקיות שמכילות \(n\) סוגריים שמאליים ו-\(n\) סוגריים ימניים מתחילה עם הערכים הבאים: \(1,2,5,14,42,132,429\).

נעבור לבעיה לחלוטין לא קשורה – שילוש של מצולע משוכלל. מצולע משוכלל עם \(n\) צלעות הוא מצולע שבו כל הצלעות וכל הזוויות הפנימיות שוות בגודלן. למשל: משולש שווה צלעות. למשל: ריבוע. למשל: משושה משוכלל, וכן הלאה. כשעוסקים במצולעים במדעי המחשב – בעיקר בגרפיקה – נוח לעתים קרובות לפרק אותם למשולשים על ידי מתיחת קווים בין קודקודים קיימים עד שהצורה חולקה כולה למשולשים (לפעולה זו קוראים שילוש – טריאנגולציה). נשאלת השאלה – כמה שילושים שונים קיימים למצולע בעל \(n\) צלעות? מכיוון שעבור \(n=1,2\) אין בכלל מצולעים בעלי \(n\) צלעות, אני "ארמה" טיפה: \(b_{n}\) יסמן את מספר השילושים של מצולע בעל \(n+2\) צלעות. והנה זה פלא: הסדרה \(b_{n}\) גם היא מתחילה עם הערכים \(1,2,5,14,42,132,429\). זה מייד מדליק אצלנו נורת איתות בראש – הייתכן שיש קשר בין שתי הבעיות, בעיית הזוגות החוקיים של סוגריים ובעיית הטריאנגולציה? וכדי לאמת את החשדות שלנו אנחנו מחשבים (באמצעות מחשב) עוד כמה ערכים של הסדרות – והנה, כל ערך חדש שאנו מחשבים אכן יהיה זהה. וזה מוסיף ומחזק את האמונה שלנו ששתי הסדרות הללו חד הן, עד לשלב שבו נטרח לקחת עט ונייר ולהוכיח את הקשר בין שתי הסדרות. ההוכחה עצמה אינה טריוויאלית אך גם אינה מסובכת מדי, והסדרה \(a_{n}\) היא סדרה כה מעניינת ומרכזית ומופיעה בעוד הקשרים רבים ושונים שהיא זכתה לשם מיוחד: "מספרי קטלן". למעשה, קיימת אפילו נוסחה סגורה עבורם, אך לא אציג אותה כעת.

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

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

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

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

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

בואו נעבור להתמודד עם בעיה קצת יותר מעניינת. ניקח חבילת קלפים סטנדרטית של 52 קלפים, ונשאל את עצמנו – בכמה דרכים שונות ניתן לערבב אותה? "ערבוב" הוא בסך הכל סידור כלשהו של הקלפים בשורה – הקלף הראשון, השני וכן הלאה. בואו נניח שאנחנו לא ממש מערבבים את החבילה, אלא בוחרים במפורש מי יהיה הקלף הראשון, ומי יהיה השני וכן הלאה. איך עושים זאת? יש לנו 52 אפשרויות לבחירת הקלף הראשון. אחרי שבחרנו אותו הוא "יוצא מהמשחק" ולכן יש לנו רק 51 אפשרויות לבחור את הקלף השני. אם כן, כמה אפשרויות יש לנו לבחור את שני הקלפים הראשונים? על פי עיקרון הכפל, מכיוון שמדובר בבחירה דו-שלבית, יש לנו \(52\cdot51\) אפשרויות. נקודה עדינה שיש לשים לב אליה היא שגם אם נבחר את אותם קלפים אך בסדר שונה (אס עלה ראשון, מלך עלה שני אל מול מלך עלה ראשון, אס עלה שני) זה עדיין ייחשב לשתי התחלות של ערבובים שונים (כי סדר הקלפים שונה).

מכאן ואילך ההמשך הוא באותה הרוח: יש 50 אפשרויות לבחירת הקלף השלישי, 49 לבחירת הרביעי, וכן הלאה. כשהגענו לקלף האחרון נותרה לנו רק בחירה אחת – שלו בלבד – ולכן יש אפשרות אחת בלבד. בסיכומו של דבר עיקרון הכפל ייתן לנו את התוצאה \(52\cdot51\cdot50\cdots3\cdot2\cdot1\). מספר זה ניתן לכתוב גם כ-\(1\cdot2\cdots52\) (הרי אין חשיבות לסדר ביצוע פעולות הכפל). מכיוון שדבר שכזה – הכפלה של כל המספרים מ-1 ועד \(n\) – היא דבר נפוץ למדי במתמטיקה (ובקומבינטוריקה בפרט) נהוג לתת לה שם וסימון מיוחד: למכפלה \(1\cdot2\cdots n\) (כאשר \(n\) הוא תמיד מספר טבעי חיובי) קוראים "\(n\) עצרת"ומסמנים אותה ב-\(n!\) (\(n\) ואז סימן קריאה – כמו רוב הסימונים, אין מאחוריו יותר מדי הגיון מחוכם אלא בעיקר קונבנציה שבחר מישהו והשתרשה במהלך השנים).

אם כן, יש \(52!\) ערבובים של חבילות קלפים, ובאופן כללי יש \(n!\) לסדר בשורה \(n\) איברים שכולם שונים זה מזה – לסידור שכזה קוראים "תמורה", ובעברית – פרמוטציה. למי שסקרן, הערך המספרי המדוייק של \(52!\) הוא \(80658175170943878571660636856403766975289505440883277824000000000000\). המספר העצום בגודלו הזה הוא הסיבה לעושר הרב שאפשר למצוא במשחקי קלפים – אין כמעט שום סיכוי שיתקבלו שני ערבובים זהים, ולכן שני משחקים זהים.

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

עם הבעיה הזו אפשר להתמודד בעזרת הכלי שכבר רכשנו – מספר הפרמוטציות של \(n\) איברים. הבה ונניח ש-13 הקלפים נבחרים באופן הבא: ראשית מערבבים את החבילה, וכעת נותנים לשחקן את 13 הקלפים הראשונים בערבוב. אחרי שנותנים לו אותם הסדר הפנימי של הקלפים "נמחק", ולכן אם נספור כל ערבוב של החבילה באופן שונה, נבצע ספירה כפולה. מכיוון שזה מבלבל קצת בהתחלה, הבה ונביט בדוגמה פשוטה יותר: נניח שיש לנו חבילה שכוללת ארבעה קלפים בלבד: \(\mbox{A,K,Q,J}\), ושהשחקן רוצה לקבל שניים מהם. כבר את ארבעת הקלפים הללו ניתן לערבב בצורות רבות – 24, ליתר דיוק – ולכן לא אראה את כולן אלא אשאל שאלה אחרת: בכמה דרכים שונות אפשר לערבב את החבילה כך שהשחקן יקבל את \(\mbox{A,K}\)?

ובכן, אלו הן האפשרויות (שתי האותיות שמצד שמאל הן מה שהשחקן יקבל): \(\mbox{AKQJ,AKJQ,KAQJ,KAJQ}\). ספרנו ארבע פעמים חלוקה שהיינו אמורים לספור רק פעם אחת. איך אפשר לנטרל זאת? הצעד הראשון יהיה לשים מעין "מחיצה" שתפריד בין מה שהשחקן מקבל ומה שלא: \(\mbox{AK|QJ,AK|JQ,KA|QJ,KA|JQ}\). כעת נשאל את עצמו – מה קורה מכל אחד מעברי המחיצה? בצד שמאל אנחנו "בוחרים" את אחת משתי הפרמוטציות האפשריות של האיברים \(\mbox{A,K}\), ובצד ימין אנו "בוחרים" את אחת משתי הפרמוטציות האפשריות של האיברים \(\mbox{J,Q}\). בצורה הזו מתקבלות כל האפשרויות לבנות חלוקה של \(\mbox{A,K,Q,J}\) שבה \(\mbox{A,K}\) בצד שמאל ו-\(\mbox{Q,J}\) בצד ימין.

חזרה לבעיה שלנו – כאן יש 13 קלפים בצד שמאל, ו-39 קלפים בצד ימין. לכן יש \(13!\) אפשרויות לבחור סידור לקלפים בצד שמאל, ו-\(39!\) אפשרויות לבחור סידור לקלפים בצד ימין, ולכן על פי עקרון הכפל יש \(13!\cdot39!\) אפשרויות לבחור סידורים לכל הקלפים גם יחד כל עוד תובעים ש-13 הקלפים שבצד שמאל ישארו כולם בצד שמאל. במילים אחרות – לכל בחירה של \(13\) קלפים, יש בדיוק \(13!\cdot39!\) ערבובים של החבילה שבה \(13\) הקלפים הללו הם אלו שנבחרים.

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

אם כן, אם אנחנו יודעים את כמות הרגליים בעדר, ואנו יודעים שלכל כבש ארבע רגליים, משמעות הדבר היא שספרנו כל כבש ארבע פעמים, ולכן כדי לקבל את מספרם של הכבשים צריך לחלק את מה שספרנו ב-4. כך גם בדוגמה שלנו: יש \(52!\) ערבובים שונים של החבילה – זה מספר הרגליים; וכל חלוקת \(13\) קלפים נספרה \(13!39!\) פעמים – זה מספר הרגליים שיש לכבש; ולכן יש בסך הכל \(\frac{52!}{13!39!}\) חלוקות שונות. גם זה מספר עצום – \(635013559600\), אבל הוא קטן משמעותית מ-\(52!\).

באופן כללי אם יש לנו \(n\) אובייקטים שונים ואנו רוצים לבחור מתוכם \(k\) אובייקטים בלי חשיבות לסדר הבחירה, אז אותו החשבון מראה שיש \(\frac{n!}{k!\left(n-k\right)!}\) אפשרויות לעשות זאת. גם לביטוי זה יש סימון מקוצר: "\(n\) בחר \(k\)", או \({n \choose k}\) (שימו לב – זה אינו שבר!). היצור הזה מכונה גם "מקדם הבינום" בשל הקשר שלו לבינום של ניוטון – נוסחה כללית לביטויים מהצורה \(\left(a+b\right)^{n}\); ארחיב על כך בפוסט הבא בנושא.