חידת חמשת החדרים
חידת חמשת החדרים היא חידה קלאסית ופופולרית. בחידה ישנו מלבן המחולק לחמישה חדרים. מטרת הפותר היא ליצור מסלול העובר פעם אחת בכל קיר.
פתרון
[עריכת קוד מקור | עריכה]
כמו בחידת הגשרים של קניגסברג, החידה יכולה להיות מוצגת כגרף שבו כל חדר (כולל השטח שמחוץ למלבן) מסומן על ידי קודקוד ושני קודקודים מחוברים בקו אם יש להם קיר משותף. כיוון שיש יותר משני קודקודים עם מספר אי זוגי של קצוות (בגרף הם מסומנים בכתום), המולטיגרף אינו מכיל מסלול אוילר, מה שאומר שהחידה לא פתירה.
אפשר לפתור את החידה על ידי שינוי הכללים. לדוגמה, אם מרשים מעבר ביותר מקיר אחד כל פעם (כלומר דרך פינות), מעבר רב פעמי בקירות או פתרון החידה בטורוס ולא במישור.
הוכחה לחוסר הפתרון
[עריכת קוד מקור | עריכה]אפילו ללא שימוש בתורת הגרפים לא קשה להוכיח שלחידה אין פתרון. ראשית צריך להבהיר את הכללים. החדרים וקו הפתרון צריכים להיות מצוירים על צד אחד של נייר שטוח. קו הפתרון חייב להיות רציף, אבל יכול להיות ישר או מכופף ויכול לחצות את עצמו (אבל לא בתוך קיר). קו הפתרון חייב לעבור דרך כל "קיר" בדיוק פעם אחת, כאשר "מעבר" פירושו חצייה מצד אחד של הקיר לצד השני, מחדר לחדר אחר או מחדר לאזור החיצוני. כלל זה בא למנוע מעבר בשני קירות בו זמנית - בפינה בה הם נפגשים - או מעבר לאורך הקיר וחזרה לאותו צד. ישנם 16 "קירות", שבעה מפרידים את החדרים זה מזה, ותשעה מפרידים את החדרים מהאזור החיצוני.
ההוכחה היא הוכחה בדרך השלילה. כלומר, אנו מניחים שיש פתרון, מוצאים את המאפיינים של כל הפתרונות, ואז מראים שמאפיינים אלה סותרים את הכללים. כך אנו מסיקים שטעינו ואין פתרון.
תארו לכם שיש "משקיף" בכל חדר. המשקיף יכול לראות את קו הפתרון רק כשהוא נמצא בחדר שלו. כשמציירים את קו הפתרון הוא יראה אותו נכנס ויוצא מהחדר שלו. בנוסף לכך הוא יכול לראות את הקו מתחיל או מסתיים בחדר שלו. אין משקיף באזור החיצוני כך שישנם 5 משקיפים.
למטה: כאשר הקירות עומדים על טורוס, ניתן לפתור את החידה (הקו המקווקו פירושו הליכה לצד השני של הטורוס).
ראשית, נתבונן במשקיפים הנמצאים בחדר השמאלי התחתון ובחדר הימני התחתון. לכל חדר יש ארבעה קירות. אם הקו מתחיל בחדר שבו המשקיף נמצא, המשקיף יראה את הקו נוצר ויוצא מהחדר. לאחר מכן הוא יראה את הקו נכנס ויוצא מהחדר, ולבסוף הוא יראה את הקו נכנס לחדר ומסתיים שם (לא נשארו לקו קירות לצאת דרכם). אם הקו לא מתחיל בחדר בו המשקיף נמצא המשקיף יראה את הקו נכנס ויוצא מהחדר פעמיים, כשהוא חוצה את כל הקירות. עד כאן אין שום בעיה.
כעת, נתבונן במשקיפים בשלושת החדרים האחרים. לכל חדר ישנם חמישה קירות. אם הקו מתחיל בחדר בו המשקיף נמצא, המשקיף יראה את הקו נוצר ויוצא מהחדר (קיר אחד), לאחר מכן הוא יראה את הקו נכנס ויוצא (שני קירות נוספים), ולבסוף הוא יראה את הקו נכנס ויוצא (שני הקירות האחרונים). אם הקו לא נוצר בחדר, המשקיף יראה את הקו נכנס ויוצא (שני קירות), לאחר מכן הוא יראה את הקו נכנס ויוצא שוב (שני קירות נוספים), ולבסוף הוא יראה את הקו נכנס ומסתיים (לא נשארו לקו עוד קירות לצאת בהם). כך שאנו רואים שבחדרים עם חמישה קירות הקו חייב להתחיל או להסתיים, אין אפשרות אחרת. הטיעונים שלנו לא טענו דבר על הקירות שאותם קו הפתרון עובר, הסדר שבו קו הפתרון חוצה את הקירות או הדרך שקו הפתרון עושה מחוץ לחדר, כך שהטענות שלנו תקפות לגבי כל הפתרונות האפשריים. לסיכום כדי לעבור בכל הקירות בחדרים עם חמישה קירות הקו חייב להתחיל או להסתיים באותו החדר.
אולם יש לנו שלושה חדרים עם חמישה קירות. לקו הפתרון יש התחלה אחת וסוף אחד כך שהוא יכול לעבור בכל חמשת הקירות רק בשני חדרים, ובחדר השלישי הוא יכול לעבור לכל היותר בארבעה קירות. לכן קו הפתרון לא מציית לכל הכללים (הוא לא מציית לכלל המחייב אותו לעבור בכל הקירות).