Let $ABCDEF$ regular hexagon of side length $1$ and $O$ is its center. In addition to the sides of the hexagon, line segments from $O$ to the every vertex are drawn, making as total of $12$ unit segments. Find the number paths of length $2003$ along these segments that star at $O$ and terminate at $O$.
Problem
Source: 6-th Hong Kong Mathematical Olympiad 2003
Tags: symmetry, combinatorics unsolved, combinatorics
11.01.2007 18:40
Let $a_{n}$ be the number of ways to go from $O$ to any (fixed) other vertex in exactly $n$ steps (well-defined by symmetry), and $b_{n}$ be the number of ways to go from $O$ to $O$ in exactly $n$ steps; we are interested in calculating $b_{2003}$. It's clear that $a_{n+1}= 2a_{n}+b_{n}$ and that $b_{n+1}= 6a_{n}$, with initial values $a_{0}= 0$ and $b_{0}= 1$. Then $a_{n+1}= 2a_{n}+6a_{n-1}$ so $a_{n}= a w^{n}+bz^{n}$ where $w, z$ are roots of $x^{2}-2x-6 = 0$. Then $a+b = a_{0}= 0$ and $aw+bz = a_{1}= 1$, and everything beyond this point is going to be just a lot of arithmetic that I don't want to do
11.01.2007 18:51
JBL wrote: Let $a_{n}$ be the number of ways to go from $O$ to any (fixed) other vertex in exactly $n$ steps (well-defined by symmetry), and $b_{n}$ be the number of ways to go from $O$ to $O$ in exactly $n$ steps; we are interested in calculating $b_{2003}$. It's clear that $a_{n+1}= 2a_{n}+b_{n}$ and that $b_{n+1}= 6a_{n}$, with initial values $a_{0}= 0$ and $b_{0}= 1$. Then $a_{n+1}= 2a_{n}+6a_{n-1}$ so $a_{n}= a w^{n}+bz^{n}$ where $w, z$ are roots of $x^{2}-2x-6 = 0$. Then $a+b = a_{0}= 0$ and $aw+bz = a_{1}= 1$, and everything beyond this point is going to be just a lot of arithmetic that I don't want to do you are right, i think thanh you very much, your solution is very nice.
12.02.2020 11:49
JBL wrote: $a_{n+1}= 2a_{n}+b_{n}$ Can someone explain a bit how did this come ? (only a bit hint please)
14.02.2020 10:31
bump $^2$
14.02.2020 10:59