Climbing the stairs

The number of days one can go without repeating the pattern is $377$, and, therefore, it is possible to have a different pattern each day of the year.

Before solving the problem, most students who submitted a solution found it useful to look at smaller cases.

Oliver from  Beechwood Park School, England,  Elz from Banstead Juniors and Jason from Commit Learning found it useful to write all the solutions for some cases:

There are $8$ ways to climb $5$ steps by taking at most two at the time, namely $11111$, $1112$, $1121$, $1211$, $2111$, $122$, $212$ and $221$, where $1$ represents the action of taking one step and $2$ the one of taking two steps.

Oliver found it interesting to look at the case where one can take at most three steps at a time, and he find almost all the solutions:

$11111$, $1112$, $1121$, $1211$, $2111$, $113$, $131$, $311$, $122$, $121$, $211$

Since $32$ and $23$ are also valid solutions, there are $13$ ways in total of climbing the $5$ stairs.

Hoi and Glory from Harrow International School Hong Kong, asked themselves an additional question: what if we can take up to five steps at a time.

In this case there are $16$ ways, namely $11111$, $1112$, $1121$, $1211$, $2111$, $113$, $131$, $311$, $14$, $41$,$122$, $121$, $211$, $31$, $23$, $5$. The fastest way for me to find all the possibilities was to draw a diagram and to write all the numbers in order. It was also very important to double check it.

Thomas from Hardwick Middle School,England, Michelle, Chihiro, Laura and Ken from  Shatin College,Hong Kong, Troll from British School Manila and Liam from Thomas Deacon Academy, UK, all managed to find, by inspecting smaller cases, a correlation between the answer and the Fibonacci's sequence.

To solve this problem I decided to start with a low number of stairs, like $2$. So I took $2$ and worked out how many solutions there were. I continue doing that and I noticed that the numbers of ways for a particular number of stairs was the sum of the numbers of ways to climb the stair for the previous two numbers of stairs. After repeating this process I ended up with these results:

$1$ step $=1$ way,

$2$ steps $=2$ ways,

$3$ steps $= 3$ ways,

$4$ steps $= 5$ ways,

$5$ steps $= 8$ ways, 

$6$ steps $=13$ ways

$7$ steps $= 21$ ways

$8$ steps $= 34$ ways

$9$ steps $= 55$ ways

$10$ steps $= 89$ ways

$11$ steps $= 144$ ways

$12$ steps $= 233$ ways

$13$ steps $=377$ ways

which form the Fibonacci's sequence. Therefore the answer is $337$ and we can choose one different way of climbing the $13$ steps for each day of the year.

Harry from Alleyn's School, UK, continued with a generalisation of this problem.

When $1$ or $2$ steps can be taken at a time, a staircase of $5$ stairs can be descended in $8$ different ways. I explored this and found that when I had a staircase with $n$ stairs, I could simply add the possibilities of the staircases with $n-1$ and $n-2$ numbers of stairs; a Fibonacci sequence. I knew I had found all of the combinations as I did it systematically. I worked

out that this happens because the possibilities of the previous two numbers of stairs can be written out, with a $1$ put on the end of all the possibilities of $n-1$ and a $2$ on the end of those of $n-2$.

When I added the possibility of taking $3$ steps in one go, I saw a pattern similar to a Fibonacci sequence, only with adding the previous $3$ numbers rather than two:

$$x_n = x_{n-1} + x_{n-2} + x_{n-3}$$

(where $x_n=$ the number of ways of climbing $n$ stairs). This happens due to the same reason;

a $1$ is put on the end of all $n-1$ possibilities, a $2$ on the end of $n-2$ and a $3$ on the end of $n-3$. I assume that with a $4$-step move, $$x_n=x_{n-1} + x_{n-2}

+ x_{n-3} + x_{n-4}$$, although I have not checked this.

With only $2$ and $3$ step moves allowed, I discovered a sequence I had to dwell on for quite a while: $1,1,1,2,2,3,4,5,7,9,12,16...$ After I had looked at this in many ways, I eventually discovered that when $n$ is the number of stairs in the staircase, the number of possibilities is equal to the sum of the number of possibilities in $n-2$ and $n-3$: one must skip the number

preceding n and then add the previous $2$ numbers. A $2$ is put on the end of the $n-2$ sequences and a $3$ on the end of $n-3$ sequences. $n-1$ is not included as a $1$ cannot be put on the end of anything; only moves of $2$ and $3$ steps are allowed.

Ali from Deira International School, UAE and Hadi from Haileybury Almaty, Kazakhstan, had a totally different approach:

You can take either $0,1,2,3,4,5$ or $6$ double steps each day. Let $s$ be the number of double steps you take. We will find the total ways you can take each number of double steps.

For $0$ double steps there is only $1$ way. This is all single steps. so for $s = 0$ there is $1$ way.

For $1$ double step we consider the double step to be a single object. Now there are $11$ $1$ step objects and $1$ $2$ step object $11\times 1 + 1\times 2 = 13$. This object can be placed in

$$ {12 \choose 1} = 12$$

ways so for $s = 1$ there are 12 ways (since ${n \choose r} = \frac{n!}{(n-r)!r!}$).

For $2$ double steps we again consider the double steps to be a single object and so this time there are $9$ $1$ step object so there are a total of $11$ objects. These two 2 step objects can be placed in $ {11 \choose 2} = 55$ ways.

Following on using the same argument we find there are $ {10 \choose 3} = 120$ ways for 3 double steps.

For 4 double steps: ${9 \choose 4} = 126$ ways.

For 5 double steps: ${8 \choose 5} = 56$ ways.

For 6 double steps: ${7 \choose 6} = 7$ ways.

We add them all up:

$$1+12+55+120+126+56+7 = 377$$

ways so it is possible to have a unique way for each day of the year as an year has atmost 366 days

Well done to you all for sending such a variety of solutions.