זיקיות בשלושה צבעים על אי בודד - האם כולן יוכלו אי פעם להפוך לצבע אחד?

שתי זיקיות ירוקות אוחזות בענפים בתוך צמחייה

צילום: MSDN.WhiteKnight, Wikimedia Commons (CC0)

על אי בודד חיות 45 זיקיות: 13 אדומות, 15 ירוקות ו-17 כחולות.

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

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

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

השאלה: האם קיימת סדרת מפגשים שבסופה כל 45 הזיקיות יהיו באותו צבע? ואם לא - איך אפשר להוכיח שזה בלתי אפשרי, כשמספר האפשרויות אינסופי?

+ - רמז דק Click to collapse

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

+ - רמז עבה Click to collapse

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

+ - פתרון Click to collapse

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

הצעד המכריע: לחפש שמורה

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

מה קורה בכל מפגש

נסמן ב-A, B, C את מספרי הזיקיות בשלושת הצבעים. מפגש בין A ל-B מוביל למצב (A-1, B-1, C+2).

עכשיו נסתכל על ההפרש A מינוס B: הוא ירד ב-1 ועלה ב-1 - כלומר לא השתנה כלל.

ומה עם ההפרש A מינוס C? הוא השתנה ב-(-1) פחות (+2), כלומר במינוס 3. וההפרש B מינוס C - גם הוא במינוס 3.

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

חישוב המצב ההתחלתי

13, 15, 17. השאריות בחלוקה ב-3 הן 1, 0 ו-2 בהתאמה - שלוש שאריות שונות זו מזו.

ההפרש בין האדומות לירוקות הוא מינוס 2, ששקול ל-1 מודולו 3. ההפרש בין הירוקות לכחולות הוא מינוס 2, גם הוא 1 מודולו 3. אף הפרש אינו מתחלק ב-3.

חישוב מצב היעד

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

המסקנה

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

ומתי כן אפשר?

התנאי שגילינו הוא הכרחי - ומסתבר שהוא גם מספיק: אם שניים מבין שלושת המספרים ההתחלתיים משאירים אותה שארית בחלוקה ב-3, אפשר להגיע לצבע אחיד. נסו למשל 12, 15, 18 - שם כל השאריות שוות ל-0, וסדרת מפגשים מתאימה אכן קיימת. די היה לשנות זיקית אחת בלבד בהרכב המקורי כדי שהתשובה תתהפך.

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