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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

כדי לא לסבך לעצמך יותר מדי את החיים, אתה כותב קטע קוד פשוט: לכל משבצת בלוח אתה מגריל מספר כלשהו עבורה (ומוודא שאף מספר לא יוגרל פעמיים), ואז שמח ומאושר אתה הולך לישון ומפיץ את המשחק עם מערכת ההפעלה. בינתיים בא אלייך העובד מקיוביקל ג' 3 ואומר שהוא ניסה לשחק קצת ולא הצליח לפתור את המשחק, אבל אתה מנפנף אותו, ובצדק; הרי הוא לא הצליח לפתור אפילו את משחק מס' 11,982 בפריסל!

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

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

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

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

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

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

29 תגובות על הפוסט “מה שהיה הוא שיהיה

  1. האם הוכחה ע"י חישוב נחשבת "הוכחה"?
    אם נניח יבדקו את כל המהלכים האפשריים אם מחליפים בין ריבוע 14 ל 15, וע"י כל הצעדים האפשריים הוא לא מצליח לפתור את המשחק, זה נחשב הוכחה מתמטית שהוא לא פתיר?

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

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

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

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

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

  5. התרגום של אינווריאנטה ל"שמורה" ממש יפה. יש לך מושג מה מקורו? לא נתקלתי בו אף פעם לפני זה.

    ואחלה בלוג, אגב.

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

  7. פינגבאק: המשחק נים « לא מדויק

  8. פינגבאק: חידת החיילים של קונווי « לא מדויק

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

  10. נניח שבשורה הראשונה יש, לפי הסדר, 2 4 6 5 ובשורה השניה התא הראשון ריק. אז כרגע 5 אחראי לשתי הפרות סדר שקשורות לשורה הזו (הוא בא לפני 4 ו-2). אם נוריד אותו למטה, הוא יהיה אחראי רק להפרת סדר אחת בשורה הזו (בא אחרי 6) ולכן מספר הפרות הסדר השתנה ב-1.

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

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

    2) כעת, אנחנו יכולים למלא את החור בלוחית חדשה שכתוב עליה 16. צעד חוקי הוא החלפת הלוחית שכתוב עליה 16 (איפב שהיא לא תהיה על הלוח) עם לוחית שכנה. זה אותו משחק, רק פחות נח לשחק (אבל יותר נח לחשוב). מצב הלוח בכל שלב הוא תמורה על 16 אברים. כל צעד הוא חילוף ולכן הופך את זוגיות התמורה. אחרי מספר זוגי של צעדים (לפי סעיף 1), התמורה המתקבלת חייבת להיות זוגית ולכן לא יכולה לתת את המצב שבו רק ה 14 וה 15 הפוכים.

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

  12. פינגבאק: איך אוילר עוזר לנו לבנות בתים ולטייל על גשרים « לא מדויק

  13. פינגבאק: מחשבת – נקמתן של השמורות « לא מדויק

  14. פינגבאק: מראה מראה שעל הקיר, למה את מבדילה בין ציר וציר? | לא מדויק

  15. מהי השמורה כאשר מספר המשבצות בלוח הינו אי זוגי? (נניח 3X3).
    במקרה כזה הזוגיות של הפרות הסדר משתנה עם כל החלפה נוספת. השמורה שציינת קיימת רק כל עוד מספר המשבצות בלוח (כולל המשבצת הריקה) זוגי.

    תודה, ובאמת כתיבה מעולה!

  16. ניסוח קצת יותר כללי לשמורה: מינוס 1 בחזקת המרחק של המשבצת הריקה מהמקום ה"נכון" שלה (מרחק גם בציר x וגם בציר y) כפול הזוגיות של התמורה שמתארת את כל הלוח, כאשר מתייחסים למשבצת הריקה בתור מספר חוקי לכשעצמו (נאמר 9 בלוח של 3×3).

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

  17. רז – עבור גודל אי-זוגי, אפשר לקחת פשוט את מספר הפרות הסדר מבלי להוסיף את מספר השורה של המשבצת הריקה.

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

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

  20. אני ממש נהנה מהאתר שלך! ואתה כותב דברים קשים בצורה כה בהירה,מדהים!
    1.סתם המלצה שלי – כדאי להשתמש במושג – מצב תחילי ומצב סופי, וכאשר רואים שהמצב התחילי לא יוכל להגיע למצב הסופי , אז הוכחת את הבעיה.
    2.מה שקשה לי בהסבר הוא- אתה אומר שהמצב התחילי הוא מספר זוגי של הפרות סדר, ובמצב הבעייתי המצב התחילי הוא מספר אי זוגי של הפרות סדר, ואם נעשה שינוי כלשהו, הוא לא ישפיע על הזוגיות, אך לשם כך מדוע אתה מונה שינוי בשורה?, היה מקום לחשב מחדש רק את כמות האי סדרים החדשה שנוצרה, ולהראות שהיא שמרה על זוגיות!?

  21. פינגבאק: חבורות של תמורות | לא מדויק

כתיבת תגובה

האימייל לא יוצג באתר.