HMMT February

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

Let $R$ be the rectangle in the Cartesian plane with vertices at $(0,0)$ , $(2,0)$ , $(2,1)$ , and $(0,1)$ . $R$ can be divided into two unit squares, as shown; the resulting figure has seven edges.

Compute the number of ways to choose one or more of the seven edges such that the resulting figure is traceable without lifting a pencil. (Rotations and reflections are considered distinct.)

Solution

Solution:

We have two cases, depending on whether we choose the middle edge. If so, then either all the remaining edges are either to the left of or to the right of this edge, or there are edges on both sides, or neither; in the first two cases there are 6 ways each, in the third there are $16+1=17$ ways, and in the last there is 1 way. Meanwhile, if we do not choose the middle edge, then we have to choose a beginning and endpoint, plus the case where we have a loop, for a total of $6 \cdot 5+1=31$ cases. This gives a total of $6+6+17+1+31=61$ possible cases.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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