Difference between revisions of "2009 OIM Problems/Problem 1"
(Created page with "== Problem == Let <math>n</math> be a natural number greater than 2. Suppose that <math>n</math> islands are located in a circle and that between each two neighboring islands...") |
|||
| Line 5: | Line 5: | ||
== Solution == | == Solution == | ||
| − | {{ | + | WLOG first travel from <math>x_1</math> to <math>x_2</math>. If we reverse back to <math>x_1</math> immediately, then we must continue in that direction until <math>x_2</math> (since otherwise there is no way to return to those bridges). This pattern continues for all <math>x_i</math>. |
| + | |||
| + | 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 <math>2^n</math> ways to choose between each pair of bridges. Next, we can reverse at any <math>x_i</math> for <math>i>1</math>, and if we continue all the way to <math>x_1</math> clockwise, we can either continue forwards or reverse. Thus there are <math>n+1</math> cases if we initially head clockwise. This number is doubled since we can initially travel from <math>x_1</math> to <math>x_n</math> instead, so in total we have <math>2\cdot (n+1)\cdot2^n=\boxed{2^{n+1}(n+1)}</math> choices. | ||
| + | |||
| + | ~ [https://artofproblemsolving.com/wiki/index.php/User:Eevee9406 eevee9406] | ||
== See also == | == See also == | ||
[[OIM Problems and Solutions]] | [[OIM Problems and Solutions]] | ||
Latest revision as of 11:59, 20 March 2025
Problem
Let 
be a natural number greater than 2. Suppose that islands are located in a circle and that between each two neighboring islands there are two bridges, with the islands 
in order of the clock hands. Starting on island 
, in how many ways can the 
bridges be crossed by passing over each bridge exactly once?
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com
Solution
WLOG first travel from to 
. If we reverse back to immediately, then we must continue in that direction until (since otherwise there is no way to return to those bridges). This pattern continues for all 
.
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 
ways to choose between each pair of bridges. Next, we can reverse at any for 
, and if we continue all the way to clockwise, we can either continue forwards or reverse. Thus there are 
cases if we initially head clockwise. This number is doubled since we can initially travel from to 
instead, so in total we have 
choices.
