# Challenge 69: Three Ants on an Octahedron

Share
Embed
• Published on Nov 29, 2018
• Congratulations to Essentials of Math, Gustavo Exel, Devansh Sehta, Minh Cong Nguyen, Prathmesh, Eliot Argüello, Jack Miller, NoName, Daulian Doge, and Benjamin Wang for successfully solving the last week's math challenge question! Essentials of Math was the first person to solve the question.
Your support is truly a huge encouragement.
Every subscriber and every like are wholeheartedly appreciated.
Welcome, everyone! My channel hosts one weekly math challenge question per week (made by either myself, my family, or my friends), which will be posted every Wednesday. Please comment your proposed answer and explanation below! If you are among the first ten people with the correct answer, you will be recognized in the next math challenge video. The solution to this question and new question will be posted next Wednesday.
For more Weekly Math Challenges:

• Steven Mellemans 6 months ago

I hate these problems. I got the answer 64/27 but only by brute force counting the probabilities between each of the 3 states. I could not simplify or redefine the problem in order to find these probabilities in a less labor intensive way. Curious to find out what the easiest approach is.

• Raiyan Ahmed 6 months ago

3 ants go marching on the octahedron HORRAA HORAAAAA....

• NoName 6 months ago +1

Yey
I was featured

• Thanks for you

• Brian talks about 6 months ago

Come to my channel and solve my problem in my latest video. The first one who does can win bitcoin (I encoded the secret key to a wallet into the answer of my problem) first one to solve gets the prize!!!

• Zakiror Rahman 6 months ago

• Anandan Poornash 6 months ago

• mstmar 6 months ago

There are 3 rotationally symmetrical states the ants can be in : one where at least 2 ants are on the same vertex (the end state, e), one like the start where 2 ants are opposite and 1 between them (the start state, s), one where they form a triangle of connected vertices (t). Counting how many of the possible moves gets us from s and t to the other states, then dividing by the total number of moves gets us the probability that the ants go from one state to another:
p(s->e) = 7/16, p(s->s) = 5/16, p(s->t) = 1/4
p(t->e) = 3/8, p(t->s) = 3/8, p(t->t) = 1/4
now the expected number of moves to get from start to end with the following formulas for the expected distance:
e(s->e) = p(s->e) * 1 + p(s->s) * (1+e(s->e)) + p(s->t) * (1+e(t->e))
e(t->e) = p(t->e) * 1 + p(t->s) * (1+e(s->e)) + p(t->t) * (1+e(t->e))
we substitute our probabilities then solve for e(s->e) giving us an expected moves until collision of 64/27 (approximately 2.37)

• manishkumar singh 6 months ago +2

(4/3)^3

• O W E M 6 months ago +4

hehe. 69.

• Alex Edwards 6 months ago

Revision to my answer below, I meant 64/27.
Similar to some of the other replies here, I also got **64/27**.

Removing symmetries, and considering the ants indistinguishable, there are only two configurations in which no two of the three ants share a vertex. They are the case described in the problem in which two ants are opposite of each other and the remaining ant is on one of the four remaining vertices, and the case in which the three ant occupy a trio of vertices that border the same face of the octohedron. Let's denote the two states respectively i and j, and the expected number of moves starting from each as I and J respectively.

Starting from state i, there are 64 possible moves the ants can make. Some slightly tedious counting will show that 20 of these return to state i, 16 result in state j, and 28 result in an ant collision, which is the desired result.

Thus, I = 20/64 * (I+1) + 16/64 * (J + 1) + 28/64 = 5/16 * I + 1/4 * J + 1
Shifting around, we get I = 4/11 J + 16/11

Likewise, starting from state j, there are 64 possible moves. 24 of these result in state i, 16 of these return to state j, and 24 of these result in a collision.

Thus, J = 24/64 * (I+1) + 16/64 * (J+1) + 24/64 = 3/8 * I + 1/4 * J + 1
Which is equivalent to J = 1/2 * I + 4/3

All that's left to do is solve for the unknowns.
J = 1/2 * I + 4/3 => -I = -2J + 8/3

Adding this to the first equation gives 0 = -18/11J + 136/33 => J = 68/27
Substituting this into the first equation, I = 4/11 (68/27) + 16/11 = 64/27 which is the answer.

As a fun note: This type of problem appears often in programming competitions. This problem was simple because it had only two states, but the solution can be extended to any finite state machine who's state transitions are governed by probability. These problems get complex very quickly, hence the need for computational power.

• adandap 6 months ago +2

There are three possible states, which I will call O (opposite) and A (adjacent) and C (coincident). Once we reach C we stop. The states O and A can transition from one to another with probabilities Poo (!) Poa Pao and Paa, which gives us a 2 x 2 transition matrix once we work out the probabilities. If I counted right (and I got it wrong at least once!) they are 20/64, 24/64, 16, 64 and 16/64. Using the Markov chain trick of calculating (I - M) inverse and summing the row that corresponds to the transition from O (our original state) and C, we find the answer for the expectation value to be 16/9 + 16/27 = 64/27

• Max Haibara 6 months ago +4

Notice that there are only 3 different states :
- 2 ants in the opposite vertices (our first state). Let's define this state as O.
- 3 ants in the same side. Let's define this state as T.
- at least 2 ants meet in a vertex (our final state). Let's define this state as M.
In each vertex, we can choose 4 different edges. Since there are 3 ants, in total there are 4x4x4=64 different moves that they can make.
If we are in state O, there are :
- 28 different ways to go to state M
- 20 different ways to go to state O
- 16 different ways to go to state T
If we are in state T, there are :
- 24 different ways to go to state M
- 24 different ways to go to state O
- 16 different ways to go to state T
Let's use a recursion to solve this problem. Define f("state") is the expected number of moves so that at least 2 ants meet in a vertex if the current state is "state". Then :
f(O)=28/64 f(M) + 20/64 f(O) + 16/64 f(T) + 1
f(T)=24/64 f(M) + 24/64 f(O) + 16/64 f(T) + 1
f(M)=0
substitute the value of f(M) :
f(O) = 20/64 f(O) + 16/64 f(T) + 1 => 64 f(O) = 20 f(O) + 16 f(T) + 64 => 16 f(O) = 5 f(O) + 4 f(T) + 16 => 11f(O)-4f(T)=16
f(T) = 24/64 f(O) + 16/64 f(T) + 1 => 64 f(T) = 24 f(O) + 16 f(T) + 64 => 16 f(T) = 6 f(O) + 4 f(T) + 16 => -6f(O)+12f(T)=16
Then we can just solve it like a regular equation system. Multiply the first equation by 3
33f(O)-12f(T)=48
-6f(O)+12f(T)=16
27f(O)=64
f(O)=64/27

• Max Haibara 6 months ago +2

Notes: maybe you wonder why it doesn't look like a recursion at all. Basically the short explanation is : I'm a competitive programmer and we have something that's based on recursion, called Dynamic Programming. Basically I'm just trying to solve this problem with the way I do it in Competitive Programming, instead of a math competition. Obviously it's still the same thing, just viewed from a different perspective.
Simple explanation of Dynamic Programming (DP) : in DP, we have 3 main components: State, Recurrence, and Base Case.
State is the parameter of the function. In this problem, we have only 1 state, which is "state" that has 3 different values.
Recurrence is the recursive formula. It's the f(O)=28/64 f(M) + 20/64 f(O) + 16/64 f(T) + 1
and f(T)=24/64 f(M) + 24/64 f(O) + 16/64 f(T) + 1.
Base case is when the recursion is stopped. It's f(M)=0.
So yeah, it should have the same answer unless I made a mistake in my calculation :p

• PhyMath MaSics 6 months ago

Let's assume that A,B,C and D are coplanar vertices of the octahedron and Austin, Caroline and Becky are at points A,C and D(as A and C are opposite vertices and point D is symmetrical with other points). Now consider Austin's move:
1)when Austin moves from A to B the possible ways to resist collide is 3+2=5
2)when Austin moves from A to E number of ways is 2
3)when Austin goes from A to F number of ways is 2+2=4
Now total possible moves are 4^3=64
Hence the probability is (5+2+4)/64=11/64

• Aswini Banerjee 6 months ago +1

There are infinitely many ways for ignoring collision as They can simply just move around any closed path along the octahedron.

• LetsSolveMathProblems  6 months ago +7

Infinitely many possibilities do not necessarily imply an infinite expected value. For example, consider tossing a coin until heads shows up. For every positive integer N, it is certainly possible that we get N tails in a row. However, note that the probability of getting N consecutive tails approaches 0 as N increases, so the probability of getting "infinitely many tails in a row" is 0. In fact, the expected number of throws until the first heads is 2, a finite number.

• Aaron Lamoreaux 6 months ago +3

There answer is 2.37037037 or (64/27) expected moves until two ants are on the same vertex.
Notice that there are only two arrangements of ants on the octohedron W.L.O.G which we will call A and B. A is where three are on all vertices of a single face of the octohedron. The other is where two ants are opposite and one ant is directly between them. Notice that these are the only arrangements of ants without respect to order, rotation, ant number, etc.
We can then set up a system of equations for each arrangement. From each arrangement there are 64 possible reachable states. Some of these are A or B and the rest are a state where at least two ants are on the same vertex. For B there are 16 ways to get to A and 20 ways to get to B. Thus B = (1/64)(28 + 16(A + 1) + 20(B + 1)). For A there are 16 ways to get to A and 24 ways to get to B. Thus A = (1/64)(24 + 16(A + 1) + 24(B + 1)). Solving for A and B gives A = 68/27 and B = 64/27 as the expected moves to reach the end state.
Since the initial state matches a B configuration, we answer 64/27 = 2.37037037 expected moves as the answer.

• Brian talks about 6 months ago

On my channel (see recent video)... if u solve my problem... you can win bitcoin (I encoded the secret key to an account into the answer)
Wanna take this shit to the next level bro?