14
$\begingroup$

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?"

grid example

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:hint

$\endgroup$
  • 1
    $\begingroup$ I'd say instinctively that if they have 2 machines they have to carry them both to the top-left corner and it's the same effort as having 1 machine and carry it twice to the top-left corner (having thus 2 subsequent passes rather than 2 contemporaneous passes). Because of this, I would consider Bob's idea unsuccessful. But this is likely not the point of the riddle $\endgroup$ – Alessandro Apr 5 '16 at 8:54
  • $\begingroup$ I also don't get what the added value of two machines is. It's exactly the same as using 1 machine twice, just as Alessandro explained $\endgroup$ – Ivo Beckers Apr 5 '16 at 9:01
  • $\begingroup$ Both machines can take different paths. the maximum value will be twice, and it can be done in lots of ways. $\endgroup$ – Arcane Apr 5 '16 at 9:14
  • 2
    $\begingroup$ The math to figure out how many paths can be made using 19 moves down and 19 moves right is fairly easy. Figuring out how many combinations of two of those paths is fairly easy too. It is however less trivial to figure out how many of those are non-intersecting. Any combination where the two paths intersect in any other square then start or finish will yield sub-optimal harvest quantities... $\endgroup$ – Tim Couwelier Apr 5 '16 at 9:39
  • 1
    $\begingroup$ prntscr.com/aod4ix I've tried to use paint to show how it maybe done. The green are starting points, Yellow and red are the areas where machine can move without intersecting. This is just 1 case. At the end double the total number to permute columns instead of rows. $\endgroup$ – Arcane Apr 5 '16 at 10:05
4
$\begingroup$

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 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.

$\endgroup$
  • $\begingroup$ I think it could use some clarity and detail, but as far as the proof goes, it is definitely correct and provides a non-recursive (and thus much more efficient) method of obtaining a general solution. All in all, great reasoning! $\endgroup$ – Fimpellizieri Apr 6 '16 at 9:04
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The answer is correct, but what Alice did was much simpler than this. $\endgroup$ – ffao Apr 5 '16 at 18:49
  • $\begingroup$ @ffao If this answer is correct then how was Bob unsuccessful? I thought we needed to show this number is less than the number of ways to make one pass? $\endgroup$ – Jonathan Allan Apr 5 '16 at 19:05
  • 2
    $\begingroup$ Bob was unsuccessful in stumping Alice $\endgroup$ – ffao Apr 5 '16 at 19:05
  • $\begingroup$ oh ha ha misinterpreted that $\endgroup$ – Jonathan Allan Apr 5 '16 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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