Maths Olympiad Prep

Library / /89 of 377

Combinatorics Difficulty 4.8 AIME Find the answer United States

Problem:
The L shape made by adjoining three congruent squares can be subdivided into four smaller L shapes.
Figure 1
Each of these can in turn be subdivided, and so forth. If we perform 2005 successive subdivisions, how many of the 420054^{2005} L's left at the end will be in the same orientation as the original one?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
42004+220044^{2004} + 2^{2004}

After nn successive subdivisions, let ana_{n} be the number of small L's in the same orientation as the original one; let bnb_{n} be the number of small L's that have this orientation rotated counterclockwise 9090^{\circ}; let cnc_{n} be the number of small L's that are rotated 180180^{\circ}; and let dnd_{n} be the number of small L's that are rotated 270270^{\circ}. 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,
(an+1,bn+1,cn+1,dn+1)=(dn+2an+bn, an+2bn+cn, bn+2cn+dn, cn+2dn+an)(a_{n+1}, b_{n+1}, c_{n+1}, d_{n+1}) = (d_{n} + 2a_{n} + b_{n},\ a_{n} + 2b_{n} + c_{n},\ b_{n} + 2c_{n} + d_{n},\ c_{n} + 2d_{n} + a_{n})
It is now straightforward to show by induction that
(an,bn,cn,dn)=(4n1+2n1, 4n1, 4n12n1, 4n1) (a_{n}, b_{n}, c_{n}, d_{n}) = (4^{n-1} + 2^{n-1},\ 4^{n-1},\ 4^{n-1} - 2^{n-1},\ 4^{n-1})
for each n1n \geq 1. In particular, our desired answer is a2005=42004+22004a_{2005} = 4^{2004} + 2^{2004}.

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.