ההוכחה הארוכה ביותר בהיסטוריה! (או: איך פותרי SAT מתגברים על בעיות קומבינטוריות, אבל היי זה שם פחות מפוצץ)

לפני חודש וקצת הצליחה תוצאה מתמטית נחמדה להיכנס אל החדשות לא בשל הסיבות שבגללן היא טובה, אלא בעיקר אלו שבגללן היא בעייתית: ההוכחה שלה היא (לכאורה) בגודל מפלצתי של 200 טרה-בייט. כמה זה הרבה? נאמר, זה פי 40 יותר מידע מאשר היה בשרתי ויקיפדיה ב-2010, ויש עוד שלל המחשות. בקיצור, זה הרבה מאוד. הנתון הזה …

האם סדרת פיבונאצ'י מסתתרת באלפבית העברי?

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

על משחקים ומספרים (חלק ב': מספרים. וקצת משחקים)

בפוסט הקודם התחלתי לבנות קבוצה של מספרים שהמוטיבציה אליהם הגיעה איכשהו מתוך משחקים קומבינטוריים. כזכור, הבניה הייתה פשוטה להפליא: כל מספר מיוצג על ידי אובייקט מהצורה $latex \left\{ L|R\right\} $ כאשר $latex L,R$ הן קבוצות, וכלל הבניה שלנו הוא ש"מספר" הוא אובייקט כזה כך ש-$latex L,R$ הן שתיהן קבוצות של מספרים וכל איבר של $latex …

על משחקים ומספרים (חלק א': משחקים. וקצת מספרים)

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

אז מה הקשר בין דקדוקים חסרי הקשר ופונקציות יוצרות?

תכירו – מסלולי מוצקין. מסלול מוצקין מאורך $latex n$ הוא מסלול ב-$latex \mathbb{Z}^{2}$ שמתחיל ב-$latex \left(0,0\right)$ ומסתיים ב-$latex \left(n,0\right)$ ומורכב משלושה סוגים אפשריים של צעדים: ימינה, למעלה-ימינה ולמטה-ימינה. כלומר, אנחנו כרגע ב-$latex \left(x,y\right)$ אז אנחנו יכולים לעבור אל $latex \left(x+1,y+\delta\right)$ כאשר $latex \delta\in\left\{ -1,0,1\right\} $. והנה העלילה מסתבכת: אסור למסלול לרדת מתחת לציר $latex x$, …

נוסחת ההיפוך של מביוס

נוסחת ההיפוך הקלאסית נתחיל מדוגמה. ככה יהיה הרבה יותר קל להבין מה אני רוצה. בפוסט הקודם הזכרתי את פונקציית אוילר $latex \varphi\left(n\right)$ שלכל מספר טבעי מחזירה את מספר המספרים הקטנים ממנו שזרים לו. בנוסף לכל מעלותיה, היא מקיימת את התכונה היפה הבאה: $latex \sum_{d|n}\varphi\left(d\right)=n$. כלומר, כל מספר טבעי שווה לסכום הערכים של פונקציית אוילר כל …

עקרון ההכלה וההפרדה, ואז הכללה והפחדה

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

גבישים כמו-מחזוריים וריצופים כן-מחזוריים

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

משפט טורן והולדת תורת הגרפים האקסטרמלית

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

פונקציות יוצרות – והפעם ברצינות (חלק ב')

אני רוצה להמשיך לדבר על פונקציות יוצרות והדברים המגניבים שעושים איתן, ובפוסט הזה ללכת לכיוונים עוד יותר טכניים מהפוסט הקודם (כי ככה זה במתמטיקה – כשמגיעים לדברים מתוחכמים, זה גם נהיה יותר טכני). בפוסט הקודם ראינו כי אם $latex A,B$ הן מחלקות של אובייקטים עם פונקציות יוצרות $latex a\left(x\right),b\left(x\right)$ אז הפונקציה היוצרת של $latex A+B$ …

פונקציות יוצרות – והפעם ברצינות

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

משפט רמזי

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

חלוקות וההשערה של רמנוג'אן

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

אז מה לפיוצ'רמה ולתורת החבורות?

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

כל כך קשה לבחור…

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

משולש פסקל

אחד הדברים היפים במתמטיקה הוא האופן שבו אובייקטים שנראים תמימים בהתחלה מתגלים כבעלי תכונות רבות ומעניינות. במבט ראשון, קשה לחשוב שאוסף הפתרונות של משוואה מוזרה כמו $latex y^{2}=x^{3}+ax+b$ יתגלה כבעל מבנה עשיר ומעניין מאין כמוהו, אך אוספי פתרונות שכאלו (שמכונים "עקומים אליפטיים") הם אובייקט שנחקר בצורה אינטנסיבית במתמטיקה המודרנית, והתפרסמו בפרט בגלל הקשר שלהם לפתרון …

הבינום של ניוטון

הפוסט הקודם שלי עסק במבוא לקומבינטוריקה, ברמה שבתקווה גם תלמידי תיכון יוכלו להבין. אני רוצה להמשיך כעת באותה הרוח ולהציג תוצאה קומבינטורית פשוטה אך יפה, שכבר בשלב זה ניתן להבין, באמצעות הכלים שהצגתי בפוסט הקודם – הבינום של ניוטון. בשלב כלשהו בתיכון נלמדת הנוסחה הפשוטה הבאה: $latex \left(a+b\right)^{2}=a^{2}+2ab+b^{2}$. למה? ככה. לפעמים גם נלמדת נוסחה יותר …

מהי קומבינטוריקה?

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

בעיית וויל האנטינג

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

כלל ה-0-1 של גרפים – ההוכחה

בפעם הקודמת ניסחתי את כלל ה-0-1, ולכן עכשיו אגש להוכחה שלו בלי שהיות. הרעיון הבסיסי בהוכחה הוא פשוט מאוד, אבל גם מקסים: הבה ונתבונן בתורה $latex T$, שהפסוקים שלה הם בדיוק אותם פסוקים שמתארים תכונות $latex \mathcal{P}$ עם הסתברות 1. למשל, הפסוק $latex \exists v_{1},v_{2},v_{3}\left(E\left(v_{1},v_{2}\right)\wedge E\left(v_{2},v_{3}\right)\wedge E\left(v_{3},v_{1}\right)\right)$ שמתאר את "בגרף קיים משולש" שראינו בפוסט הקודם …