Ants on an icosagon

[rocdocmac]

(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 April 10, 2018 by rocdocmac
Changed a bit!

[CaptainEd]

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.

[CaptainEd]

(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
2 sees ADE
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 April 10, 2018 by CaptainEd
error in icosagon case

[CaptainEd]

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

[CaptainEd]

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

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

[rocdocmac]

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

AD: BE, FC
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 April 11, 2018 by rocdocmac
spelling

[CaptainEd]

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

[CaptainEd]

Oops can’t count 

36/3^8 = 4/3^6

[rocdocmac]

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!!

[rocdocmac]

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?

 

[CaptainEd]

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

[rocdocmac]

Spoiler

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

 

[CaptainEd]

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

[rocdocmac]

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!

 

[CaptainEd]

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