Problem:
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 subdivisions, how many of the L's left at the end will be in the same orientation as the original one?
Solution
Solution:
After successive subdivisions, let be the number of small L's in the same orientation as the original one; let be the number of small L's that have this orientation rotated counterclockwise ; let be the number of small L's that are rotated ; and let be the number of small L's that are rotated . When an L is subdivided, it produces two smaller L's of the same orientation, one of each of the neighboring orientations, and none of the opposite orientation. Therefore,
It is now straightforward to show by induction that
for each . In particular, our desired answer is .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.