Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
rocdocmac

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!

Share this post


Link to post
Share on other sites

14 answers to this question

  • 0

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 this post


Link to post
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
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 by CaptainEd
error in icosagon case

Share this post


Link to post
Share on other sites
  • 0

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

Share this post


Link to post
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


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 by rocdocmac
spelling

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×