Luke the cat

Luke the cat likes jumping on steps. One day, Luke the cat finds a bowl of its favourite food, salmon, in a bowl on top of a flight of 12 12 steps. However, Luke the cat is tired and hungry and can only jump up 1 1 or 2 2 steps at a time. How many ways are there for it to get to the bowl of salmon?


The answer is 233.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Luke Tan
Aug 23, 2014

Yay Im a cat~ Anyways to find the number of ways: Number of ways when there are 6 "2"s and 0 "1"s: 6!/6!=1 Number of ways when there are 5 "2"s and 2 "1"s: (5+2)!/(5!x2!)=21 Number of ways when there are 4 "2"s and 4 "1"s: (4+4)!/(4!x4!)=70 ............. Number of ways when there are 0 "2"s and 12 "1"s: 12!/12!=1 Therefore the total number of ways: 1+21+70+84+45+11+1=233

Nice recurrence involved with Fibonacci :D. I would like you latex your solutions, its very dificult to read

Sanjana Nedunchezian - 6 years, 8 months ago

fibonacci series lol

math man - 6 years, 9 months ago

12 STEPS (T = 2 STEPS, O = 1 STEP)

  1. 12O -> 1

  2. 1T+10O = (10+1)! / 10! 1! = 11

  3. 2T+8O = (2+8)!/2! 8! = 45

  4. 3T+6O = (3+6)!/ 3! 6! = 84

  5. 4T+ 4O = (4+4)!/ 4! 4! = 70

  6. 5T+2O = (5+2)!/ 5! 2! = 21

  7. 6T -> 1

TOTAL = 1+11+45+84+70+21 = 233

Sarath Chandra Gullapalli - 6 years, 8 months ago
Dieuler Oliveira
Nov 9, 2014

It's actually simple to calculate it by recurrence. If we call f ( n ) f(n) the number of ways the cat can get the bowl, and since there's just 2 2 different ways of it starts doing it, we have:

i) Either the cat jumps 1 1 step at a time, reaching the first step; and the cat has now f ( n 1 ) f(n-1) ways of getting the bowl.

ii) Or the cat jumps 2 2 steps at a time, reaching the second step; and the cat has now f ( n 2 ) f(n-2) ways of getting the bowl.

So we have: f ( n ) = f ( n 1 ) + f ( n 2 ) f(n)=f(n-1)+f(n-2)

We can easily calculate it by knowing that f ( 1 ) = 1 f(1)=1 (if there's just one step, then there's just one way to gettong the bowl: by jumping just 1 1 step) and f ( 2 ) = 2 f(2)=2 (if there's just two steps, then there's two ways to getting the bowl: either jumping 1 1 step at a time or jumping 2 2 steps at a time, reaching the bowl).

Therefore:

f ( 1 ) = 1 f(1)=1

f ( 2 ) = 2 f(2)=2

f ( 3 ) = 1 + 2 = 3 f(3)=1+2=3

f ( 4 ) = 2 + 3 = 5 f(4)=2+3=5

f ( 5 ) = 3 + 5 = 8 f(5)=3+5=8

f ( 6 ) = 5 + 8 = 13 f(6)=5+8=13

f ( 7 ) = 8 + 13 = 21 f(7)=8+13=21

f ( 8 ) = 13 + 21 = 34 f(8)=13+21=34

f ( 9 ) = 21 + 34 = 55 f(9)=21+34=55

f ( 10 ) = 34 + 55 = 89 f(10)=34+55=89

f ( 11 ) = 55 + 89 = 144 f(11)=55+89=144

f ( 12 ) = 89 + 144 = 233 f(12)=89+144=\boxed{233}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...