How many ways to pick the fruit

Question

Alice and Bob have a farm in the form of a $20 \times 20$ grid, each square in the grid containing the same amount of fruit. They both live in the lower-right square. Luckily for them, Alice is a brilliant inventor, and has crafted a machine that can collect all of the fruit in the square in which it's located instantly. Unluckily for them, this machine only has the technology to move right or down, so they have to do the harvest by painstakingly carrying it to the top-left square (the machine doesn't work while carried) and making a single pass collecting as much fruit as they can.

This means that most of the field will be left unharvested, but they're lazy farmers and don't really care about that.

Bob, wanting to stump Alice, then asked "What if we carried it to the top-left square twice instead? In how many ways could we make the two trips from the top-left square to our home such that we collect the maximum total amount of fruit?"

However, he was unsuccessful, as Alice quickly entered a few numbers on her (scientific) calculator and showed him the answer.

What is the answer to Bob's question and how did Alice reach it? In other words, what is the number of non-intersecting pairs of paths from the top-left square to the bottom-right square?

Note: Two ways are considered distinct if in at least one of the two passes Alice and Bob take a different path home.

Hint 1:

The condition "they don't meet in any point except for the endpoints" is a bit clumsy. Can we transform the problem into finding two paths that share no common points at all, even the endpoints?

Hint 2:

Bob asked Alice how she reached her answer. I didn't hear the whole explanation, but saw she drawing this picture in her notebook:

Answer 1

Answer:

(C(36,18)^2 - C(36,17)^2)*2 = (38!/19!/19!)^2/37/2 = 16882265852589060000

I will solve the task in the most simple formulation:

what is the number of non-intersecting pairs of paths from the top-left square to the bottom-right square?

A.

If we have field NxM and there would be one path then it has N+M-2 decision points whether to go "Right" or "Down", N-1 of these decisions must be "Right", so there are C(N+M-2,N-1) possible paths.

B.

Like it was shown in the left part of the hint picture the upper path must always go through cells (1;2) and (19;20), similar thing for the lower path. Thereby we can consider only slightly shorter paths, which exists in two different subfields of size 19x19 (for example the upper path must be in the green rectangle). There are C(36,18)^2 pairs of such paths, but some of them will intersect.

C.

Now let us consider intersecting paths only. For each pair of such paths we can find a corresponding pair of paths if we take the first point of intersection and interchange the parts on the paths, that passes this point, like it is shown on the right picture. New paths must below to new subfiels of size 18x20 (see the green rectangle) and 20x18. Note that if we draw lines in the new subfiels they will always intersect because of the position of start and end points. Thereby we see that number of intersecting paths-pairs in our 19x19 subfields is equal to number of any possible paths-pairs in 18x20 subfields, which would be C(36,17)^2.

D.

Finally the number of paths-pairs we are interested in would be (C(36,18)^2 - C(36,17)^2)*2. We have to multiply by 2 because we do distinguish red and blue paths, so each path-pair gives us 2 possible cases.

Answer 2

Answer is:

16882265852589060000

because:

Let A(x,y) be the number of solutions for an x,y grid such that x>=y. More specifically, A(x,y) is the number of ways for 2 paths to get from square 1,1 to square x,y such that the first point at which the paths cross (other than 1,1) is at x,y. So A(20,20) is the answer we're looking for. Then A(n,2)=2, A(2,1)=1, A(1,1)=0, A(n,1)=0 for n>2. Now, if the question was simply "how many ways can you get from top left to bottom right, using right and down moves", then the answer would be $38C19$. This is because any way of getting from one corner to the other will involve 19 right moves and 19 down moves, so out of 38 moves you are choosing 19 to be 'right', so its $38C19$. If the question was "how many ways can 2 machines move from top left to bottom right", then the answer would be $(38C19)^2$. However, the question says that the number of squares visited has to be maximised. It follows that the paths of the two machines must never cross at any points other than the top left and bottom right corners. One way to work this out is to take $(38C19)^2$ and subtract the number of path-pairs that cross at one or more points (other than the corners).

Let's ask a simpler question: "given a square i,j within an x,y grid, how many path-pairs are there whose first crossing point is at i,j". When considering this, we can consider two rectangles, one whose corners are at 1,1 and i,j, and the other whose corners are at i,j and x,y. The first rectangle will contain A(i,j) valid paths, and the second will contain $(x-i C y-j)^2$ valid paths. So the answer to the simpler question is $F(i,j,x,y)=A(i,j)*(x-i C y-j)^2$

Now, to find A(x,y) for the above grid, we need to sum up all F(i,j,x,y) over all i and j, except where (both i=x and j=y). Lets call that G(x,y). Then we need to subtract G(x,y) from $(x+y-2Cy-1)^2$. So the equation looks like: $A(x,y)=(x+y-2Cy-1)^2 - G(x,y)$

Notice that if we know A(x,y), then we can find A(x+1,y) or A(x,y+1). So we have a recurrence relation. We start with A(2,2) and build up from there. Running this in a python script, we get A(5,5)=350. All solutions for x,y<=5 are below, starting at offset 0:

[0, 0, 0, 0, 0, 0] [0, 0, 1, 0, 0, 0] [0, 1, 2, 2, 2, 2] [0, 0, 2, 6, 12, 20] [0, 0, 2, 12, 40, 100] [0, 0, 2, 20, 100, 350]

So, e.g. A(5,4)=A(4,5)=100