MHB Probability problem in hexagon

[leuler]

So say I have 6 bugs standing on the 6 vertices of a hexagon, one per vertex. And say they each pick a vertex that they are not currently on, and starts moving in a straight line towards that vertex at the same speed. So my question is how many possibilities are there for the bugs to move to the vertices such that none of them are ever in the same place at the same time?

 

[MarkFL]

Can you post what you have tried or what your thoughts are on how to begin so our helpers can see where you are stuck and how best to help you?

 

[leuler]

Well, I know that if two bugs are in the same place, then they are the same distance away from their starting vertices. However, I have trouble listing out all of the possible combinations. There are 9 diagonals of a regular hexagon.

 

[leuler]

Ok, I think I might know how to do this now. There are 265 possible ways that the bugs could move to a different vertex, and 210 possible ways that the bugs meet at the center of the hexagon, and 168 ways that they could meet at a place that is not at the center. After this, you have to add the number of ways that the bugs do both, which turns out to be 240, so the total number of ways is 265-240-168+240=127. Can someone check this? My method was to represent each vertex arrangement as a permutation.

 

[johng1]

Hi,
This is an interesting fun problem. However, the only number of yours that I understand is the 265 derangements of 6 objects. My counting skills are not up to solving the problem by hand, so I enlisted the aid of the computer.

First observation is that if a given derangement d contains a transposition (d=j and d[j]=i for some i and j), then the bugs meet at the midpoint of of the line connecting vertex i and j. So this eliminates 105 of the derangements, leaving only 160 possibilities. So "just" examine each of these 160 for collisions.

The first attachment restates the problem and shows the main idea in detecting collisions:

There are 58 derangements with no collisions. The next attachment shows these. There are 7 different types. In each type, you can get another no collision derangement of the same type by reversing the arrows or a suitable rotation.

Finally, here's the C program that examines each possible derangement for collisions:

#include <stdio.h>
#include <stdlib.h>
#define MAX (20)
#define Swap(x,y,t) t=x; x=y; y=t

void Perms1(int p[],int n,int m);
void Cycle(int p[],int n);

int noCollisions=0;
FILE *ofp;

int main(void){
    int p[MAX];
    int i,n=6;
    ofp=fopen("hexagondata.txt","w");
    for (i=0;i<n;p[i]=i,i++);
    fprintf(ofp,"Derangements with no collisions.\n");
    Perms1(p,n,n);
    fclose(ofp);
    return(0);
}

void Cycle(int p[],int n)/* Outputs p in both linear and cyclic form */{
    int a[MAX];
    int i,j,k;
    fprintf(ofp,"%d.  ",noCollisions);
    for (i=0;i<n;i++) {
        a[i]=p[i];
        fprintf(ofp," %d",a[i]);
    }
    fprintf(ofp," --- ");
    do {
        for (i=0;i<n && a[i]==-1;i++);
        if (i==n) {
            break;
        }
        if (i!=n-1 && a[i]!=i) {
            fprintf(ofp,"( %d",i);
            j=a[i];
            a[i]=-1;
            do {
                fprintf(ofp," %d",j);
                k=j;
                j=a[j];
                a[k]=-1;
            }
            while (j!=i);
            fprintf(ofp," )");
        }
        else
            a[i]=-1;
    }
    while (i!=n-1);
    fprintf(ofp,"\n");
}

int collision(int p[]) {
    int i,j;
    int indices[6];
    // does p contain a transposition?
    for (i=0;i<6;i++) {
        if (p[p[i]]==i) {
            return(1);
        }
    }
    // now check each vertex for a collision
    for (i=0;i<6;i++) {
        for (j=0;j<6;j++) {
            indices[j]=(i+j)%6;
        }
        if (p[i]==indices[2]) {
            if (p[indices[1]]==indices[5] || p[indices[3]]==indices[1]) {
                return(1);
            }
        }
        if (p[i]==indices[3]) {
            if (p[indices[1]]==indices[4] || p[indices[4]]==indices[1]
                    || p[indices[2]]==indices[5] || p[indices[5]]==indices[2]) {
                return(1);
            }
        }
        if (p[i]==indices[4]) {
            if (p[indices[5]]==indices[1] || p[indices[3]]==indices[5]) {
                return(1);
            }
        }
    }
    return(0);
}
/* Standard recursive generation of all permutations.  This is modified to process only
derangements.  For such a derangement, if there are no collisions, the derangement
is printed via function cycle.
*/

void Perms1(int p[],int n, int m){
    int i,j;
    int temp;
    if (n==0) {
        for (j=0;j<m;j++) {
            if (p[j]==j) {
                break;
            }
        }
        if (j==m) { // p is a derangement
            if (!collision(p)) {
                noCollisions++;
                Cycle(p,m);
            }
        }
    }
    else {
        Perms1(p,n-1,m);
        for (i=n-2;i>=0;i--) {
            Swap(p[i],p[n-1],temp);
            Perms1(p,n-1,m);
            Swap(p[i],p[n-1],temp);
        }
    }
}

Since the numbers are so "small" for a computer, the above program runs very quickly, about 5 100th's of a second on my PC.

 

[johng1]

Addendum to my previous post. I wondered how the bugs would fare on bigger polygons. I tweaked the program of my earlier post and obtained the following:

Obviously the numbers are starting to get pretty big. The strategy of examining each derangement just is not viable for much bigger polygons. For a regular 30 sided polygon, I have no idea how to proceed.

If anyone is interested, I'll post my tweaked program.