HMMT 二月 2005 · 冲刺赛 · 第 31 题

HMMT February 2005 — Guts Round — Problem 31

[10] The L shape made by adjoining three congruent squares can be subdivided into four smaller L shapes. Each of these can in turn be subdivided, and so forth. If we perform 2005 successive 2005 subdivisions, how many of the 4 L ’s left at the end will be in the same orientation as the original one?

解析

The L shape made by adjoining three congruent squares can be subdivided into four smaller L shapes. Each of these can in turn be subdivided, and so forth. If we perform 2005 successive 2005 subdivisions, how many of the 4 L ’s left at the end will be in the same orientation as the original one? 2004 2004 Solution: 4 + 2 After n successive subdivisions, let a be the number of small L’s in the same orientation n as the original one; let b be the number of small L’s that have this orientation rotated n ◦ ◦ counterclockwise 90 ; let c be the number of small L’s that are rotated 180 ; and n ◦ let d be the number of small L’s that are rotated 270 . When an L is subdivided, n it produces two smaller L’s of the same orientation, one of each of the neighboring orientations, and none of the opposite orientation. Therefore, ( a , b , c , d ) = ( d + 2 a + b , a + 2 b + c , b + 2 c + d , c + 2 d + a ) . n +1 n +1 n +1 n +1 n n n n n n n n n n n n It is now straightforward to show by induction that n − 1 n − 1 n − 1 n − 1 n − 1 n − 1 ( a , b , c , d ) = (4 + 2 , 4 , 4 − 2 , 4 ) n n n n 2004 2004 for each n ≥ 1. In particular, our desired answer is a = 4 + 2 . 2005