לפניכם לוח בגודל 8 על 8 משבצות - 64 משבצות בסך הכול. מישהו הוציא מהלוח משבצת אחת - איזו שהיא - ונשארו 63.

ברשותכם ערימת אריחים בצורת האות L: כל אריח מכסה בדיוק שלוש משבצות - ריבוע 2 על 2 שחסרה בו פינה אחת. מותר לסובב את האריחים לכל כיוון.

מבחינת שטח בלבד הכול מסתדר: 63 חלקי 3 שווה בדיוק 21 אריחים.

השאלה: האם תמיד אפשר לרצף את הלוח החסר ב-21 אריחים כאלה, בלי חפיפות ובלי לחרוג מהלוח - ולא משנה איזו משבצת הוצאה?

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

רמז דק

לפני שתתקפו לוח 8 על 8 - פתרו את הגרסה הקטנה ביותר של הבעיה.

קחו לוח 2 על 2 שחסרה בו משבצת אחת. כמה משבצות נשארו, ואיזו צורה הן מרכיבות? התשובה לשאלה הזו היא כל הסוד.

רמז עבה

חלקו את לוח ה-8 על 8 לארבעה רבעים בגודל 4 על 4.

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

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

מה קיבלתם עכשיו? ארבעה לוחות 4 על 4, ובכל אחד מהם חסרה בדיוק משבצת אחת. הבעיה חזרה על עצמה - רק בגודל חצי.

פתרון

התשובה: כן, תמיד - ולא משנה איזו משבצת מתוך ה-64 הוצאה.

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

הצעד הבסיסי - לוח 2 על 2.

לוח 2 על 2 שחסרה בו משבצת אחת מורכב משלוש משבצות המסודרות בצורת L - וזה בדיוק אריח אחד. סיימנו.

צעד ההכללה.

נניח שאנחנו כבר יודעים לרצף כל לוח 4 על 4 שחסרה בו משבצת אחת. נראה שאז אנחנו יודעים לרצף גם כל לוח 8 על 8 חסר.

נחלק את הלוח לארבעה רבעים 4 על 4. המשבצת החסרה נמצאת ברבע אחד; נקרא לו הרבע החסר.

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

אחרי ההנחה הזו, בכל אחד מארבעת הרבעים חסרה בדיוק משבצת אחת: ברבע החסר - המשבצת המקורית, ובשלושת האחרים - המשבצת שכיסה האריח המרכזי.

לפי ההנחה, כל אחד מארבעת הרבעים האלה ניתן לריצוף. יחד עם האריח המרכזי - כיסינו את כל הלוח.

בדיקת ספירה.

לוח 4 על 4 חסר מכיל 15 משבצות, כלומר 5 אריחים. ארבעה רבעים כאלה הם 20 אריחים, ועוד האריח המרכזי האחד - סך הכול 21 אריחים, בדיוק כפי שחישבנו בהתחלה.

ובאותו אופן מפרקים גם כל רבע 4 על 4: אריח מרכזי אחד, ועוד ארבעה לוחות 2 על 2 שכל אחד מהם הוא אריח בודד. 1 ועוד 4 שווה 5. הכול מסתדר.

הנקודה המעניינת.

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

ולהשוואה: אילו היינו מנסים לרצף אותו לוח באריחי דומינו (שתי משבצות) - התשובה הייתה מיד שלילית, שהרי 63 אינו מתחלק ב-2. המספר 3 הוא שעושה את כל ההבדל.