Compute the number of ways to reach a point without overshooting puzzle

combinatoricslogicpuzzle

I am trying to solve the following puzzle:

An ant is trying to get from the origin (0, 0) to X = (13, 4) without overshooting, but he can only move up or right. He always alternates his step sizes between moving 1 unit in a single direction and moving 3 units in a single direction. Compute the number of ways the ant can start at the the origin and end at X.

First of all, it's not clear to me if the ant's first move is a move of three or a move of one. I believe we have to consider both cases. Note that it's impossible for the first move to be a three as the sum of the magnitudes of the moves has to equal 17 = 13 + 4 and
$$1 + 3 + 1 + 3 + 1 + 3 + 1 + 3 + 1 = 17$$
but
$$3 + 1 + 3 + 1 + 3+ 1 +3 + 1 = 16.$$

I have found the following solutions, but I don't know if I have found all of them:

  • URURURURR (0, 0) –> (0, 1) –> (3, 1) –> (3, 2) –> (6, 2) –> (6, 3) –> (9, 3) –> (9, 4) –> (12, 4) –> (13, 4)
  • RRURURURU (0, 0) –> (1, 0) –> (4, 0) –> (4, 1) –> (7, 1) –> (7, 2) –> (10, 2) –> (10, 3) –> (13, 3) –> (13, 4)

where U corresponds to an up move and R corresponds to a right move.

Is the answer two? Any thoughts or feedback is appreciated.

Best Answer

Good idea!

However in the step from finding $17 = 1 + 3 + 1 +\ldots$ to the solution you are missing many solutions.

Since you have to go exactly 4 units upwards, making two (or more) 3-unit steps upward is impossible. That leaves you with 2 options:

  1. One 3-unit step and one 1-unit step, or
  2. Four 1-unit steps.

Both of your examples belong to option 2. But since you make a 1-unit step 5 times, you have ${5 \choose 4} = 5$ ways to chose which four 1-unit steps go upwards. Alternatively, you can choose which 1-unit step goes to the right. In your solutions, that 1-unit step to right was last and first, resp., but they can also be any of ther other 3.

So in option 2, you 5 solutions.

For option 1, you choose one 1-unit step to go upwards of the available five 1-unit steps. You also choose one 3-unit step to go upwards of the available four 3-unit steps. Can you take it from here to complete the problem?

Related Question