בתשובה לערן בילינסקי, 22/07/07 10:15
אלון, גדי, מישהו? 453017
אין איזה משפט שאומר שחייב להיות מנצח?
אלון, גדי, מישהו? 453023
לא. עד כמה שאני מבין, תנאי משפט צרמלו חלים גם על דמקה: משפט צרמלו [ויקיפדיה].
אלון, גדי, מישהו? 453324
למה כוונתך? במשחק בו תיקו הוא אופציה (עפ"י חוקי המשחק), ברור שלא ניתן להוכיח שמישהו חייב לנצח. המשחק יכול, למשל, להיות כזה בו תיקו הוא האפשרות היחידה. אולי לא הבנתי את השאלה.

המשפטים הבסיסיים אומרים: במשחק‏1 ללא תיקו, אחד השחקנים יכול לכפות נצחון; במשחק עם תיקו, אחד השחקנים יכול למנוע מהשני לנצח (כלומר, לזכות בעצמו, או לכפות תיקו).

1 עם כל מיני תנאים טכניים: סופי, מס' סופי של אפשרויות בכל מהלך, ללא הגרלות, עם אינפורמציה מלאה, אולי עוד ששכחתי, ואולי חלק מהללו מיותרים.
אלון, גדי, מישהו? 453334
המשפט הראשון שלך אינו ברור. האם כוונתך היא למשחק *כלשהו*? אם כן, אזי זה כמעט טריוויאלי. אלא שייתכנו משחקים ספציפיים [לא עולה לי משהו בראש אבל ניתן בקלות להמציא דוגמת-צעצוע אד-הוק] בהם תיקו הוא תוצאה חוקית, אבל פרישה של כל האפשרויות מניבה נצחון בלתי-נמנע (במשחק מושלם של שני הצדדים וכו') לאחד הצדדים.
אלון, גדי, מישהו? 453357
נצחון בלתי נמנע בהחלט עומד בתנאי ''למנוע מהצד השני לנצח''.
אלון, גדי, מישהו? 453381
אני התייחסתי רק ל-''במשחק בו תיקו הוא אופציה (עפ''י חוקי המשחק), ברור שלא ניתן להוכיח שמישהו חייב לנצח''.
אלון, גדי, מישהו? 453386
חלק מהיופי במתמטיקה הוא היכולת לומר על דברים כמעט טריוויאליים שהם באמת טריוויאליים ואין מלכודת שמסתתרת מאחוריהם (מלכודות כאלו קיימות הרבה יותר משנדמה במבט ראשון).
אלון, גדי, מישהו? 453397
זהו, שיש מלכודת.
המשפט "במשחק בו תיקו הוא אופציה (עפ"י חוקי המשחק), ברור שלא ניתן להוכיח שמישהו חייב‏1 לנצח" הוא שגוי.
___
1 חייב במובן זה שהנצחון תלוי רק בו, ולצד השני אין דרך להימנע מהפסד.
אלון, גדי, מישהו? 453402
התייחסתי ל''כמעט טריוויאלי'' מההודעה הקודמת שלו (על משחק ''כלשהו'').
אלון, גדי, מישהו? 453471
הנה משהו שעלה לי בראש: איקס-מיקס-דריקס כשהפותח מניח שתי אבנים במסע הראשון.
אלון, גדי, מישהו? 453508
אלא אם טעיתי בבדיקה הזריזה, לא דוגמא מוצלחת במיוחד.
אלון, גדי, מישהו? 453527
למה?

1. תיקו הוא תוצאה אפשרית.
2. לפותח יש איסטרטגיה שמבטיחה זכיה.
טעות שלי, פספסתי את ה-Y. אבל קרוב :) 453531
אלון, גדי, מישהו? 453474
הניסוח שלי היה מרושל - סליחה.

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

1 כפילות מרגיזה. איך מבדילים בין "ריצה" של המשחק לבין המשחק עצמו?
אלון, גדי, מישהו? 453478
ישנם משחקים בהם תיקו הינו תוצאה חוקית, שיש להם איסטרטגיה המבטיחה זכיה.
אלון, גדי, מישהו? 453480
אני מתאר לעצמי. השאלה היתה לגבי דמקה ושח.
אלון, גדי, מישהו? 453498
אם הבנתי נכון, לגבי דמקה הוכיחו (בדרך הקשה). לגבי שח אין הוכחה כזאת אם כי אינטואיטיבית זה נראה נכון.
אלון, גדי, מישהו? 453500
ואני הבנתי משהו אחר:
גם לדמקה וגם לשח יש הוכחת *קיום*. לדמקה יש היום גם הוכחת *בניה*.
אלון, גדי, מישהו? 453507
אם אפשר, אשמח לקבל לינק להוכחת הקיום לגבי שח.
אלון, גדי, מישהו? 453513
הוכחת הקיום, כפי שאמרו קודם, היא "משפט צרמלו". לרוע המזל, ההוכחה מראש שקיימת אסטרטגיית נצחון לשחור או ללבן, או שקיימת לשניהם אסטרטגיית תיקו; היא לא אומרת (וזו השאלה המעניינת) מה משלושת האפשרויות הללו מתקיים במקרה של שחמט.

משפט צרמלו [ויקיפדיה]
אלון, גדי, מישהו? 453520
המשפט מוכר לי [אגב, לכך כיוונתי כאשר אמרתי שזה "כמעט טריוויאלי", לא הייתה זו כוונתי לזלזל בהוכחה הראשונית]. בפרט, ראובן דיבר על נצחון/תיקו *ללבן*, ולגבי כך שאלתי. אני חושד שהוכחת קיום כזאת לא קיימת לפי שעה.

אבל תודה בכל אופן.
אלון, גדי, מישהו? 453521
כן, אולי אני מתבלבל בין לבן לבין ''צבע כלשהו''.
אלון, גדי, מישהו? 453528
לרגע חשבתי שאתה מתחכם עם ''שחור אינו צבע''. בשחמט הוא כן.
אלון, גדי, מישהו? 453545
זה לא עלה על דעתי.
אלון, גדי, מישהו? 453348
תודה, (גם לערן).
אלון, גדי, מישהו? 453618
1 סופי => מס' סופי של אפשרויות בכל מהלך, ולכן ברור שאחד מהם מיותר או שגוי.

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

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים