חידת ה-15

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

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

החידונאי סם לויד, שהביא לפופולריות העצומה של החידה באמצעות הצעת הפרס, טען כי הוא המציא את החידה. טענה זו הייתה מקובלת למעלה מ-100 שנים. בשנת 2006 יצא לאור הספר: The 15 Puzzle book, שקבע כי את החידה המציא נויס פלמר צ'פמן, דוור ממדינת ניו יורק, כעשר שנים קודם לפרסומה בידי לויד.

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

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

מצד שני ניתן להסתכל על המשחק כעל משחק של תמורות. נסתכל על המשבצת הריקה כאילו גם בה יש לוחית, ונקבל שכל מצב במשחק בעצם מהווה סידור של המספרים מ-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

מדיה וקבצים בנושא חידת ה-15 בוויקישיתוף

• Impossible 15 Puzzle גרסת רשת של החידה.
• גדי אלכסנדרוביץ', מה שהיה הוא שיהיה, באתר "לא מדויק", 23 באפריל 2007
• מילים לשיר: 'שברים' באתר: 'שירונט'.
• הפריט מונגש לעיורים באתר: 'מילבת'.
• חידת ה-15, באתר אנציקלופדיה בריטניקה (באנגלית)
• חידת ה-15, באתר MathWorld (באנגלית)