משחק ה-15
מתוך ויקיפדיה, האנציקלופדיה החופשית
משחק ה-15 הוא שמו של משחק המורכב מלוח בן 16 משבצות, שבתוכו 15 לוחיות הנושאות את המספרים 1-15 ואילו משבצת אחת נותרת ריקה. מטרת המשחק היא לסדר את כל הלוחיות על פי הסדר, כאשר הפעולה החוקית היחידה המותרת היא הזזת לוחית הסמוכה למשבצת הריקה לתוכה (ועל ידי כך יצירת משבצת ריקה חדשה).
המשחק זכה לפרסום גדול והפך לשגעון חולף בדומה לקובייה ההונגרית לקראת סוף המאה ה-19 לאחר שהוצע פרס לשחקן שיצליח לסדר את את הלוח כך שהלוחיות 14 ו-15 יחליפו את מקומן - משימה שניתן להוכיח מתמטית שאינה ניתנת לביצוע באמצעות פעולות חוקיות.
מקורות המשחק שנויים במחלוקת - החידונאי סם לויד טען כי הוא המציא את המשחק והביא לפופולריות שלו על ידי הצעת הפרס. טענה זו הייתה מקובלת למעלה מ-100 שנים. בשנת 2006 יצא לאור ספר הטוען כי לא היה ללויד שום קשר למשחק, והמצאתו מיוחסת לנויס פלמר צ'פמן, דוור ממדינת ניו יורק.
[עריכה] פאזל ה-15
משחק ה-15 לכשעצמו (הדורש סידור של הלוח לאחר שעורבב) אינו קשה לפתרון. בתחילת שנת 1880 הוצע פרס לא עבור פתרון המשחק, אלא עבור מי שיצליח לפתור את המשחק כאשר המצב התחילי זהה למצב הסופי פרט לכך שהלוחית מספר 14 והלוחית מספר 15 מחליפות את מקומן.
הנסיון לפתור את הפאזל עורר שגעון חולף שנמשך מספר חודשים עד שגווע ביולי 1880. התברר כי הפאזל המוצע כלל אינו ניתן לפתרון.
דרך אחת להיווכח בכך שהמשחק אינו ניתן לפתרון היא על ידי הצגת תכונה של הלוח שנשמרת בכל מהלך חוקי ומתקיימת בלוח המקורי אך לא מתקיימת בלוח שבו 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 נשמרת.
[עריכה] לקריאה נוספת
- Jerry Slocum , Dic Sonneveld, The 15 Puzzle book, Slocum Puzzle Foundation, 2006.
[עריכה] קישורים חיצוניים
- Impossible 15 Puzzle גרסת רשת של המשחק.
