Skippy the kangaroo

anonimnystefy · 2016-02-12 15:47:33

Yeah, basically what I did is partition the length into 1's and 2's, then find the number of ways to permute each one and to insert the one step backwards. (I.e., the same thing as you, phro, except I did not actually permute anything, just counted the permutations.)

Last edited by anonimnystefy (2016-02-12 15:48:51)

bobbym · 2016-02-12 15:49:22

The one step backwards is the one I did not adequately solve for.

Nehushtan · 2016-02-12 20:05:46

anna_gg wrote:

Why did you change your mind? I also got 167.

167 was for if Skippy could make 0 or 1 backward move. However, if Skippy has to make exactly 1 backward move, then 146. I wasn't sure what the wording of the puzzle meant.

phrontister wrote:

I like Nehushtan's logic, but he left something out in both answers and included something in the first that gave the correct answer there.

What did I leave out? My logic is as follows.

First consider what happens when Skippy didn't make a backward move. To do 7 metres, he can skip 1 metre and then do 6 metres, or skip 2 metres and then do 5 metres. To do 6 metres, he can skip 1 metre and then do 5 metres, or skip 2 metres and then do 4 metres. And so on. So to compute how many ways to do 7 metres without moving backwards, I first compute the number of ways to do 1 and 2 metres 2, then 3 metres, then 4 metres, and so on, up to 7 metres. It turns out to be a case Fibonacci adding: if f(n) is the number of ways to do n metres, then:

[list=*]
[*]

[/*]
[/list]

with f(1) = 1 and f(2) = 2.

Now for when Skippy can move backwards. He can do this when he's 1m, 2m, 3m, 4m, 5m or 6m from the starting point. Suppose he skips backwards at m metres from the starting point. He can do the first m metres in f(m) ways; after the backward skip, he has (8−m) metres left to do. Hence, if g(m) is the number of ways to get to the bowl skipping backwards at the m-metre mark, then

[list=*]
[*]

[/*]
[/list]

where m = 1, 2, 3, 4, 5 or 6.

Hence the answer to the puzzle is

[list=*]
[*]

[/*]
[/list]

This is assuming Skippy can choose not to skip backwards; if he has to make exactly one backward skip, then the answer is

[list=*]
[*]

[/*]
[/list]

Last edited by Nehushtan (2016-02-12 20:07:40)

Nehushtan · 2016-02-12 20:38:31

The calculations in detail.

[list=*]
[*]

[/*]
[/list]

Here f(n) is the number of ways Skippy can skip a distance of exactly n metres without moving backwards. If his initial skip is 1 metre, he has n−1 metres left to skip; if his starts by skipping 2 metres, he has n−2 metres left to do.

For backwardness:

[list=*]
[*]

[/*]
[/list]

g(m) is the number of ways to get to the bowl from 7 metres away, skipping back a metre at the m-metre mark from the starting point. The kangaroo can skip the first m metres in f(m) ways; after the backward skip, he will be 8−m metres from his bowl, and can get there in f(8−m) ways.

Hence the total number of ways to skip to his bowl from 7 metres away (assuming he has the option to decline skipping backwards) is

[list=*]
[*]

[/*]
[/list]

Last edited by Nehushtan (2016-02-12 20:49:08)

bobbym · 2016-02-12 21:29:07

Would either or both anonimnystefy and phrontister please provide me with the output in terms of {1,2,-1}, I am getting 146.

anonimnystefy · 2016-02-12 22:12:55

Okay, so I have discovered that my code for the optional backwards step is not correct, despite giving the correct result (it fails on lower numbers, etc.).

I /have/ written new code for this one, which is the same principle, basically...

bobbym · 2016-02-12 22:20:33

So we now agree on the answer...

phrontister · 2016-02-13 02:06:39

Hi Bobby;

I agree on Anna's and mine.

I haven't seen your code and I don't understand stefy's, but as both of you have the same answer as Nehushtan you're probably all getting there through similar logic, though maybe by different methods.

Nehushtan, in post #8, didn't use this option:

backward on 7th metre: 21 ways
[list=*]
[*]7m & 1m = 21 x 1 = 21[/*]
[/list]

However, I think it should be included, as shown by the following sequence (see also the last sequence - the 7th - in the Skippies images in post #11):
Skippy reaches the bowl without having taken a backwards jump along the way, and at this point is in breach of the rule that requires it (posts #2 & #3). However, Skippy, an Australian kangaroo, realises the omission and simply jumps backwards 1 metre and then forwards again 1 metre to return exactly to the edge of the bowl. There are 21 occurrences of that scenario...and 21 + 146 = 167.

Have you also omitted using that option?

Last edited by phrontister (2016-02-13 14:05:52)

phrontister · 2016-02-13 02:10:27

Hi Bobby,

bobbym wrote:

Would either or both anonimnystefy and phrontister please provide me with the output in terms of {1,2,-1}, I am getting 146.

I can't explain my method better than graphically, so here goes, in terms of {1,2,-1}:

Happy for someone to point out the flaw in my logic!

Last edited by phrontister (2017-02-26 22:10:24)

bobbym · 2016-02-13 04:31:57

Hi phrontister;

I did omit that option but since this kangaroo is native to your country and your answer agrees with what the OP wanted you would get the upvote.

phrontister · 2016-02-13 04:34:12

Thanks for your vote!

Off to bed...see you later.

bobbym · 2016-02-13 04:35:32

Have a good night.

phrontister · 2016-02-13 11:25:07

Hi Nehushtan;

Nehushtan wrote:

What did I leave out?

Please see post #33.

Maybe also the description of my method in post #34. It's not mathematical, but may help understand the logic I used...which basically was to list all permutations of jumps (including invalid ones, as I found it easier to account for the permutations this way), and to then deduct from that list all invalid permutations (those being the backwards first jumps and the backwards last jumps).

phrontister · 2016-02-13 12:39:33

Here's an image of my full list of permutations (including invalids), in which I've highlighted those that I think are valid but which others have left out (ie, those where Skippy reaches the bowl without having taken a backwards jump along the way - which is invalid - but from there still succeeds in reaching the bowl correctly).

Last edited by phrontister (2017-02-26 22:00:39)

anna_gg · 2016-02-13 20:44:50

A great job by all of you. Indeed the backwards jump is mandatory and Skippy cannot reach the bowl without having taken the back jump (i.e. after he reaches the 7 meters). I therefore start to believe that 146 is correct.

phrontister · 2016-02-13 23:54:28

Hi Anna;

Please let me know if these three jump sequences - expressed in {1,2,-1} terms - enable Skippy to reach the bowl:

A. 1,1,1,1,1,1,1,-1,1
B. 2,1,1,2,1,-1,1
C. 2,2,1,2,-1,1

Last edited by phrontister (2016-02-14 00:00:24)

anna_gg · 2016-02-14 00:37:11

No, because, in all 3 cases, the 7 meters are reached before he takes the backward jump.

phrontister wrote:

Hi Anna;
Please let me know if these three jump sequences - expressed in {1,2,-1} terms - enable Skippy to reach the bowl:
A. 1,1,1,1,1,1,1,-1,1
B. 2,1,1,2,1,-1,1
C. 2,2,1,2,-1,1

I think this is it, but without adding f(7) in the end; thus 146.

Nehushtan wrote:

The calculations in detail.
[list=*]
[*]
[/*]
[/list]
Here f(n) is the number of ways Skippy can skip a distance of exactly n metres without moving backwards. If his initial skip is 1 metre, he has n−1 metres left to skip; if his starts by skipping 2 metres, he has n−2 metres left to do.
For backwardness:
[list=*]
[*]
[/*]
[/list]
g(m) is the number of ways to get to the bowl from 7 metres away, skipping back a metre at the m-metre mark from the starting point. The kangaroo can skip the first m metres in f(m) ways; after the backward skip, he will be 8−m metres from his bowl, and can get there in f(8−m) ways.
Hence the total number of ways to skip to his bowl from 7 metres away (assuming he has the option to decline skipping backwards) is
[list=*]
[*]
[/*]
[/list]

phrontister · 2016-02-14 03:51:26

anna_gg wrote:

No, because, in all 3 cases, the 7 meters are reached before he takes the backward jump.

Thanks for clearing that up, Anna.

I'd treated the last forward jump of a sequence that reached 7 metres but didn't contain a backwards jump as not having actually reached the bowl (since it was rendered invalid by the absence of a backwards jump), and that Skippy would be free to take a backwards jump from there, followed by a forward 1-metre jump to reach the bowl correctly.

There were 21 of those sequences, so my answer now is 167 - 21 = 146.

Sorry, everyone!

Last edited by phrontister (2016-02-14 11:27:25)

Math Is Fun Forum

#26 2016-02-12 15:47:33

Re: Skippy the kangaroo

#27 2016-02-12 15:49:22

Re: Skippy the kangaroo

#28 2016-02-12 20:05:46

Re: Skippy the kangaroo

#29 2016-02-12 20:38:31

Re: Skippy the kangaroo

#30 2016-02-12 21:29:07

Re: Skippy the kangaroo

#31 2016-02-12 22:12:55

Re: Skippy the kangaroo

#32 2016-02-12 22:20:33

Re: Skippy the kangaroo

#33 2016-02-13 02:06:39

Re: Skippy the kangaroo

#34 2016-02-13 02:10:27

Re: Skippy the kangaroo

#35 2016-02-13 04:31:57

Re: Skippy the kangaroo

#36 2016-02-13 04:34:12

Re: Skippy the kangaroo

#37 2016-02-13 04:35:32

Re: Skippy the kangaroo

#38 2016-02-13 11:25:07

Re: Skippy the kangaroo

#39 2016-02-13 12:39:33

Re: Skippy the kangaroo

#40 2016-02-13 20:44:50

Re: Skippy the kangaroo

#41 2016-02-13 23:54:28

Re: Skippy the kangaroo

#42 2016-02-14 00:37:11

Re: Skippy the kangaroo

#43 2016-02-14 03:51:26

Re: Skippy the kangaroo

Board footer