אדום כחול צהוב
ה"למה של שפרנר"-משחק מתמטי
Your browser doesn't support Java applets, go to http://javatester.org/configuring.html
הוראות המשחק

גרסה לשני שחקנים

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

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


נוכיח עתה כי במשחק זה גורל השחקן תמיד להפסיד.

(מתוך מאמרו של ערן לונדון כפי שהופיע במאמרו "לא שש לססגוני" בגליון מספר 8 של אלף אפס.)

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

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

טענה:
מספר הקטעים ה"טובים" הוא אי-זוגי.

הוכחת הטענה:
נסרוק את הנקודות מימין לשמאל.

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

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

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

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

התוכלו להציע אסטרטגיות מנצחות?

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