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

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

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

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

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

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

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

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

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

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