חידת ה-15
חידת ה-15 (או משחק ה-15) היא חידה מכנית המורכבת מלוח בן 16 משבצות, שבתוכו 15 לוחיות הנושאות את המספרים 1-15 ומשבצת אחת נותרת ריקה. לפתרון החידה יש לצאת ממצב שבו הלוחיות מעורבבות על הלוח, לסדר אותן לפי הסדר, כאשר הפעולה החוקית היחידה המותרת היא הזזת לוחית הסמוכה למשבצת הריקה לתוכה (ועל ידי כך יצירת משבצת ריקה חדשה).
החידה זכתה לפרסום גדול לקראת סוף המאה ה-19, לאחר שבשנת 1880 הוצע פרס למי שיצליח לסדר את הלוח כך שהלוחיות 14 ו-15 יחליפו את מקומן (משימה שניתן להוכיח מתמטית שאינה ניתנת לביצוע באמצעות פעולות חוקיות, כמוסבר בסעיף הבא). הניסיון לפתור את הפאזל עורר שגעון חולף שנמשך מספר חודשים עד שגווע ביולי 1880.
החידונאי סם לויד, שהביא לפופולריות העצומה של החידה באמצעות הצעת הפרס, טען כי הוא המציא את החידה. טענה זו הייתה מקובלת למעלה מ-100 שנים. בשנת 2006 יצא לאור ה- The 15 Puzzle book, שקבע כי את החידה המציא נויס פלמר צ'פמן, דוור ממדינת ניו יורק, כעשר שנים קודם לפרסומה בידי לויד.
אין פתרון לחידה
כאמור, ב-1880 הציע סם לויד פרס כספי גדול למי שפותר את החידה כאשר במצב ההתחלתי המשבצות 14 ו-15 החליפו את מקומן. סם לויד יכול היה להיות בטוח שהפרס לא ייגבה, מכיוון שלחידה זאת אין פתרון. נראה כאן שתי הוכחות לכך שאין לחידה פתרון, אחת מסתמכת על 'תכונה נשמרת' - כלומר תכונה של מצבים שנשמרת תחת מהלכים במשחק - אך המצב ההתחלתי והמצב הסופי אינם מקיימים אותה. לאחר מכן תוצג הוכחה שנייה, דומה לה במהות, המראה שמספר המהלכים לפתרון החידה צריך להיות גם זוגי וגם אי-זוגי, וכך להגיע לסתירה. שני הפתרונות מבוססים על עקרון הזוגיות, עיקרון יעיל מאד בפתרון חידות מתמטיות רבות.
הוכחה א': תכונה נשמרת
ההוכחה מתבססת על תכונה של הלוח שנשמרת בכל מהלך חוקי, שמתקיימת בלוח המקורי אך לא מתקיימת בלוח שבו 14 ו-15 החליפו את מקומן. מכיוון שמהלכים חוקיים אינם יכולים לשנות את התכונה, נובע מכך שלא ניתן להגיע בעזרת מהלכים חוקיים מהלוח המקורי אל הלוח המוחלף (או להפך).
אחת התכונות שניתן להציג מתבססת על המושג המתמטי של הפרות סדר: זוג המספרים x,y יוצר הפרת סדר אם x גדול מ-y בערכו, אבל הלוחית של x באה לפני הלוחית של y בתוך הלוח, כאשר הסדר הוא משמאל לימין ומלמעלה למטה. למשל, בלוח המקורי אין הפרות סדר כלל, ובלוח שבו 14 ו-15 החליפו את מקומם קיימת הפרת סדר אחת: 15 בא לפני 14.
לצורך נוחות יסומן מספר הפרות הסדר שיש בלוח, כשהוא מחובר עם מספר השורה שבה נמצאת המשבצת הריקה, בתור S. מתברר כי S הוא בעל זוגיות קבועה. כלומר, אם לפני ביצוע מהלך S היה זוגי, הוא יישאר זוגי גם לאחר מכן. מכיוון שלמצב המקורי מותאם מספר זוגי (כי יש 0 הפרות סדר והשורה שבה נמצאת המשבצת הריקה היא 4) ואילו למצב המוחלף מותאם מספר אי זוגי (כי יש הפרת סדר אחת, והשורה שבה נמצאת המשבצת הריקה היא עדיין 4, ולכן המספר הכולל הוא 5), לא ניתן לעבור בין שני המצבים באמצעות פעולות חוקיות.
כדי להיווכח כי S הוא אכן בעל זוגיות קבועה, יש לשים לב לכך שאם מתבצע מהלך חוקי של הזזת לוחית שמאלה או ימינה, מספר הפרות הסדר אינו משתנה וגם השורה שבה נמצאת המשבצת הריקה אינה משתנה. אם לעומת זאת לוחית מוזזת למעלה או למטה, השורה שבה נמצאת המשבצת הריקה משתנה ב-1, ואילו הלוחית שזזה מחליפה מקום עם 3 לוחיות אחרות, ולכן נרשמים 3 שינויים בכמות הפרות הסדר: אם הלוחית שהוזזה ואחת מ-3 הלוחיות האחרות גרמו קודם להפרת סדר, לאחר ההזזה הפרת הסדר נעלמת. אם קודם הן לא גרמו להפרת סדר, היא נוצרת בשל ההזזה. על כן השינוי בגודלו של S הוא או 0, או 2 או 4. בכל אחד מהמקרים הללו, הזוגיות של S נשמרת.
הוכחה ב': מספר המהלכים הדרושים לפתרון החידה
כדי להיווכח בכך, אפשר להשתמש בעקרון הזוגיות. נניח שניתן לפתור את החידה. נצבע את המשבצות בלוח בשחור ולבן, כמו לוח שחמט, ונביט על התנועה של המשבצת הריקה. בכל תור מזיזים לוחית לתוך המשבצת הריקה, ולכן אפשר לראות את התור כאילו המשבצת הריקה היא שזזה לתוך אחת מארבע המשבצות הסמוכות אליה. כשהיא זזה היא גם משנה את צבעה. לכן אם היא מתחילה ממשבצת שחורה, במהלך הבא היא תהיה על משבצת לבנה, מהלך אחרי על משבצת שחורה, וכך הלאה: אחרי מספר מהלכים אי זוגי היא תהיה על משבצת לבנה ואחרי מספר מהלכים זוגי היא תהיה על משבצת שחורה. מכיוון שבמצב הסופי וההתחלתי המשבצת הריקה באותו מקום, על אותו צבע, אזי מספר המהלכים שדרושים לפתרון הוא זוגי.
מצד שני ניתן להסתכל על המשחק כעל משחק של תמורות. נסתכל על המשבצת הריקה כאילו גם בה יש לוחית, ונקבל שכל מצב במשחק בעצם מהווה סידור של המספרים מ-1 עד 16, וסידור כזה נקרא תמורה. המטרה במשחק היא להגיע מהתמורה:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
(הלוחית הריקה מסומנת פה במספר 16) לתמורה:
1,2,3,4,5,6,7,8,9,10,11,12,13,15,14,16
תמורות באופן כללי מתחלקות לתמורות זוגיות ולתמורות אי זוגיות. תמורות זוגיות הן תמורות שניתן להגיע אליהן מהמצב ההתחלתי על ידי מספר זוגי של החלפות של שני איברים, ותמורות אי-זוגיות הן כאלו שניתן להגיע אליהן מהמצב ההתחלתי על ידי מספר אי זוגי של החלפות של שני איברים. ישנו משפט הקובע שכל תמורה או שהיא זוגית או שהיא אי-זוגית - כלומר אם ניתן להגיע אליה על ידי מספר זוגי של החלפות של שני איברים, אי אפשר להגיע אליה על ידי מספר אי-זוגי של החלפות.
המצב הסופי מהווה תמורה אי-זוגית מכיוון שניתן להגיע אליו על ידי חילוף אחד (של המספרים 14 ו-15), ולכן הפתרון, שהוא סידרה של חילופים של שני איברים (רק שבפתרון אחד משני האיברים חייב להיות המשבצת הריקה, המספר 16) גם הוא חייב להיות בעל מספר אי-זוגי של חילופים. כאן הגענו לסתירה מכיוון שהוכחנו שהפתרון מכיל מספר זוגי של מהלכים. מכאן שהפתרון אינו קיים. לפיכך הפרס הכספי שהציע סם לויד על פתרון החידה מעולם לא נגבה.
עבור מצבים אפשריים - מצבים שעבורם ניתן לפתור את החידה, היא איננה קשה במיוחד.
אזכורים
בשירים
החידה מוזכרת בשירו של הרב מנחם פרומן: 'שברים'.
הוא כותב כך:
איזה קטעים, אל תשאל - זה לא רציני.
לקבוע אותם במסגרת אחת - לא רציני.
הם לא מִספרים, שמזיזים אותם בתוך לוח המשחק.
זה לא רציני לספור אותם, לא רציני.
במחשבים
במערכת ההפעלה: 'חלונות 7' יש אפשרות לשים על שולחן העבודה מספר חפיצים, ביניהם גם 'תצרף להרכבה'. בחפיץ זה ניתן לבחור אחת מאחת עשר תמונות להרכבה. אחת התמונות היא 'חידת ה-15'.
לקריאה נוספת
- Jerry Slocum, Dic Sonneveld, The 15 Puzzle book, Slocum Puzzle Foundation, 2006.
- סיימון סינג, המשפט האחרון של פרמה, עמ' 167-170
קישורים חיצוניים
- Impossible 15 Puzzle גרסת רשת של החידה.
- גדי אלכסנדרוביץ', מה שהיה הוא שיהיה, באתר "לא מדויק", שגיאה: זמן שגוי
- מלים לשיר: 'שברים' באתר: 'שירונט'.