Jump to content
BrainDen.com - Brain Teasers
  • 0

Ants on a checkerboard


bonanova
 Share

Question

Two ants named Al and Bert sit at diagonal corners of a checkerboard and decide to change places. Al, at the lower left,  walks randomly upward or to the right, and Bert, at the upper right, walks randomly downward or to the left. They follow the boundaries of the checkerboard squares. That is, except when following the extreme boundary of the checkerboard, their left and right feet always touch squares of opposite color.

checker.jpg

What is the probability of their meeting (1) if they walk at the same speed, or (2) if Al walks 3 times as fast as Bert?

Link to comment
Share on other sites

11 answers to this question

Recommended Posts

  • 1

Here's what I came up with

Spoiler

As Captain Ed said, if Al walks three times as fast as Bert, they’ll meet at the diagonal that goes from halfway through one side of the board and halfway through a neighboring side. To calculate the probability that the ant will land at any one of those vertices along that diagonal, one might think it suffices to calculate the number of paths that could lead to each of those vertices.

In general, if an ant is walking to a square at (x, y) where the ant can either take a step going +1 along the x-axis or +1 along the y-axis, then the number of possible paths it could take to reach square (x, y) is the number of paths it could take to reach square (x-1, y) plus the number of paths it could take to reach square (x, y-1). That’s shown in the following figure. (Unfortunately, I mixed up Al and Bert and I have the faster walking ant starting in the upper right corner, but nevertheless this shows the number of different paths that the ant could take to reach that diagonal.)

5a6f3e00abe04_Boardants.JPG.3efc0ca187242a986ac9b9e6202e0388.JPG
But notice in the first paragraph, I said “one might think it suffices to calculate the number of paths that could lead to each of those vertices.” It happens to be the case that I am not one. If we’re dealing with an ant that walks along the edges of each square, then when it reaches the halfway point of the board, it no longer has a 50/50 chance of going in any direction – if the ant is on an edge of the entire checkerboard, then there’s only one direction it can go that would not have it scurrying off the edge of the board. Since it doesn’t have two choices, the probability that it would walk in a direction that would take it off the board should instead be redirected to move it along the only available path. In that case, the probability of ending up in each vertex is proportional to the numbers in the following figure.

5a6f3dffefc94_Boardants2.JPG.6e08ed352a8f2f1282af795aa9454143.JPG

Odds that the upper right ant ends up in each of the five possible intersections are
794/4096, 792/4096, 924/4096, 792/4096, 794/4096

Odds that the lower left ant ends up in each of the five possible intersections are the same as the odds that the upper right ant will end up at the corresponding spot on the diagonal from the middle of the top edge to the middle of the right edge.
1/16, 4/16, 6/16, 4/16, 1/16

So the odds that they meet are
(794 x 1 + 792 x 4 + 924 x 6 + 792 x 4 + 794 x 1) / (4096 x 16) = 13468 / 65536 ~= 0.2055

Edit: an aside

Spoiler

It can't be the case that the probability of the ants meeting is, in general, not dependent on their speed. Suppose the ant in the upper right moved 15 squares by the time the lower left ant moved 1. In that case, the ants would meet on one of two vertices in the bottom left square, either its upper left or its lower right vertex, and the odds of meeting would of course be 50/50.

Edit2: even further aside

Spoiler

But if you allow an ant to walk off the edge of the board, then the probabilities of meeting might become independent of speed. I haven't mathed that out.

 

Edited by plasmid
Link to comment
Share on other sites

  • 1

Cute puzzle, Bonanova, as always.

(1) 

after 8 steps, each of them is in one of the 9 vertices going SE from the upper left corner. The probabilities are C(8,1)/256, C(8,2)/256, etc. So the probability of Al and Bert arriving at the same corner is the sum of the squares of those probabilities

(2) partially

after 12 Al steps, (and therefore 4 Bert steps), they are each on the shorter NW-SE diagonal beginning in the middle of the top of the board.. For Bert, the probabilities are C(4,1)/16, C(4,2)/16, etc. I have not figured out the probabilities for Al, however

Link to comment
Share on other sites

  • 0
22 hours ago, CaptainEd said:

Cute puzzle, Bonanova, as always.

(1)

  Hide contents

 

after 8 steps, each of them is in one of the 9 vertices going SE from the upper left corner. The probabilities are C(8,1)/256, C(8,2)/256, etc. So the probability of Al and Bert arriving at the same corner is the sum of the squares of those probabilities

 

(2) partially

 

  Hide contents

after 12 Al steps, (and therefore 4 Bert steps), they are each on the shorter NW-SE diagonal beginning in the middle of the top of the board.. For Bert, the probabilities are C(4,1)/16, C(4,2)/16, etc. I have not figured out the probabilities for Al, however

 

 

 

Right so far, and the one not yet calculated is interesting.

Link to comment
Share on other sites

  • 0

 

 

 

My previous wasn’t exactly right, but now I think I’ve got it

A) the 9 vertices from NW corner to SE corner get probabilities

C(8,0)*C(8,0) + C(8,1)C(8,1) + ... + C(8,8)*C(8,8), divided by 2^16, because Al and Bert each take 8 steps

B) the 5 vertices from top center in Se direction get probabilities

C(12,4)*C(4,0) + C(12,5)*C(4,1) + C(12,6)*C(4,2) + C(12,7)*C(4,3) + C(12,8)*C(4,4), all divided by 2^16, because Al takes 12 steps and Bert takes 4. 

Edited by CaptainEd
Elephant font, please remove
Link to comment
Share on other sites

  • 0

For @plasmid, your argument sways me for part b, but I’m certain of part a.

A) for the 8 step case, there are no places where the ant can’t go in a particular direction, so it seems like the 9 endpoints exhaust all the possibilities of 2^8. So I believe the C(8,0),...,C(8,8) counts are accurate, as well as the denominator. So, unless my iPhone Excel formula fell victim to roundoff rot, my number feels right.

B) for the 12 step case, though, your argument feels reasonable, that we don’t want the denominator to count trajectories that would take Al off the board.

I still like the calculation of the paths actually taken to the five vertices. For example, the vertex that requires 8 up and 4 to the right should receive all combinations of 8 ups and 4 rights, which feels like C(12,4). 

We may have to ask the philosophical question, “what does it mean for a choice to be uniformly randomly distributed if the ant gets to the end of the world?”

I have to look more deeply, if I can.

Link to comment
Share on other sites

  • 0

I think for part (b), I’ve got the right answer for the wrong question.

If Al starts at the SW corner, and makes 12 steps, one per vertex, some of his paths will go outside the checkerboards, to the north and to the east. The only vertices that Bert can reach are the five beginning at top center and proceeding SW to the right side of the board, as we have said before.

The number of paths is 2^12, so the probabilities if meeting Bert is as I said earlier.

 

The problem is, as plasmid points out, this doesn’t meet the OP, which seems to require the ant to stay on the board (or at least keep one foot track on the board).

 

One approach, as plasmid says, is to divert all the wayward paths to remain on the top edge or right edge. That would preserve the denominator, and add to the numerator.

 

Another approach is to reduce the denominator by the paths that would have gone out of bounds. That would reduce the denominator to the total of the paths that end on the same 5 vertices. That ought to raise the total probability, even higher than plasmid’s calculation. And it makes it hard to justify the notion of choosing steps at random.

Link to comment
Share on other sites

  • 0

Regarding the 5 probabilities after 12 ant moves:

Spoiler

Enumerating paths and treating them as equals gives { C(12,8) C(12,7) C(12,6) C(12,5) C(12,4) } / (3498) multiplied by { 1 4 6 4 1 } / 16 and summing for a result of .22995. But Al (the faster ant)'s paths involve from 8 to 12 choices, so they are not equally likely. Probabilities derived by dividing each path by the sum of all paths (3498 in this case) will be incorrect. What is the right approach?

  • @plasmid augments paths that touch an intermediate border point, where a choice is eliminated, by multiplying by 2 at each point. The effect is to create virtual paths that increase the count to each end point by 299, making 4096 = 212 total paths and leads to the correct probability of .20551.

    I have three other approaches. The first is the one I thought would be found here. Another is quick and dirty. The last one occurred to me as I'm writing this.

     
  • This one seems evidently correct but is the most involved of the three.

    Call the Final points { F1 F2 F3 F4 F5 } with probabilities of { fffff5 }.

    Start with a result from the first problem, the probabilities {
    d1 d2 d3 d4 d5 d6 d7 d8 d9 } of reaching the 9 diagonal points. Then (by inspection) determine the probabilities of reaching each Fi from the one-to-five possible starting diagonal points Dj. Call those p(Dj, Fi). There are 25, but really only 15 due to symmetry, and some are trivial. Others take just a little thought. Clearly p(D1 ,F1)=1. Then, since p(D2, F2) (4 E moves) = 1/16, we have p(D2, F1) = 15/16, and so on. Then we have

    fi = sum(j) { dj x p(Dj, Fi) }
     
  • This one involves the least work.

    Paths to { F2 F3 F4 } don't hit an edge. So { fff4 } = { C(12,7) C(12,6) C(12,5) } / 212
    Then  f1 = f5 = 1/2 ( 1 - sum { f2  ff4 } )
         
  • This one recognizes an equivalent calculation.

    What is the probability of flipping 8 heads before flipping 5 tails? I don't know whether this is an easy question or not, but the answer gives f1 and f5.
  •  
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...