## Up the wooden hill

Posted by Chris on November 20, 2011 – 5:11 am

A cat is going up a stairway with thirteen steps. However, instead of walking up the stairs one step at a time, the cat jumps two, three or four steps at a time (though if necessary, it will just walk the last step). How many different ways can the cat go from the bottom to the top?

November 20th, 2011 at 12:16 pm

One: You can only go UP one way

November 20th, 2011 at 12:59 pm

I like it. But it’s not the answer I’m looking for.

November 20th, 2011 at 1:55 pm

34

November 20th, 2011 at 2:18 pm

Nope. There are more ways than that.

November 20th, 2011 at 2:31 pm

Six times 2, plus 1: 1 way

Five 2’s and a 3: 6 ways

Four 2’s and a 4, plus 1: 5 ways

Three 2’s and two 3’s, plus 1: 10 ways

Two 2’s and three 3’s: 10 ways

One 2, one 3 and two 4’s: 12 ways

(Gone past Carc already!)

Four 3’s, plus 1: 1 way

Three 4’s, plus 1: 1 way

Three 3’s and one 4: 4 ways

I’m sure to have miscalculated some of these, or missed other combinations, but my answer is a round 50.

November 20th, 2011 at 2:56 pm

Hi Wiz. You are close. Hint: if I’d made it many more steps, and/or added a 5 step move, you’d really be struggling. But there is a simple methodical way of doing it.

I have a dim memory of solving a similar problem on ToM a year or two back. But I think there were so many steps, that I found a formula to do it. I’m too lazy to bother this time.

November 20th, 2011 at 3:03 pm

wait, the cat also can go only one stair up?

“instead of walking up the stairs one at a time, the cat jumps two, three or four stairs up at each step” sounds different to me

i thought, it can only go 2, 3 or 4 stairs at once.

November 20th, 2011 at 3:19 pm

Hi Carc, that’s right, the cat takes 2, 3 or 4 steps at a time. The only exception is that the cat can walk the very last step. i.e. if the cat has managed to jump to step 12, then he’ll walk to step 13 (the upper floor). I’m also treating step 0 as the lower floor.

November 20th, 2011 at 3:39 pm

I haven’t tried it, but an auxillary problem could be that the cat is great at maths, and contrives to never land on the 12th step. How many ways does that give to get to the top?

November 20th, 2011 at 4:00 pm

Take away the number of times that the cat goes up one step at the end.

November 20th, 2011 at 4:03 pm

Hi WIz. You’re right. I’ve just been checking that problem. In consequence I realise that I’d goofed too. My answer to you was wrong – it’s a lot more than 50 ways to the top.

November 20th, 2011 at 4:11 pm

well, that’s pretty much the answer, i calculated(appart from that i made a mistake at my calculation):

in this case the cat has to make 3-step-jumps exactly one or three times(since it’s the only possibility to have 13 as an odd number).

when it’s 1 there are 10 steps left to be divided between 2’s and 4’s(i mistkenly calculatet with 8 first (13-3=8, oh yeah..)) so it’s 5 2’s, 3 2’s and 1 4 or 1 2 and 2 4’s.

with 3 3’s there are 4 steps left for either 2 2’s ore 1 4.

using the formula

(jumps)!/((2’s)!*(3’s)!*(4’s)!)

and adding up everything i get 52 possibilities.

November 20th, 2011 at 4:21 pm

Hi Carc. Until 20 minutes or so ago, I thought the answer was 52. But I had forgotten to take the step from 12 to 13 into account.

November 22nd, 2011 at 7:44 am

The #ways for the cat to get to the nth step is #ways to step n−2 plus #ways to get to step n−3 plus #ways to get to step n-4. The cat can get to step 1 in 0 ways, to step 2 in 1 way, to step 3 in 1 way and to step 4 in 2 ways. (Step 0 is the floor).

Step 0 1 2 3 4 5 6 7 8 9 10 11 12 13

#ways 1 0 1 1 2 2 4 5 8 11 17 24 36 52

However, for the special case of the last step, we can add the 36 ways to get to step 12, giving a total of 88 ways.

November 22nd, 2011 at 9:00 am

Correct! Let me improvise again, and post an additional question I haven´t thought of myself. Assume the cat wants to go upstairs to take a crap on our bed, an action we of course do not approve at all! However, we don´t have time to keep an eye on the cat, but we are in possession of a tiny bowl of delicious milk, which the cat cannot resist provided they both ¨meet¨ at some particular stair. If this happens the cat will simply stop, drink the milk, forget its task and go down the staircase to take a nap. Where do we have to place the bowl in order to give our bedsheets the best chance to survive (steps 0 and 13 are not allowed – the cat will not pay attention to the milk there)? Note that, we assume that all the 88 routes are equally likely, which is significantly different than assuming that the cat makes jumps of length 2, 3, and 4 with equal probability!

November 22nd, 2011 at 10:16 am

I’m probably being naive, but the 6th step looks like it will be the most probable step for the cat to land on. That is not my final answer (yet).

November 22nd, 2011 at 3:15 pm

Yes, Chris – you’ve been naive The problem is pretty easy though – pure computations. However, if somebody wants to try it for N stairs – be my guest I don’t have time to do it now, so I will work on it later only in case there are volunteers to help!

November 22nd, 2011 at 3:23 pm

Hi Slavy. I had a horrible idea that youd’d say that. I don’t fancy listing all 88 routes, yet alone whatever the n-step case would give. I haven’t really tried, but it doesn’t look too promising that there’s an “easy” way to do it.

I think I could program my way through it.

There are, at least several, possible interesting phenomena in the problem.

November 23rd, 2011 at 1:33 am

Hi Chris, you don´t need to do all that work – actually you´ve already done everything that is necessary. The answer is again intuitively clear – the milk should be at step 2. Apart from the mathematical formulas, the argument is that the smallest initial jump leads to the most options afterwards. To prove it – we just ¨concatenate¨. Denote by a(n) the n-th lower entry of your table. Then the number of different cat routes through the n-th step is exactly a(n)*(a(13-n)+a(12-n)), because each such route can be split into two independent paths – from the first to the n-th step, and from the n-th to the 13-th step. Direct computations from your table give rise to 41 paths through the 2-nd step, and smaller numbers for the other choices of n. I believe that such a conclusion could be made in general (for N steps) directly from the recursive formula we have for the a(n)s, but haven´t worked on that. Of course, another possible direction is to increase the number of milk bows we have So what are the optimal places of 2 different bowls? (unfortunately, if we allow very low positions this problem is trivial as well – obviously those are steps 2 and 3, but what if the bowls should be higher?) And what happens if we change the probability measure and assume that for each jump the cat has probability 1/3 to make any of the three types of jumps – 2,3, and 4 steps?

November 23rd, 2011 at 5:19 am

Hi Slavy. I was wondering if something like that might happen.

One thing that had struck me is that wherever the cat lands, except that it has less steps to go, it’s options are now the same as where it started from. So I was thinking that at worst, I’d have to make a set of tables similar to the original, but starting from scratch (pun intended) at each step.

November 23rd, 2011 at 9:59 am

On average, how many leaps will the cat need to take to make it to the top? Simply looking at the extreme cases (most and least efficient) we know it is less than 7 (2+2+2+2+2+2+1; 1 way), but more than 4 (4+4+4+1 = 4+4+3+2 = 4+4+2+3 = 4+3+4+2 = 4+3+2+4 = 4+2+4+3 = 4+2+3+4 = 3+4+4+2 = 3+4+2+4 = 3+2+4+4 = 2+4+4+3 = 2+4+3+4 = 2+3+4+4 = 4+3+3+3 = 3+4+3+3 = 3+3+4+3 = 3+3+3+4 ; 17 ways). We can also see that it will be much closer to 4 than 7. Well there are 18 of the 88 ways up the stairs. Wiz has done a lot of the work to come up with the rest in post #5.

I think I’m correct in assuming that (for example) 4+4+3+2 is the same as 4+4+3+2. Meaning you cannot swap the first and second 4’s and call them 2 different runs.

November 23rd, 2011 at 10:03 am

I guess I could have denoted that more clearly. I don’t know if subscripts are possible, so I will use 4a and 4b.

4a + 4b + 3 + 2

and

4b + 4a + 3 + 2

don’t exist since the cat will either take a 4-step jump and another, or not. Right?…

November 24th, 2011 at 9:19 am

Hi DP. If you write the paths as e.g. 4+3+4+2, then that is different to e.g. 4+4+3+2

—

If we consider paths from a given step, we can use my previous table, but just shift the role of step 13 to an earlier position. e.g. from step 6, the number of ways to step 13 is 4+5=9. The number of ways to step 6 is 4, so altogether step 6 is used in 4*9 = 36 paths.

Step 0 1 2 3 4 5 6 7 8 9 10 11 12 13

#ways to (1) 0 1 1 2 2 4 5 8 11 17 24 36 52+36=88

#ways from (88) - 41 28 19 13 9 6 4 3 2 1 1 (1)

#times used (88) - 41 28 38 26 36 30 32 33 34 24 36 (88)

The probability of using step 2 is 41/88. Simlilarly for the other steps.

My guess for step 6 wasn’t too good: the probability of using step 6 is 36/88.

In order of usage we get, 2, 4, 6 & 12, 10, 9, 8, 7, 3, 5,

That probability is on the understanding that each path is equally likely.

I still haven’t answered Slavy’s challenges

November 24th, 2011 at 7:59 pm

If step 2 has been blocked (by the milk), it’s simplest to start a new table.

Step 0 1 2 3 4 5 6 7 8 9 10 11 12 13

#ways to (1) 0 (0) 1 1 1 2 3 4 6 9 13 19 28+19=47

#ways from (47) - - 28 19 13 9 6 4 3 2 1 1 (1)

#times used (47) - - 28 19 13 18 18 16 18 18 13 19 (47)

So, no surprise, step 3 is the next one to block.

November 27th, 2011 at 6:01 am

Hi Chris,

I’ve been internetless for 4 days, so I need to catch up with the posts! Need to catch up with my work, as well, so I’ll most probably only answer direct questions until the next weekend (and provided I finally get internet connection at home)…

November 27th, 2011 at 6:52 am

Hi Slavy. I still haven’t answered all of your additional questions. But that’s only due to lack of time.

In the case of not using the lower steps (2,3,4) for the bowl of milk, I note that step 12 (or 6) is the next best choice for the first bowl. The hardest part isn’t the calculatons, it’s making the tables line up.

I’ve just noticed (in comment 23) that step 3 is used less than step 2.

November 28th, 2011 at 6:20 am

there are 88 posibilities

December 4th, 2011 at 5:14 pm

88 ways