למה לא שלושים ושתיים?

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

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

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

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

חידת העוגה

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

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

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

ועכשיו עצרו רגע, לפני שאתם מוסיפים את הנקודה השישית. עם חמש נקודות יש שש־עשרה חלקים, והמספרים עד עכשיו היו 1, 2, 4, 8, 16. כמה יהיו עם שש? כתבו את הניחוש שלכם איפשהו, ורק אז לחצו.

שלושים ואחת

שלושים ואחת. לא שלושים ושתיים. אם יש לכם סבלנות, אפשר לספור ישירות על הציור, ולא להאמין למונה. וזה לא עניין של מזל: בכל מיקום של שש נקודות שתבחרו, כל עוד שום שלושה חתכים לא עוברים באותה נקודה, יוצאים שלושים ואחד חלקים. גררו את הנקודות, פזרו אותן אקראית, והמספר לא יזוז. ואם תמשיכו להוסיף נקודות, תראו שהמרחק מההכפלה רק גדל: 57 במקום 64, אחר כך 99 במקום 128, ו-163 במקום 256. עם עשר נקודות יוצאים 256 חלקים, בזמן שההכפלה הייתה נותנת 512.

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

כמה דברים שווה לשים לב אליהם כבר עכשיו. קודם כל, התבנית 1, 2, 4, 8, 16 לא הייתה «כמעט נכונה». היא החזיקה בדיוק חמש פעמים, בלי שום סטייה, ואז נשברה. שנית, אי אפשר היה לגלות את זה בלי לנסות את המקרה השישי: חמש בדיקות מוצלחות לא אמרו שום דבר על השישית. ושלישית, התשובה תלויה בפרט שאף אחד לא חשב עליו כשניסח את החידה: האם שלושה חתכים נפגשים באותה נקודה.

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

גלריה של תבניות שנשברות

מספר ראשוני הוא מספר שלם, גדול מ-1, שאי אפשר לכתוב כמכפלה של שני מספרים שלמים קטנים ממנו. 2, 3, 5, 7, 11 ו-13 ראשוניים. 12 אינו ראשוני, כי $12 = 3 \cdot 4$, ומספר כזה נקרא פריק. הראשוניים מפוזרים בין המספרים בלי שום סדר גלוי, ולכן מי שמוצא נוסחה שנותנת ראשוני אחרי ראשוני מרגיש שגילה משהו.

הנה נוסחה כזאת. קחו מספר שלם $n$, העלו אותו בריבוע, הוסיפו את $n$ עצמו, והוסיפו 41. ב-$n = 0$ יוצא 41, ראשוני. ב-$n = 1$ יוצא 43, ראשוני. ב-$n = 2$ יוצא 47, ב-$n = 3$ יוצא 53, וב-$n = 4$ יוצא 61: כולם ראשוניים. לאונרד אוילר, מגדולי המתמטיקאים של המאה ה-18, הדפיס את הרשימה הזאת. המשיכו בעצמכם, צעד אחר צעד, ונחשו מראש אם הרצף ייגמר.

הרצף נמשך ארבעים פעמים ברציפות, מ-0 ועד 39. ואז, ב-$n = 40$, הוא נשבר: יוצא 1681, שהוא $41 \cdot 41$. ומי שמתבונן בנוסחה יכול היה לראות את זה מראש, בלי שום בדיקה:

ואחרי שרואים את זה, ברור שגם $n = 41$ לא יעבוד: $41^2 + 41 + 41$ הוא סכום של שלושה מספרים שכולם מתחלקים ב-41. ארבעים הצלחות ברצף לא הבטיחו כלום.

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

כל החמישה ראשוניים. ב-1640 כתב פרמה, במכתב למתמטיקאי ברנאר פרניקל, שכל המספרים מהצורה הזאת ראשוניים, ואף מנה ברשימה את שני הבאים בתור. הוא הודה שאין לו הוכחה מדויקת, אבל כתב שכבר פסל, בהוכחות שאין בהן ספק, כמות גדולה מאוד של מחלקים אפשריים. המספר הבא, $2^{32} + 1$, גדול מארבעה מיליארד, ובלי מחשב קשה מאוד לבדוק אותו. כמאה שנה אחרי פרמה מצא אוילר שהוא מתחלק ב-641:

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

והדוגמה השלישית היא הקיצונית ביותר. כל מספר שלם אפשר לפרק למכפלה של ראשוניים, ולספור כמה גורמים יש בפירוק, כולל חזרות. ב-$12 = 2 \cdot 2 \cdot 3$ יש שלושה גורמים, ב-$15 = 3 \cdot 5$ יש שניים, ובמספר ראשוני כמו 7 יש אחד. למספר 1 אין גורמים בכלל: אפס, וזה מספר זוגי. והנה טענה שנקראת «השערת פוליה», על שם ג’ורג’ פוליה, שכתב עליה ב-1919: מכל המספרים מ-1 ועד מספר כלשהו גדול מ-1, לפחות מחצית הם בעלי מספר אי-זוגי של גורמים. בדקו אותה עד עשרה, עד אלף, עד מיליון: היא נכונה. היא נכונה גם עד מאה מיליון, וגם עד תשע מאות מיליון. המספר הראשון שבו היא נכשלת הוא 906,150,257.

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

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

מה עושה חתך אחד

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

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

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

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

וזה הכלל כולו: חתך שחוצה $c$ חתכים קודמים מוסיף $c + 1$ חלקים. נסו אותו בהמחשה, חתך אחרי חתך, ונחשו כל פעם לפני שאתם לוחצים.

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

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

עם שש נקודות בפיזור כללי יש 15 חתכים ו-15 נקודות מפגש, ולכן $1 + 15 + 15 = 31$. את שני המספרים האלה נספור עוד מעט. קודם, משהו חשוב יותר: מה בעצם עשינו כאן.

הדומינו

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

הטיעון עשה שני דברים. הוא בדק מקרה אחד, את ההתחלה: עוגה בלי חתכים היא חלק אחד, ואכן $1 + 0 + 0 = 1$. והוא הראה משהו על המעבר ממקרה למקרה: אם הנוסחה נכונה אחרי שציירנו חתכים כלשהם, היא נשארת נכונה גם אחרי החתך הבא. כי החתך הבא מוסיף בדיוק $c + 1$ חלקים, ובאותו רגע הוא מוסיף גם חתך אחד ו-$c$ נקודות מפגש לשני המונים שבנוסחה. שני האגפים גדלים באותו שיעור.

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

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

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

ועכשיו אפשר לראות בדיוק מה היה חסר ב-1, 2, 4, 8, 16. בדקנו חמש אבנים, וכולן נפלו. אבל אף אחד לא הראה שכל אבן מפילה את הבאה. וכשבאמת ניסינו את השישית, היא נשארה עומדת. בדיקה של אבנים, אחת אחרי השנייה, לא תחליף את הצעד לעולם: גם אחרי מאה מיליון אבנים שנפלו, אולי דווקא האבן הבאה היא זו שעומדת. זה בדיוק מה שקרה להשערת פוליה.

כמה חתכים, וכמה נקודות מפגש

נשארו שני מספרים לספור, ושניהם שאלות של בחירה.

כמה חתכים? חתך אחד לכל זוג נקודות. עם שש נקודות, מכל נקודה יוצאים חמישה חתכים, לחמש הנקודות האחרות, כלומר $6 \cdot 5 = 30$. אבל כך ספרנו כל חתך פעמיים, פעם מכל אחד משני הקצוות שלו, ולכן יש $30 / 2 = 15$ חתכים. באופן כללי, עם $n$ נקודות יש $\frac{n(n-1)}{2}$ חתכים. זו גם התשובה לשאלה הישנה, כמה לחיצות ידיים יש כשכל אחד בחדר לוחץ יד לכל אחד אחר.

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

וכמה דרכים יש? נבחר את הנקודות אחת אחרי השנייה: את הראשונה אפשר לבחור ב-$n$ דרכים, את השנייה ב-$n - 1$, את השלישית ב-$n - 2$, ואת הרביעית ב-$n - 3$. אבל כך בחרנו את אותה רביעייה בכמה סדרים שונים: כל אחת מהארבע יכולה להיות הראשונה, כל אחת משלוש הנותרות השנייה, וכן הלאה. יש $4 \cdot 3 \cdot 2 \cdot 1 = 24$ סדרים כאלה, ולכן מספר הרביעיות הוא

עם שש נקודות: $\frac{6 \cdot 5 \cdot 4 \cdot 3}{24} = \frac{360}{24} = 15$.

למספר הדרכים לבחור $k$ דברים מתוך $n$ יש סימון משלו, $\binom{n}{k}$, וקוראים לו מקדם בינומי. בסימון הזה מספר החתכים הוא $\binom{n}{2}$, מספר נקודות המפגש הוא $\binom{n}{4}$, ומספר החלקים הוא

ועכשיו אפשר לחשב כמה שרוצים:

ומה עם מאה נקודות? $1 + 4950 + 3921225 = 3926176$: קצת פחות מארבעה מיליון חלקים, כשההכפלה הייתה נותנת מספר בן שלושים ספרות. זה ההבדל בין שני סוגי הגידול. $\binom{n}{4}$ גדל בערך כמו $n$ בחזקת ארבע, כלומר כמו פולינום, ואילו $2^{n-1}$ מכפיל את עצמו בכל צעד, וגידול כזה, מעריכי, משאיר כל פולינום מאחור.

למה ההכפלה החזיקה בדיוק חמש פעמים

יש לנו נוסחה, ויש לנו הוכחה. אבל נשארה תעלומה: למה בכלל 1, 2, 4, 8, 16? פולינום ממעלה 4 שנותן במקרה חזקות של 2 חמש פעמים ברצף נשמע כמו צירוף מקרים חשוד. התשובה עוברת דרך אחד האובייקטים היפים במתמטיקה.

משולש פסקל נבנה כך. בשורה העליונה, שנקרא לה שורה 0, יש רק 1. כל שורה מתחילה ונגמרת ב-1, וכל מספר אחר בה הוא סכום שני המספרים שמעליו, משמאל ומימין:

המספרים במשולש הם בדיוק המקדמים הבינומיים: המספר ה-$k$ בשורה $n$, כשסופרים מ-0, הוא $\binom{n}{k}$. למה? נניח שבוחרים $k$ נקודות מתוך $n$, ואחת מ-$n$ הנקודות צבועה באדום. יש בחירות שהנקודה האדומה בהן, ואז צריך לבחור עוד $k - 1$ נקודות מתוך $n - 1$ האחרות. ויש בחירות שהיא לא בהן, ואז בוחרים את כל $k$ הנקודות מתוך $n - 1$ האחרות. לכן

וזה בדיוק «סכום שני המספרים שמעליו».

שני דברים על המשולש הזה פותרים את התעלומה. הראשון: סכום כל שורה הוא חזקה של 2. בשורה 0 הסכום הוא 1, בשורה 1 הוא 2, בשורה 2 הוא 4, ובשורה 5 הוא 32. הסיבה: כל מספר בשורה נכנס לשני מספרים בשורה שמתחתיו, ולכן כל שורה מסתכמת בפי שניים מקודמתה.

השני: אפשר לפרק את נוסחת החלקים לפי אותו כלל. $1 = \binom{n-1}{0}$, וגם $\binom{n}{2} = \binom{n-1}{1} + \binom{n-1}{2}$ ו-$\binom{n}{4} = \binom{n-1}{3} + \binom{n-1}{4}$. כלומר, מספר החלקים של עוגה עם $n$ נקודות הוא סכום חמשת המספרים הראשונים בשורה $n - 1$ של משולש פסקל:

ועכשיו התעלומה נפתרת מעצמה. כל עוד בשורה יש לכל היותר חמישה מספרים, «חמשת הראשונים» הם השורה כולה, והסכום הוא חזקה של 2. בשורה $n - 1$ יש $n$ מספרים, ולכן זה נכון בדיוק עד $n = 5$. בשורה 5 יש כבר שישה מספרים, 1, 5, 10, 10, 5, 1, וחמשת הראשונים מסתכמים ב-31. ה-1 האחרון, שנשאר בחוץ, הוא ההפרש בין 31 ל-32.

הזיזו את מספר הנקודות קדימה, וראו כמה מהר מה שנשאר מחוץ לחלון גדל: 1 בשש נקודות, 7 בשבע, 29 בשמונה. בעשר נקודות מחוץ לחלון נשארים 256, בדיוק כמו בפנים. ההכפלה לא הייתה צירוף מקרים, והיא גם לא הייתה חוק. היא הייתה שלב, שבו השורות עוד קצרות מספיק.

ומה קרה לשש נקודות במרווחים שווים

נשארה הפתעה אחת פתוחה: שלושים במקום שלושים ואחת. ועכשיו, כשיש לנו הוכחה, אפשר לראות בדיוק איפה היא נשברת.

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

בתיבה של ההוכחה ההנחה הזאת כתובה במפורש: אין שלושה חתכים שעוברים באותה נקודה. היא לא הייתה קישוט. כששלושה חתכים או יותר נפגשים, הנוסחה צריכה תיקון: במקום להוסיף 1 על כל נקודת מפגש, מוסיפים את מספר החתכים שעוברים בה, פחות אחד. בנקודה רגילה עוברים שני חתכים, והיא תורמת 1, כמו קודם. במרכז המשושה עוברים שלושה חתכים, והוא תורם 2. שלושה זוגות של חתכים נפגשים שם, אבל בנקודה אחת, ולכן יש בשש נקודות במרווחים שווים רק 13 נקודות מפגש: 12 רגילות, ומרכז אחד. $1 + 15 + 12 + 2 = 30$.

זה גם מה שההמחשה הראשונה סופרת, בכל מצב: היא מחשבת מהגאומטריה את כל נקודות המפגש, ומוסיפה על כל אחת את מספר החתכים שעוברים בה, פחות אחד. ומכאן ש-31 הוא לא «מספר החלקים של שש נקודות», אלא המספר הגדול ביותר של חלקים ששש נקודות יכולות לתת. בכל פעם ששלושה חתכים או יותר נפגשים, הולכים חלקים לאיבוד. נסו שמונה נקודות במרווחים שווים: 88 במקום 99. במרכז נפגשים ארבעה חתכים, ובעוד שמונה נקודות נפגשים שלושה.

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

מה הלאה

והנה שאלה שנשארת פתוחה, בתוך העוגה עצמה: כמה חלקים יש כשהנקודות במרווחים שווים? ב-6 נקודות 30, ב-8 נקודות 88, ב-10 נקודות 230, וב-12 נקודות 456. במספר אי-זוגי של נקודות אין שאלה: שלושה חתכים אף פעם לא נפגשים שם באותה נקודה, את זה הוכיח הייניקן בשנות השישים, והנוסחה שלנו עובדת. במספר זוגי של נקודות חתכים נפגשים שלושה־שלושה, ארבעה־ארבעה ולפעמים יותר, בדפוסים שקשה לנחש. את מספר נקודות המפגש במצולע משוכלל חישבו במלואו רק ב-1998 ביורן פונן ומייקל רובינשטיין, והתשובה שלהם היא פולינום אחר לכל שארית של $n$ בחלוקה ב-2520. ובינתיים, נסו לספור בהמחשה הראשונה כמה נקודות מפגש מרובות יש בעשר נקודות במרווחים שווים, ואיך הן מסודרות.

ובחידות הבאות של «מדומינו לאינסוף» כל חידה עומדת בפני עצמה, וכל אחת מלמדת כלי אחר:

1. למה לא שלושים ושתיים? החידה הזאת: למה בדיקה של מקרים אינה הוכחה.
2. שרשרת של מנצחים: טורניר בלי תיקו, ואינדוקציה בצורתה הפשוטה ביותר.
3. מגפה על לוח שחמט: כמויות שאף פעם לא גדלות.
4. ביתרון מהפתק הראשון: ספירת קולות, ונוסחה שנשענת על שני מקרים קטנים.
5. הגפרור האחרון: משחקים שפותרים מהסוף להתחלה.
6. כמה שומרים צריך מוזיאון? כשצעד אחד אחורה לא מספיק.
7. ארבעה מספרים על ריבוע: הדוגמה הנגדית הקטנה ביותר.
8. בדיוק חצי: למה לפעמים קל יותר להוכיח טענה חזקה יותר.
9. עשרה מטרים של חבל: אינדוקציה שקופצת קדימה ואחורה.
10. מי יודע שיש לו בוץ על המצח? אינדוקציה שמתרחשת בדמיון של מישהו אחר.

הערה על המספרים וההוכחות

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

• ספירת החלקים בהמחשות מחושבת מהגאומטריה: הן מוצאות את כל נקודות המפגש, ומוסיפות על כל אחת את מספר החתכים שעוברים בה פחות אחד. לפני הפרסום הרצתי העתק של הקוד ב-Node. בכל מספר של נקודות מ-1 עד 12, ב-2,000 מיקומים אקראיים, הספירה שווה ל-$1 + \binom{n}{2} + \binom{n}{4}$. בנקודות במרווחים שווים היא נותנת 4, 8, 16, 30, 57, 88, 163, 230, 386 ו-456 ל-3 עד 12 נקודות, בהתאם לסדרה A007678 באנציקלופדיה המקוונת של סדרות שלמים, OEIS, ועוד $n$ החלקים שבין המצולע לשוליים. בחמש עוגות, ובהן שש נקודות בפיזור כללי ושש במרווחים שווים, הספירה הושוותה גם לספירה בלתי תלויה של אזורים בתמונה של 3,000 על 3,000 פיקסלים.
• הראשוניים נבדקים בחלוקה ניסיונית: מנסים לחלק ב-2 ובכל מספר אי-זוגי עד השורש. $2^{32} + 1$ קטן מספיק כדי שהמחשב יחזיק אותו בדיוק.
• ההוכחה שבתיבה היא הוכחה מלאה, בהנחה שאין שלושה חתכים שעוברים באותה נקודה. הספירה עם נקודות מפגש של יותר משני חתכים לא הוכחה כאן, אבל אותו טיעון, עם אותה הבחנה לגבי נקודות החצייה של חתך חדש, מוכיח גם אותה.
• העובדות ההיסטוריות נבדקו מול המקורות הראשונים ככל שאפשר: המכתב של פרמה לפרניקל (כתבי פרמה, כרך 2), המכתב של אוילר בזיכרונות האקדמיה בברלין לשנת 1772 (E461 בארכיון אוילר), העבודה של אוילר על מספרי פרמה (E26), המבוא של לז’נדר ל-Essai sur la théorie des nombres (1798), והמאמר של גאי, The Strong Law of Small Numbers (American Mathematical Monthly 95, 1988). מצב מספרי פרמה לקוח מהטבלה של וילפריד קלר, שעודכנה בדצמבר 2025. הנתונים על השערת פוליה לקוחים מהסקירה של בורוויין, פרגוסון ומוסינגהוף (2008), והחסם על השערת מרטנס מהמאמר של קים ונגוין (2024). הטענה על מצולעים משוכללים לקוחה מהמאמר של פונן ורובינשטיין (SIAM Journal on Discrete Mathematics 11, 1998), והסדרות A000127, A006561 ו-A007678 מ-OEIS.