אני חייב לכם תשובה

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

לפני כמה ימים שאלתי פה האם זה חדשני? ובכן, יש לי תשובה. התשובה היא “כן ולא”.

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

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

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

ראשית, הסידורים שמצאתי. אני אתן את הסידור הכי פשוט:
קוביה 1 – כל הפאות כחולות
קוביה 2 – כל הפאות ירוקות
קוביה 3 – כל הפאות אדומות
קוביה 4 – כל הפאות צהובות

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

מצד שני, תתקשו מאוד למצוא סידור של הקוביות המתוארות שאינו פתרון.

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

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

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

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

שחר