### # Hat-Check problem

Introduction

A couple of days ago we did the santa secret ('amigo invisible').
We wrote each name in a small paper and put them in a box.
Each participant had to take one small paper from the box.
We repeated the draw five times before to obtain a name different than our own.

What is the probability that each one obtain a different name?

The response has a limit in 1/e (Euler's number) and exists a similar probability game (the hat-check problem).

I found the hat-check problem after write a C program and observe that the result is similar beyond five friends/hats.

C program

```# `cat hat_game.c`
#include <stdio.h>
#include <stdlib.h>

unsigned int *hats;
unsigned int favorable;
unsigned int possible;
unsigned int max;

void init(){
unsigned int i;
favorable=0;
possible=1;
hats=(unsigned int *)malloc(max*sizeof(unsigned int));
for(i=0;i<max;i++){
possible*=i+1;
}
}

void end(){
float probability;
free(hats);
printf("\n");
printf("favorable   = %u\n",favorable);
printf("possible    = %u\n",possible);
probability=(float)favorable/possible;
printf("probability = favorable/possible = %.10f\n\n",probability);
}

int exists(unsigned int num,unsigned top){
unsigned int i;
for(i=0;i<top;i++){
if(hats[i]==num){return 1;}
}
return 0;
}

void print_result(){
unsigned int i;
printf("======> ");
for(i=0;i<max;i++){
printf("%u ",hats[i]);
}
printf("\n");
}

int hat_game(int min){
unsigned int i,j;
for(i=min;i<min+1;i++){
for(j=0;j<max;j++){
if((i!=j)&&(exists(j,i)==0)){
hats[i]=j;
if(i==max-1){
//print_result(max);
favorable++;
return 0;
}else{
hat_game(i+1);
}
}
}
}
}

int main(int argc, char *argv[]){
max=atoi(argv);
init();
hat_game(0);
end();
return 0;
}
# `gcc -O3 -march=native -o hat_game hat_game.c`
# `./hat_game 10`

favorable   = 1334961
possible    = 3628800
probability = favorable/possible = 0.3678794503```

References

http://www.proofwiki.org/wiki/Hat-Check_Problem
http://en.wikipedia.org/wiki/Derangement