Our Red Frog wants to get to the Orange Frog, but he can only jump right and down, but over multiple lilies if he chooses, although he can't stay still.
How many ways can he do it?
5
$\begingroup$
$\endgroup$
asked Apr 1 '16 at 17:19
-
$\begingroup$ yes - he can jump straight to the orange frog in one go if he wishes $\endgroup$ – JonMark Perry Apr 1 '16 at 17:24
-
$\begingroup$ Ah he can jump down and right at the same time then. I get it. $\endgroup$ – Raystafarian Apr 1 '16 at 17:25
-
$\begingroup$ Can you clarify - can the frog only jump down and right from the centre of the pad to the centre of another pad? Or can (for example) he walk to the left of a pad and jump down-right to the right side of a pad whose centre actually slightly to the left? $\endgroup$ – jhabbott Apr 2 '16 at 2:20
-
$\begingroup$ @jhabbott; view it as a 'square-saturated directed graph', where the 'square' operation takes u->v && v->w implies u->w, so this issue is removed $\endgroup$ – JonMark Perry Apr 2 '16 at 3:24
12
$\begingroup$
$\endgroup$
Each number represents the number of ways to get to that pad. Except for the first 1, each number is the sum of all the numbers above and to the left of it. The final answer is 74.
-
$\begingroup$ @Raystafarian There's no formula for an arbitrary arrangement like this, although certain arrangements (like grids) would have formulas. $\endgroup$ – f'' Apr 1 '16 at 17:54
1
$\begingroup$
$\endgroup$
I got a different answer, but it should be easy to point out what I'm missing
70
-
3
1
$\begingroup$
$\endgroup$
I completed mine similar to Raystafarian. I determined how many paths you can take to get to each pad. I started with A and found 1 path. The B, with another 1 path. THen when I look at something like D, I see it can be reached from A or B. Add those together, you have 2 paths to reach D. Continue down the chain until you find the final value for L.
My picture also includes the assumed jumps I can make. I assumed that jumps were not possible unless the middle is clearly down and right. So jumps C-D and B-H were not possible.
74 Total possibilities
The program does the calculations for me. So if I HAD allowed the the other jumps, I would have gotten these values.
CD allowed yields 82, BH allowed yields 79, CD and BH yields 87.
It matches f"s answer, but I wanted to include the alternates and have a spreadsheet to show that it can be reduced to spreadsheet with set equations. Give me any number of lily-pads and define the limits and this will solve it.
