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

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

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

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

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

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

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

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

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

תכירו – מסלולי מוצקין. מסלול מוצקין מאורך $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 \varphi\left(n\right)$ שלכל מספר טבעי מחזירה את מספר המספרים הקטנים ממנו שזרים לו. בנוסף לכל מעלותיה, היא מקיימת את התכונה … להמשיך לקרוא

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

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

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

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

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

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

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

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

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

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

משפט רמזי

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

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

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

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

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

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

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

משולש פסקל

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

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

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

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

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

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

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

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

בפעם הקודמת ניסחתי את כלל ה-0-1, ולכן עכשיו אגש להוכחה שלו בלי שהיות. הרעיון הבסיסי בהוכחה הוא פשוט מאוד, אבל גם מקסים: הבה ונתבונן בתורה $latex T$, שהפסוקים שלה הם בדיוק אותם פסוקים שמתארים תכונות $latex \mathcal{P}$ עם הסתברות 1. … להמשיך לקרוא