חידת ריצוף, או – כשאינדוקציה מתמטית הופכת למגניבה

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

החידה היא כזו: נתון לוח משבצות עם $latex 2^{n}\times2^{n}$ משבצות ($latex n$ הוא מספר טבעי חיובי). הנה דוגמה:

האם ניתן לרצף אותו עם צורות דמויות "ר" שגודלן 3 משבצות – אלו שרואים בתמונה הבאה?

ובכן, ברור שלא: לוח כזה מכיל $latex 2^{2n}$ משבצות ומספר זה לא יתחלק אף פעם ב-3, אבל כל שטח שמרוצף על ידי "ר"-ים שכאלו ודאי יכיל מספר משבצות שמתחלק ב-3, כי הוא רוצף על ידי כפולה שלמה של "ר"-ים.

אבל, מה אם נסיר משבצת אחת? לא קשה לראות ש-$latex 2^{2n}-1$ תמיד מתחלק ב-3. אז המניעה הברורה מוסרת. אם כן, אם אנו מסירים, למשל, את המשבצת השמאלית העליונה מהלוח, האם ניתן יהיה לרצף אותו? התשובה המפתיעה היא שכן, תמיד, בלי תלות בגודל הלוח. ואיך מוכיחים את זה? באינדוקציה.

בסיס האינדוקציה ברור – אם יש לנו לוח בגודל $latex 2\times2$ שהסרנו ממנו את המשבצת השמאלית העליונה, אז הלוח עצמו הוא צורת "ר" ולכן בוודאי ניתן לריצוף על ידי צורת "ר" אחת. אם כן, השלב הבא הוא להניח שאנו יודעים לרצף לוח בגודל $latex 2^{n}\times2^{n}$ שהוסרה ממנו המשבצת השמאלית העליונה ולנסות לרצף לוח בגודל $latex 2^{n+1}\times2^{n+1}$. הרעיון המתבקש (והנכון) הוא לחלק את הלוח לארבעה רבעים; כל רבע כזה יהיה מגודל $latex 2^{n}\times2^{n}$ ולכן ניתן יהיה להפעיל עליו את הנחת האינדוקציה… אה, רגע, לא. אפשר להפעיל את הנחת האינדוקציה רק על לוח שהוסרה ממנו המשבצת השמאלית העליונה. אז אנחנו אמנם יודעים לרצף את הלוח השמאלי העליון מבין הארבעה, אבל זהו, נתקענו.

כאן מגיעה ההברקה: במקום להוכיח באינדוקציה את הטענה שלנו, ננסה להוכיח באינדוקציה טענה חזקה יותר. כל מי שלמד מתמטיקה כנראה נתקל בזה מתישהו. לנסות ולהוכיח רק את הטענה ה"צרה" שלנו באינדוקציה זה לרוב קשה כי אנחנו חייבים להשתמש ב"עותק מוקטן" של אותה טענה בדיוק בהוכחה שלנו. לעומת זאת, אם נרחיב את הטענה שאנו מוכיחים יהיה לנו כלי חזק יותר להשתמש בו במהלך ההוכחה; והוכחת הבסיס לא בהכרח תהיה קשה יותר. אם כן, הטענה שנוכיח תהיה הטענה הבאה: אם נוריד מלוח $latex 2^{n}\times2^{n}$ משבצת כלשהי, עדיין יהיה ניתן לרצף אותו. זו טענה מתבקשת כי לא נראה שיש חשיבות מסויימת דווקא לפינה; ובכל זאת, ההבנה שצריך לחזק את הטענה שלנו אינה טריוויאלית.

הבסיס עדיין נותר קל – לוח של $latex 2\times2$, לא משנה מאיפה תעיפו ממנו משבצת, יהיה צורת "ר" ולכן ניתן לריצוף בידי צורות כאלו. לעומת זאת הוכחת הצעד היא כעת פשוטה ביותר, ויפהפיה לחלוטין. הרעיון הוא כזה: נחלק את הלוח לארבעה חלקים שווי גודל; באחד מהם חסרה משבצת, אז נרצף אותו (על פי הנחת האינדוקציה אפשר). עבור כל אחד משלושת הלוחות האחרים, נסיר מהם משבצת ואז נרצף אותם. מהיכן נסיר את המשבצות? אה, זה הפאנץ': בדיוק מאיזור האמצע, באופן כזה ששלוש המשבצות שהוסרו יוצרות בעצמן צורת "ר".

כל המוסיף גורע ולכן אסיים את הפוסט כאן ואתן לכם ליהנות בשקט מהפתרון.

31 תגובות בנושא “חידת ריצוף, או – כשאינדוקציה מתמטית הופכת למגניבה”

  1. חיזוק הטענה נראה מיותר – שכן אתה משתמש באינדוקציה רק בשביל הסרת המשבצות בצורה המסויימת – ואתה מסיר אותה תמיד מהפינה (ברור שלא משנה איזו פינה הסרת)…

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

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

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

  4. יופי של פוסט, והפעם אפילו הצלחתי להבין אותו (אני חושב).
    ו……. מותר לנסות לפתור את החידה?

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

  5. היה נדמה לי שהאתגר הוא לרצף ריבוע בו חסרה משבצת שרירותית (כמו "השלישית בשורה השנייה"). לא ניסיתי למצוא פיתרון חדש.

  6. לאורי: יש לי הוכחה נוספת, אבל היא פחות אלגנטית משל גדי.

    נתחיל ממשבצת הריקה – הריבוע 1X1
    נצמיד אותו לריש ר1 ונקבל ריבוע 2X2
    מארבעה רישים ר1 נייצר ריש ר2 (שניים צמודות ככפיות, ושניים בצדדים). נצמיד אותו לריבוע 2X2 ונקבל ריבוע 4X4
    מארבעה רישים ר2 נייצר ר4, נצמיד ל 4X4 – ריבוע 8X8.
    וכן הלאה

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

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

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

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

  11. תודה רבה!
    זנחתי זה מכבר את לימודי המתמטיקה בפתוחה (לחץ עבודה ותירוצים מעין אלה) והבלוג שלך הוא מנת המתמטיקה השבועית שלי.
    בהיר ומעניין.
    המשך כך ושוב תודה.

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

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

  14. חלופה אחרת לחיזוק הטענה היא בניית צורות 'ר' גדולות יותר. כלומר, מארבעה אריחים בצורת 'ר' של 3 משבצות ניתן לבנות צורת 'ר' של 12 משבצות (כלומר, של ארבעה ריבועי 2X2). מכאן מראים את הבנייה של צורת 'ר' מריבועים בגודל חזקה של 2, ומסיימים בזה (כמובן, יחד עם האינדוקציה הבסיסית). עם זאת, הטענה החזקה אכן יפה יותר.

  15. יריב – אהבתי. כשקראתי את התגובה של יוסי חשבתי שלזה הוא מתכוון. נראה לי שהתכוונת לכתוב "12 משבצות = *שלושה* ריבועי 2X2". אני מסכים שמדובר בגרסה אחרת של שימוש באינדוקציה – אלא שהפעם יותר קל לחשוב על זה מהקטן לגדול ולאו דווקא מהגדול לקטן – ובשבילי לפחות זה עושה את זה יותר קל להבנה. השיטה בפוסט נראית לי לטוב ולרע קצת כמו קסם – מההוכחות המתמטיות שאני קורא אותן, מבין שהן תקפות, ועדיין מרגיש כאילו מישהו עבד עלי כרגע. השיטה של יריב ויוסי יותר אינטואיטיבית. המחיר של זה הוא שאולי לא שמים לב לזה, אבל מתחבאת שם פעמיים אינדוקציה מתמטית – פעם אחת כדי להוכיח שיש ר בכל הגדלים הנחוצים, ופעם אחת להתבסס על זה כדי להוכיח את הטענה עצמה. אפשר להוסיף לשיטה הזו די בקלות התאמה שמאפשרת לשים את המשבצת החסרה בכל מקום אחר שאתה רוצה. אם תיקח את הרעיון כמו שיוסי הציג אותו – הרי אף אחד לא מכריח אותך לשים את כל הר'ים באותו כיוון

  16. הי כולם,
    ניתן למעשה להוכיח באינדוקציה כי עבור כל n>1 שאינו מתחלק ב-3
    ניתן לחלק את הצורה ל"רישים".
    אנו יודעים לחלק 3×2 5×5-1 4×4-1
    מכאן אפשר לבנות יופי של אינדוקציה.

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *