2009 OIM Problems/Problem 1

Problem

Let $n$ be a natural number greater than 2. Suppose that $n$ islands are located in a circle and that between each two neighboring islands there are two bridges, with the islands $x_1, x_2, \cdots , x_n$ in order of the clock hands. Starting on island $x_1$ , in how many ways can the $2n$ bridges be crossed by passing over each bridge exactly once?

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

WLOG first travel from $x_1$ to $x_2$ . If we reverse back to $x_1$ immediately, then we must continue in that direction until $x_2$ (since otherwise there is no way to return to those bridges). This pattern continues for all $x_i$ .

Notice that at every pair of bridges, we can always choose to take one or the other, and the remaining bridge will be forced upon us; thus there are $2^n$ ways to choose between each pair of bridges. Next, we can reverse at any $x_i$ for $i>1$ , and if we continue all the way to $x_1$ clockwise, we can either continue forwards or reverse. Thus there are $n+1$ cases if we initially head clockwise. This number is doubled since we can initially travel from $x_1$ to $x_n$ instead, so in total we have $2\cdot (n+1)\cdot2^n=\boxed{2^{n+1}(n+1)}$ choices.

~ eevee9406

Page

Toolbox

Search

2009 OIM Problems/Problem 1

Problem

Solution

See also