# 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[1]);
        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