BrainDen.com - Brain Teasers
• 1

# Ants on an icosagon

## Question

(a)    If an ant is placed on each vertex of a regular isocagon, what is the probability that there will be no encounter between any two ants if all ants start moving simultaneously and randomly (either clockwise or anti-clockwise) along the edge to the next vertex without changing direction?

What are the chances of no encounter if there are …

(b)   Four ants, each placed on the vertices of a tetrahedron?

(c)    Eight ants, starting at the corners of a cube?

Edited by rocdocmac
Changed a bit!

## Recommended Posts

• 1

Rocdocmac, we are clearly well matched: I had a misenumeration  and a miscount, and I’ll raise you my typographical error.

yes, the 8-cycles were duplicated, now I count 12 of them, for a total of 24 out of 3^8.

and, yes, 21658347 is a typo for 21658743, which is a duplicate.

##### Share on other sites

• 0

(a) and (b), haven't done (c) yet:

I assume a trial consists of all ants moving from one vertex to one other vertex. (In other words, we aren't asked about the probability of them never colliding, no matter how far they wander)).

icosagon

The only successful cases are those where all 20 choose Clockwise or all 20 choose Anti-clockwise
probability 2/(2^20)

tetrahedron

ants are on corners 1,2,3,4
the edges connecting them are A(1,2), B(1,3), C(1,4), D(2,3),E(2,4),F(3,4)

1 sees ABC
3 sees BDF
4 sees CEF

if each picks one at random, how many cases are there? 81 cases

enumerate all 4-tuples
AAxx no success
AD: BC, BE, BF, FC, FE--5
AE: BC,  BF, DC,  DF, FC, --5
BA: DC, DE, DF, FC, FE--5
BD: FC, FE--2
BE: DC, DF, FC--3
CA: BE, BF, DE, DF, FE--5
CD: BE, BF, FE--3
CE: BF, DF--2

total 30/81

Edited by CaptainEd
error in icosagon case
##### Share on other sites

• 0

Woops, I did not consider the possibility of two ants arriving at the same vertex through different paths...

##### Share on other sites

• 0

tetrahedron: success only if no two ants arrive at same cell

AE: BF
BA: FE
BD:
BE:
CA: DF
CD: BE
CE:
only 6/81 cases succeed, by my count

##### Share on other sites

• 0

Sorry for the "icosagon"  in the title! Should read isocagon. 'Twas a dyslexic moment!

16 hours ago, CaptainEd said:

tetrahedron: success only if no two ants arrive at same cell

Hide contents

AE: BF
BA: FE
BD:
BE:
CA: DF
CD: BE
CE:
only 6/81 cases succeed, by my count

Spoiler

So far both correct (a) 1/524288 and (b) 2/27

Edited by rocdocmac
spelling
##### Share on other sites

• 0

Ants on cube
Now I see it would be easier if I counted permutations.

What kind of cycles are valid?
1-cycles: impossible, thus no 7-cycles
2-cycles: bad because they represent two ants switching places. Thus no 6-cycles
3-cycles: impossible, thus no 5-cycles
4-cycles: Yes
8-cycles: Yes

Call the vertices
6              5
1      2
4      3
7              8

4-cycles
(1234)(8765) and reverse 2nd one
(1234)(5678) now reverse 1st
(4321)(8765) and reverse both
(4321)(5678)
Ditto for next plane pair
(1256)(8743)
(1256)(3478)
(6521)(8743)
(6521)(3478)
Ditto for third plane pair
(1476)(2385)
(1476)(5832)
(6741)(2385)
(6741)(5832)

Now 8-cycles
First plane pair, crossover at 47
(12347856)next crossover at 16
(23416785)next crossover at 25
(34125678)next  crossover 38
(41238567)
Ditto other direction
(14325876)
(43216587)
(32147658)
(21438765)
Ditto for second plane pair
(12567834)
(25614783
(56123478)
(61258347)
Ditto other direction
(16523874)
(65214387)
(52167438)
(21658347)
Finally third plane pair
(14765832)
(47612583)
(76143258)
(61478325)
And reverse
(16743852)
(67412385)
(74165238)
(41678523)

Total 27 cases out of 3^8
Or
1/243

##### Share on other sites

• 0

Oops can’t count

36/3^8 = 4/3^6

##### Share on other sites

• 0
Spoiler

I'm happy with the first set of 12 possibilities (parallel faces) and the number of combinations (6561). Watch out, however, that there are repetitions in the second lot with the crossovers, e.g. 41238567 is essentially the same as 67412385. Also, the entry "21658347" is invalid!

On 4/11/2018 at 11:25 AM, rocdocmac said:

Sorry for the "icosagon"  in the title! Should read isocagon.

Should have said "isocagon" in the OP is wrong - icosagon in the title needs no change. Double dyslexia!!

##### Share on other sites

• 0
35 minutes ago, CaptainEd said:

Rocdocmac, we are clearly well matched: I had a misenumeration  and a miscount, and I’ll raise you my typographical error.

Hide contents

yes, the 8-cycles were duplicated, now I count 12 of them, for a total of 24 out of 3^8.

and, yes, 21658347 is a typo for 21658743, which is a duplicate.

Spoiler

CaptainEd got all three right! The probability of no collision for 8 ants starting at cube corners is 24/6561 = 8/2187.

Does anyone wish to try a similar OP with ants on the vertices of a regular octahedron and (pentagonal) dodecahedron?

##### Share on other sites

• 0

Ants on octahedron
Once again attempting to count unique permutations

There are six ants.
1-cycles: impossible, so no 5-cycles
2-cycles: invalid, so no 4-cycles
3-cycles: possible
6-cycles: possible

Label the vertices 1-6. With links 2-3-4-5-2 and links from 1 to 2, 3, 4, 5, and from 6 to the same four vertices.
1
2.   3.    4.    5
6

3-cycles
(123)(456), (123)(654), (321)(456), (321)(654),
(134)(256),(134)(652), (431)(256),(431)(652)
(145)(236),(145)(632), (541)(236), (541)(632),
(125)(346), (125)(643), (521)(346), (521)(643)

6-cycles
(123645), (123654), (123465),
(134625), (134652), (134562),
(145623), (145632), (145263),
(152643), (152634), (152364),
(126345), (126543),
(136452), (136254),
(146523), (146325),
(156234), (156432)

36 permutations out of 4^6= 9/1024

##### Share on other sites

• 0
Spoiler

The 16 for 3 cycles is correct, but the 20 for 6 cycles needs an update!

##### Share on other sites

• 0

Thanks, rodocmac

Ants on octahedron
Once again attempting to count unique permutations

There are six ants.
1-cycles: impossible, so no 5-cycles
2-cycles: invalid, so no 4-cycles
3-cycles: possible
6-cycles: possible

3-cycles
Label the vertices 1-6. With links 2-3-4-5-2 and links from 1 to 2, 3, 4, 5, and from 6 to the same four vertices.
1
2.   3.    4.    5
6

3-cycles
(123)(456), (123)(654), (321)(456), (321)(654),
(134)(256),(134)(652), (431)(256),(431)(652)
(145)(236),(145)(632), (541)(236), (541)(632),
(125)(346), (125)(643), (521)(346), (521)(643)

6-cycles
(123645), (123654), (123465),
(134625), (134652), (134562),
(145623), (145632), (145263),
(152643), (152634), (152364),

(132654), (132645), (132564),
(143625), (143652), (143265),
(154632), (154623), (154632),
(125643), (125634), (125463)
(126345), (126543),
(136452), (136254),
(146523), (146325),
(156234), (156432)

48 permutations out of 4^6= 3/256

##### Share on other sites

• 0

CaptainEd ...

Spoiler

Spot-on with your most recent octahedral attempt and congrats for solving this one too!

Are you going to try deciphering the dodecahedral case as well? It does take some time if done "by hand", no doubt, but certainly not a too difficult exercise!

##### Share on other sites

• 0

Rodocmac, thank you, but I’ll pass. I’ve posted “oops” enough for now :-)

## Join the conversation

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

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

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