4
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ This puzzle has a wonderful trap! Unfortunately I have a hunch the answer is something horrible like 416219573710066468074766866309477040127999/517665364007190708723383247796848033792000. $\endgroup$ – Lopsy Apr 4 '15 at 20:05
  • 1
    $\begingroup$ @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}]] $\endgroup$ – Milo Brandt Apr 4 '15 at 22:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Lopsy Apr 5 '15 at 6:09
  • $\begingroup$ @Meelo Your Mathematica code looks right to me. I tried different sizes and could not find a pattern in the denominators either. $\endgroup$ – finsternis Apr 9 '15 at 3:24
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.