פורטל:מתמטיקה/חידה/55

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

פתרון

ההוכחה היא באינדוקציה מתמטית:

בסיס האינדוקציה- עבור ריבוע בגודל 2X2 ברור כי ניתן לרצף את הלוח עם טרומינו L כך הפינה הימנית תישאר לא מרוצפת (על ידי L טרומינו אחד).

הנחת האינדוקציה- ניתן לרצף כל ריבוע בגודל $2^{n}\times 2^{n}$ עם טרומינו L, כך שהפינה הימנית תישאר לא מרוצפת.

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