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

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

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

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

פרדוקס ברס ומנהרות הכרמל

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

איך לחזות את מזג האוויר בלי להסתכל בשמיים? (משפט המינימקס)

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

משפט הנישואים היציבים

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

זוג או פרד (כן, עם ד’!)

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

בחר לך דיקטטור

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

מי שהיה נשוי שלוש נשים

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

צ’ומפ צ’ומפ

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

דילמת הבלונדינית האלטרואיסטית

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

נפלאות אי התבונה (חלק ד')

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

נפלאות אי התבונה (חלק ג')

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

נפלאות אי התבונה (חלק ב')

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

נפלאות אי התבונה (חלק א')

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