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

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

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

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

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

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

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

נניח שאנו בוחרים נקודה אקראית בריבוע, וסופרים בכמה צבעים היא צבועה. בסיכוי של 3/4 (או 75%) היא צבועה בכחול, ובנוסף בסיכוי של 3/4 (או 75%) היא צבועה באדום. לכן תוחלת מספר הצבעים שבהם צבועה הנקודה היא 3/4+3/4=1.5. נשים לב שמספר הצבעים שבהם צבועה הנקודה הוא תמיד מספר שלם, כי הרי אף נקודה לא צבועה ב-1/2 צבע, ואם הממוצע של מספרים שלמים הוא 1.5, אחד מהם חייב להיות לפחות 2. לכן יש לפחות נקודה אחת שצבועה בשני צבעים.

רוצים לנסות להשתמש בשיטה בעצמכם? נניח כי במקום 2 צבעים, יש 4 צבעים שונים שכל אחד מהם מכסה ¾ משטחו של הריבוע. איך נראה שקיימת לפחות נקודה אחת שצבועה בלפחות 3 צבעים שונים? מה יקרה אם נשתמש ביותר צבעים? ומה יקרה אם השטח של כל צבע יהיה קטן מ- 3/4?

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

קישורים:

[1] הספר של נוגה אלון ויואל ספנסר על השיטה ההסתברותית

[2] הספר של רובין הרטשורן בגיאומטריה אלגברית