- Thread starter
- #1

- Thread starter leuler
- Start date

- Thread starter
- #1

- Admin
- #2

- Thread starter
- #3

- Thread starter
- #4

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

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:

Code:

```
#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);
}
}
}
```

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.