3
$\begingroup$

A nice How many ways to pick the fruit puzzle reminded me about a similar puzzle, with quite different solution.

Let's say Alice and Bob quarrelled and decided to split up their field. Now Alice can run her machine only in the upper part of the field and can never go below the main diagonal. See example on the picture. In how many ways could she make the one trip from the top-left square to her home?

enter image description here

In other words, what is the number of paths on NxN grid, which go strictly to the right or down, start from the top-left, end to the bottom-right square and never cross the diagonal?

P.S. I'm replacing 20x20 by NxN in order to avoid numerical solutions, which are quite straight forward of course.

Improve this question
$\endgroup$
2
  • $\begingroup$ This puzzle is really awesome. I originally heard a slightly different version with a slightly different story: In an election where Alice receives $a$ votes and Bob receives $b$ votes($a > b$), what is the probability, as the votes are counted, that Alice is always strictly ahead? $\endgroup$
    – Tyler Seacrest
    Apr 6, 2016 at 21:17
  • $\begingroup$ @TylerSeacrest, originally I met it in a formulation of a queue in a shop. Shop have no money, men buy something for 50c each, half of them have 1$ bill and half - 2 quarters. The question is probability that all men will get change. The puzzle was really fun to solve by combining men in groups of size N+1. $\endgroup$
    – klm123
    Apr 6, 2016 at 21:30

2 Answers 2

Reset to default
7
$\begingroup$

This is a classic appearance of the Catalan numbers. The answer on an $n$ by $n$ grid is $C_{n-1}=\frac{1}{n}{2n-2\choose n-1}$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is a pity that you posted this before somebody, who knows nothing about Catalan numbers, would find a solution. But still this is eligible answer and I accept it. The interesting question here is why coefficient is 1/n exactly and how to see quickly that diagonal limitation lowers the combinations by factor of n. $\endgroup$
    – klm123
    Apr 6, 2016 at 18:08
2
$\begingroup$

This is an easier puzzle with a much simpler solution. You can see the answer by looking at how many ways you can get into a square:

From the top left square, you can only get there with 1 path, and you can only get to the place just right of it with one path.

\11.................
 \..................
  \.................
   \................
    \...............
     \..............
      \.............
       \............
        \...........
         \..........
          \.........
           \........
            \.......
             \......
              \.....
               \....
                \...
                 \..
                  \.
                   \

(where each number represents the number of ways to get to that square)

From any square (eg. F4), the number of ways you can get to it is the sum of the squares above (F3) and to the left (E4), because either of them can represent a path to the square (F4). Here are all of the sums (< 9) in their positions in the grid. 

\11111111111111111111
 \123456789..........
  \259...............
   \5................
    \................
     \...............
      \..............
       \.............
        \............
         \...........
          \..........
           \.........
            \........
             \.......
              \......
               \.....
                \....
                 \...
                  \..
                   \.

Using this algorithm (and excel), I found the final number of paths to be:

1767263190

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry, your result is correct of course, but the process of achieving it is not what is the puzzle about at all. I fixed this flow by asking for a general formula for NxN sized grid. $\endgroup$
    – klm123
    Apr 6, 2016 at 17:24
  • $\begingroup$ @klm123 Ah, ok. I was a little surprised when I saw this, precisely because this algorithm makes it so much easier than the original problem. $\endgroup$
    – Lacklub
    Apr 6, 2016 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.