+0  
 
0
989
4
avatar+198 

 

I am confused to even start the problem, and it looks so simple, so help, hints, or the solution would be nice!!

 Aug 21, 2018
edited by Max0815  Aug 24, 2018
 #1
avatar+397 
+3

We can use case work counting with this. We have three cases, if we start with \(1\) step, \(2\) steps, or \(3\) steps. You then can add a subcase of \(1\) step, \(2\) steps, or \(3\) steps to the beginning cases. You can keep doing this until all your cases add up to \(9\). This is a hassle, but it works. I don't reccommend this method, but I do not know any other methods, sorry. The end answer is \(149\). Haha I hope this helped! Hopefully you can find a better solution!

 

- Daisy

 Aug 22, 2018
 #2
avatar+118587 
+3

 

 

 

 

steps (in any order)

number of 

steps

Permutations  
all ones 1,1,1,1,1,1,1,1,1 9 1 1
ones and 2s 1,1,1,1,1,1,1,2 8 8 8
  1,1,1,1,1,2,2 7 7C2 21
  1,1,1,2,2,2 6 6C3 20
  1,2,2,2,2 5 5 5
ones and threes 1,1,1,1,1,1,3 7 7 7
  1,1,1,3,3 5 5C2 10
all threes 3,3,3 3 1 1
twos and threes 2,2,2,3 4 4 4
ones, twos and threes 3,2,1,1,2 5 5*4C2 30
  3,2,1,3 4 4*3 12
  3,2,1,1,1,1 6 6*5 30
TOTAL       149
 Aug 22, 2018
 #3
avatar+26364 
+4

When I run up a staircase, my stride can carry me up 1, 2, or 3 steps at a time. In how many ways can I run up a 9-step staircase (given that my last stride lands me on the 9th step)?

 

Let \(T_n\) be the number of ways to climb n stairs taking only 1 or 2 or 3 steps:

 

\(\begin{array}{|rcll|} \hline T_n &=& \mathcal{T}_{n+2} \qquad \mathcal{T} \text{ is the Tribonacci number } \\\\ && \text{case of n=9 steps}: \\\\ T_{9} &=& \mathcal{T}_{11} \qquad \\ && \mathcal{T}_0 = 0 \\ && \mathcal{T}_1 = 0 \\ && \mathcal{T}_2 = 1 \\ && \mathcal{T}_3 = 1 \\ && \mathcal{T}_4 = 2 \\ && \mathcal{T}_5 = 4 \\ && \mathcal{T}_6 = 7 \\ && \mathcal{T}_7 = 13\\ && \mathcal{T}_8 = 24\\ && \mathcal{T}_9 = 44\\ && \mathcal{T}_{10} = 81\\ && \mathcal{T}_{11} = 149\\ && \mathcal{T}_{12} = 274\\ && \ldots \\ T_{9} &=& 149 \\ \hline \end{array}\)

 

Source: http://oeis.org/search?q=1%2C2%2C4%2C7%2C13%2C24%2C&sort=&language=english&go=Search

"Tribonacci numbers: \(a(n) = a(n-1) + a(n-2) + a(n-3) \text{ with } a(0)=a(1)=0, a(2)=1\)."

"a(n) = number of compositions of n-2 with no part greater than 3.

Example: a(5)=4 because we have \(1+1+1 = 1+2 = 2+1 = 3\).

\(\ldots\)

\(a(n+1) = \dfrac{3*c*\left((1/3)*(a+b+1)\right)^n}{c^2-2*c+4}\) where
\(a=(19+3*\sqrt{33})^{1/3}\),
\(b=(19-3*\sqrt{33})^{1/3}\),
\(c=(586+102*\sqrt{33})^{1/3}\).
Round off to the nearest integer.
"

 

Example:

\(\begin{array}{|rcll|} \hline T_{9} = a(11)& =& \dfrac{3*c*\left((1/3)*(a+b+1)\right)^{10}}{c^2-2*c+4} \\ a=(19+3*\sqrt{33})^{1/3}& =& 3.30905647997\ldots \\ b=(19-3*\sqrt{33})^{1/3}& =& 1.20880378568\ldots \\ c=(586+102*\sqrt{33})^{1/3}& =& 10.5431194025\ldots \\ T_{9} & =& \frac{3*10.5431194025*\left((1/3)*(3.30905647997+1.20880378568+1)\right)^{10}}{10.5431194025^2-2*10.5431194025+4} \\ & =& \frac{14,014.7325577}{94.0711279297} \\ & =& 148.980169220 \\ \mathbf{T_{9}} & \mathbf{=}& \mathbf{149} \\ \hline \end{array} \)

 

laugh

 Aug 22, 2018
edited by heureka  Aug 22, 2018
edited by heureka  Aug 22, 2018
edited by heureka  Aug 22, 2018
edited by heureka  Aug 22, 2018
edited by heureka  Aug 22, 2018
 #4
avatar+198 
+2

Thank you to everyone who replied. You answers are appreciated!

 Aug 22, 2018

1 Online Users