20 באוקטובר, 2010

מה שהיה הוא שיהיה

כל מי שאוהב מתמטיקה מוצא את עצמו נאלץ להתגונן פה ושם מפני מבטים חקרניים ושפתיים רועדות ששואלות את השאלה המתבקשת: “למה”? וגם אני לא פטור מכך.

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

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


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

החידה היא פשוטה: בואו נסתכל על הלוח כשהוא מעורבב “טיפה” – החלפנו את המיקום של לוחית מס’ 14 ושל לוחית מס’ 15. כיצד אפשר לסדר את הלוח מחדש כשזה המצב ההתחלתי?

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

הכל טוב ויפה, אבל איך אפשר לומר בביטחון שכזה “אי אפשר לפתור את זה”? אולי המתמטיקאי סתם טיפש ולא יודע לגלות את הפתרון?

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

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

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

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

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

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

מה ההפרש הזה? ובכן, גזרנו את המשבצת הימנית התחתונה והשמאלית העליונה, ושתיהן היו לבנות. כלומר, לפני שהתחלנו לכסות את הלוח באבני דומינו ההפרש היה 2 (בהתחלה ההפרש היה אפס; בגזירה הורדנו 2 משבצות לבנות, ואפס משבצות שחורות). גם אחרי שנניח אבן דומינו אחת על הלוח ההפרש יהיה 2. גם אחרי שנניח 20 אבנים על הלוח הוא יהיה 2, וגם אחרי שנניח 31 אבני דומינו על הלוח ההפרש יהיה 2…

אבל רגע, יש בלוח הגזור 62 משבצות, אז אם הנחנו 31 אבני דומינו עליו, זה אומר שכיסינו את כולו (כי כל אבן דומינו מכסה 2 משבצות). כלומר, אין בכלל משבצות גלויות, ולכן ההפרש בין מספר המשבצות הלבנות הגלויות למספר המשבצות השחורות הגלויות הוא 0, וזה לא בסדר. זה סותר את התכונה שראינו שנשמרת. לכן לא ייתכן שנצליח לשים 31 אבני דומינו על הלוח – כלומר, אין סיכוי שנכסה אותו.

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

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

קצת יותר במדויק – המספר שאנחנו מסתכלים בזוגיות שלו הוא המספר שמורכב ממספר הפרות הסדר שבלוח, ועוד מספר השורה שבה נמצאת המשבצת הריקה. למשל, בלוח המקורי, המסודר, המספר הזה הוא 4: יש 0 הפרות סדר, והשורה שבה נמצאת המשבצת הריקה היא 4. לעומת זאת, בלוח שבו בוצעה ההחלפה בין 14 ו-15, יש הפרת סדר בודדת, ועדיין השורה שבה נמצאת המשבצת הריקה היא 4, ולכן המספר הוא 5. כלומר, בלוח המסודר המספר שלנו הוא זוגי, ובלוח המעורבב הוא אי זוגי. לכן כל מה שיש להראות הוא שזוגיות המספר הזה נשמרת על ידי הפעולות החוקיות שאפשר לבצע על הלוח.

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

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


זוהי גירסה מקוצרת של רשימה מהבלוג לא מדויק

תגובה אחת   (רסס)

  1. מאת בשמת_א:

    איזה יופי!

הוספת תגובה

(מומלץ להיכנס או )