4

I'm going to raise the difficulty of the original question one dimension, so maybe a refresher will be good... Link: Ant walking on a number line


I just mentioned i will raise it by one dimension... and yes i meant it.

I will be using co-ordinates to put the points.

The ant is at (7,7)

The drops of honey are now lines of honey at x=10, y=10 and x=0, y=0

Let P(10) be the possibility of the ant eating the honey from x=10 or y=10

and P(0) be the possibility of the ant eating honey from x=0 or y=0.

The ant moves up, down, left, or right randomly.

And... Calculate P(0) and P(10)

the4seasons
  • 564
  • 3
  • 13
  • This puzzle has a wonderful trap! Unfortunately I have a hunch the answer is something horrible like 416219573710066468074766866309477040127999/517665364007190708723383247796848033792000. – Lopsy Apr 04 '15 at 20:05
  • 1
    @Lopsy Yeah; Mathematica gives me $\frac{114225184}{142065451}$ as the answer. I haven't a clue where that denominator comes from, but numerically this is close to Akiino's answer. For the reference of anyone with Mathematica, here's the code (I haven't golfed it yet though!): Solve[Join @@ Drop[Drop[ Array[m, {11, 11}, {0, 0}] /. {m[a_, b_] -> m[a, b] == (m[a - 1, b] + m[a + 1, b] + m[a, b - 1] + m[a, b + 1])/4} /. {m[0, a_] -> 0, m[a_, 0] -> 0, m[10, b_] -> 1, m[b_, 10] -> 1}, 1, 1], -1, -1], Join @@ Array[m, {9, 9}]] – Milo Brandt Apr 04 '15 at 22:16
  • 1
    Ok, confirmed. My fraction was wrong because my code had an integer division roundoff error. After fixing that, it's the same as yours. I made an 11x11 array and initialized the finish squares to either 0 or N, where N is a very large integer which had to be a multiple of the denominator; and then repeatedly replaced every square by the average of its neighbors until convergence. – Lopsy Apr 05 '15 at 06:09
  • @Meelo Your Mathematica code looks right to me. I tried different sizes and could not find a pattern in the denominators either. – finsternis Apr 09 '15 at 03:24

2 Answers2

5

We can solve this with a general approach by doing some linear algebra. The nice thing about a general approach like this is, that even irregular, 42-dimensional (finite) shapes can still be solved.

In this case, it will involve a matrix with 81 rows and 117 columns and compute for all starting fields the exact probability distribution of rest states (at the border). And while a matrix with 9477 entries may look a bit daunting at first, it can be easily handled by a computer program.

For illustration purposes, first consider the region of tuples $x, y \in 0,1,2,3$. Respectively only the inner square of four points $\{1,2\}×\{1,2\}$ is not filled with honey. It looks like this:

FOOD         ab
F..D   or   cαβd , to give some variable names.
F..D        eγδf
FOOD         gh

For each of the inner fields $α, β, γ, δ$, the probability distribution of final states called $D$ is given by a linear equation, e.g.: $$Dα = \frac{a+c+β+γ}{4}\text{.}$$

The resulting matrix is (after multiplication by $-4$):

   α  β γ δ  a b c d e f g h
Dα -4,1,1,0, 1,0,1,0,0,0,0,0;
Dβ 1,-4,0,1, 0,1,0,1,0,0,0,0;
Dγ 1,0,-4,1, 0,0,0,0,1,0,1,0;
Dδ 0,1,1,-4, 0,0,0,0,0,1,0,1;

And using a handy online tool by Kardi Teknomo we can compute the reduced row echelon form of this matrix: (Multiplied by $-24$)

     α β γ δ  a b c d e f g h
Dα -24,0,0,0, 7,2,7,2,2,1,2,1;
Dβ 0,-24,0,0, 2,7,2,7,1,2,1,2;
Dγ 0,0,-24,0, 2,1,2,1,7,2,7,2;
Dδ 0,0,0,-24, 1,2,1,2,2,7,2,7;

We can now extract the information that $$Dγ = \frac{2a+b+2c+d+7e+2f+7g+2h}{24}$$

And since we would like to know what the chance of turning up at $x=0$ or $y=0$ is, we just add up the chances to end up at $c, e, g$ or $h$ which is $\frac{2+7+2+7}{24} = \frac{9}{12}$.

What does this tell us about the actual problem at hand? Well we can write a little program which generates the redistribution matrix $D$ for us. Next we tell it to calculate the reduced row echelon form and finally we extract our information. For a lack of motivation though, writing that program is left as an exercise to the reader :P.

Rolf Kreibaum
  • 266
  • 1
  • 4
2

Once again, Python comes in:

from random import randint
f10 = 0
f0 = 0
coordx = 7
coordy = 7
iters = 0
finished = False
while not finished:
    while coordx > 0 and coordx < 10 and coordy > 0 and coordy < 10:
        if randint(0, 1) == 0:
            coordx += randint(0, 1)*2-1
        else:
            coordy += randint(0, 1)*2-1
        if coordx == 10 or coordy == 10:
            f10 += 1
        elif coordx == 0 or coordy == 0:
            f0 += 1
        if iters == 10000000:
            finished = True
            print 1.0 * f0 / iters, 1.0 * f10 / iters
    coordx = 7
    coordy = 7
    iters += 1

The result produced after 10.000.000 simulations is 0.195875719588 and 0.804124380412 and that makes two things clear – the answer is definitely not the same and it is not as simple (I tried to assemble an expression with this result but got nowhere). Though at least it provides a reference point for those on better terms with math than I am.

P.S. Not sure if answer or comment, but it does contain the answer in approximate form, so I'll post it here. If I'm wrong, feel free to convert it into a comment