hey this is preshtalwalker
eight ants start at different corners of
a cube
suddenly each ant moves to an adjacent
corner at random
that is each ant walks along one of its
three adjacent edges with equal chance
what is the probability that none of the
ants collide
i received this problem by email from
dave carpenter and it's quite
fascinating
can you figure it out
give this problem a try and when you're
ready keep watching the video for the
solution
so let's first consider the total number
of ways that the ants can move
each ant can move along three possible
edges
the total number of paths for eight ants
equals the product of the number of
possibilities for each ant
this means the total number path will be
3 to the power of 8 which equals 65 61.
now we need to count the number of paths
in which the ants do not collide
so one way the ants might not collide is
that the ants on opposite faces rotate
positions
for example
we can have the ants on the top face
rotate positions and have the ants on
the bottom face rotate positions
here's one way that the ants could move
so that they would not collide
but that's not the only possibility for
the ants on the top and the bottom faces
for each face the ants can move in two
directions either clockwise or
counterclockwise
so we have to consider that there will
be more possibilities
here's another way that the ants could
move in which they would not collide
here's another way
and there will also be one more fourth
way that the ants on the top and bottom
faces will not collide
in total the ants on each face can move
either clockwise or counterclockwise
and there are two faces so that means
two times two which equals four
possibilities for each pair of opposite
faces
now just for fun i'm going to show you
all of these possibilities for the top
and bottom faces at once
so you can see the ants are moving in
different directions in each of these
four different cubes
furthermore we've only considered top
and bottom faces but there can be three
pairs of opposite faces on a cube
we've just illustrated top and bottom
but we can also do the same sort of
thing for the front and back faces
and we could do the same sort of thing
for the left and right faces where the
ants in these faces
rotate positions with each other
so how many different ways have we just
figured out
well there are four different ways for
each pair of opposite faces and there
are three kinds of opposite faces that
makes for four times three which equals
12 ways the ants do not collide
but there is more
there's another way that the ants could
not collide which is that all eight of
the ants can move in a loop
a closed path that goes through every
vertex exactly once is called a
hamiltonian cycle
now to preempt a comment
it will go through every vertex exactly
once except for the vertex that's both
at the start of the end which is visited
twice
so with that caveat we have the
definition of a hamiltonian cycle so we
want to figure out how many hamiltonian
cycles there are for the cube
so this will be a little bit more
difficult to show you
so rather than going through this 3d
model i'm actually going to flatten out
the cube
this is known as a cubicle graph and
it's a 2d version of the cube
so let's illustrate the number of
hamiltonian cycles let me clean up this
diagram
and now i'm going to tell you there are
actually six undirected hamiltonian
cycles
you can imagine if you start at one
vertex there will be three choices
and then for the second vertex that you
go to there will be two more choices
so here's one example of the hamiltonian
cycle
now let me go ahead and illustrate all
of the other ones as well
now this front face involves three
different edges that are going through
this loop you could also have the front
face have exactly two of its edges
involved in a loop
so here are the remaining hamiltonian
cycles
so these are six undirected hamiltonian
cycles
for each of these we can actually place
directions
to create the ways that the ants might
possibly flow on the cube these are
directed hamiltonian cycles
now this is one way that we could draw
the arrows but we can also draw the
arrows in the opposite direction
therefore for each undirected
hamiltonian cycle we have two possible
directions for the loop
so this means
since each loop can be traversed in two
directions there are 12 directed
hamiltonian cycles in other words 12
ways that the ants could move so that
they would not collide
so now let's calculate the answer
there are 24 total ways that the ants
will not collide we have 12 cases from
case 1 and 12 cases from case 2.
this is out of a total of 6561 possible
ways the ants could move
therefore the probability that there's
no collision will be 24 divided by 6561
which equals 8 out of 2187 which is
approximately 0.37 percent it's a very
slim chance that the ants will not
collide
but it involves
very interesting geometrical loops that
are on the cube
did you figure it out
thanks for watching this video please
subscribe to my channel i make videos on
math you can catch me on my blog mind
your decisions which you can follow on
facebook google plus and patreon you can
catch me on social media at
preshtalwalker and if you like this
video please check out my books there
are links in the video description