mathematics - How many ways to pick the fruit

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

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.