הפנטגרמה והפיתגוראים

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

סדרות ביטי ומלכות שחמט

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

משפט המטריצה-עץ של קירכהוף

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

משפט רמזי

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

שדות סופיים – מי, מה, כמה ולמה

בפוסט הקודם הסברתי מהו שדה והראיתי דוגמאות לשדות סופיים פשוטים: השדות $latex \mathbb{Z}_{p}$ לכל ראשוני $latex p$ של השלמים מ-0 עד $latex p-1$ עם חיבור וכפל מודולו $latex p$ (הסברתי מדוע זה חייב להיות ראשוני). בפוסט הזה אני רוצה לשכנע … להמשיך לקרוא

משפט רייס – הגרסה המלאה

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

IP=PSPACE – ההוכחה (חלק ב')

בפוסט הקודם שעסק בהוכחה ש-$latex \mbox{IP}=\mbox{PSPACE}$ הראיתי מערכת הוכחה אינטראקטיבית עבור השפה $latex \overline{3\mbox{SAT}}$. זו הייתה הדוגמה הראשונה למערכת הוכחה "רצינית", כזו שמשתמשת בכל הכוח של האינטראקטיביות; במערכות האחרות שהראיתי תוך סיבוב או שניים המשחק נגמר, ואילו כאן ההוכחה הייתה … להמשיך לקרוא

IP=PSPACE – ההוכחה (חלק א')

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

משפט ברינגטון – ההוכחה

בפוסטים הקודמים הסברתי מה אומר משפט ברינגטון, וכעת אפשר להגיע לחלק היפה ביותר בכל העניין – ההוכחה שלו. האתגר הוא להראות שכל פונקציה שנמצאת ב-$latex \mbox{NC}^{1}$, כלומר ניתנת לחישוב על ידי מעגל בוליאני מגודל פולינומי ועומק לוגריתמי, ניתנת לחישוב על … להמשיך לקרוא

הפרדוקס של ראסל ומשפט קנטור

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

משפט לדנר, או – מפרקים לגורמים את NP

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

המלון של הילברט, או – מדוע יש גדלים שונים של אינסוף

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

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

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

כיצד אורקלים מנבאים שקשה להוכיח ש-P שונה מ-NP

בפוסט הקודם נפנפתי קצת ידיים על אחת מהסיבות הנפוצות לקושי שבהוכחה ש-$latex \mbox{P}\ne\mbox{NP}$; העובדה שאחד מרעיונות ההוכחה החזקים והיפים שבמתמטיקה ומדעי המחשב, הלכסון שגורם להפניה עצמית, מה שמככב במשפט אי השלמות של גדל ובהוכחת אי כריעותה של בעית העצירה – … להמשיך לקרוא

אז אולי רק הראשוניים בטור ההרמוני מתכנסים ל-137?

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

הגופים האפלטוניים, נוסחת אוילר לפאונים, וכדורגל

כשאומרים "נוסחת אוילר", לרוב מתכוונים לנוסחה $latex e^{\pi i}+1=0$, או לניסוח הכללי שלה, $latex e^{i\theta}=\cos\theta+i\sin\theta$. לעתים רחוקות יותר מדברים על הנוסחה $latex V-E+F=2$, וקצת חבל, כי זוהי נוסחה יפה כמעט באותה מידה – נוסחה שמצביעה על גישה שונה שנקט אוילר … להמשיך לקרוא

איך מוצאים את נוסחת פיבונאצ'י?

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

הוכחת אוילר לקיום אינסוף ראשוניים

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

משפט אי השלמות הראשון של גדל – איך (בערך) מוכיחים אותו?

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