6 persons inside an elevator – algorithm

Prove that if 6 persons are inside  an elevator then there is a subgroup of 3 persons that know each other or a subgroup of 3 persons that don’t know each other. Note: if A  knows B then B also knows A (symmetric relation).

This is a math problem, but I don’t have yet a mathematical solution for it. Thus I wrote an algorithm to show that the above statement indeed holds. The idea is to generate all the possible variants based on the fact that two persons can know each other or not. Then for each variant I check if there is a subgroup of 3 persons that know each other or a subgroup of 3 persons that don’t know each other.

Let’s analyze some numbers before to write the code. There are \binom {6}{2}=15 different pairs of persons which can know each other or not. It follows that there are 2^{15} variants to analyze. For each variant I want to check if any of the subgroups of 3 persons respect one of the conditions: know each other or don’t know each other. For this check I’ll need to generate all the combinations of 3 persons. Their number is: \binom {6}{3}=20.

The code to generate the combinations is called once, at the beginning of the main program, because same combinations can ve reused for each variant:

//store all the combinations
int combinations[20][3];
//curent combination generated by the algorithm
int curentCombination[3];
int curentCombinationNumber=0;
//generate combinations
void comb(int pos, const int& n, const int& k)
{
   if (pos >= k)
   {
      memcpy(combinations[curentCombinationNumber],
      curentCombination, k*sizeof(int));
      curentCombinationNumber++;
      return;
   }
   int start = 1;
   if (pos > 0) start = curentCombination[pos-1]+1;
   for (int v = start; v<= n; v++)
   {
      curentCombination[pos] = v;
      comb(pos+1, n, k);
   }
}

Each variant can be represented as a number from 0 to 2^{15}-1. Digits 1 will correspond to people knowing each other and digits 0 will correspond to people not knowing each other according to the following algorithm (note that <<  is a left shift operation):

//edge[i][j] is the number used for AND bitwise in order
//to check if person i knows person j
int edge[6][6];
int shift = 0;
for (int i = 0; i<6; i++)
   for (int j = i+1; j<6; j++)
   {
   edge[i][j] = (1 << shift);
   shift++;
   }

Based on the combinations and the rule established for “i knows j” the rest of the algorithm is:

//A possibility is represented using the digits in the base 2 of a number
for (int variant = 0; variant < (1<<15); variant++)
{
   bool found = false;
   //search a subgroup that know each other or don;t know each other
   for (int combCount = 0; combCount<20; combCount++)
   {
      //get the persons for this combination
      int a = combinations[combCount][0];
      int b = combinations[combCount][1];
      int c = combinations[combCount][2];
      bool ab = (edge[a][b] & variant) > 0;
      bool bc = (edge[b][c] & variant) > 0;
      bool ac = (edge[a][c] & variant) > 0;
      if ((ab && bc && ac) || (!ab && !bc && !ac)) { found = true; break;}
   }
   if (!found)
   {
      printf("Warning....something is wrong with the algorithm!!");
   }
}

Of course, it never displays: “Warning….something is wrong with the algorithm!!”

Advertisements
This entry was posted in Math. Bookmark the permalink.

One Response to 6 persons inside an elevator – algorithm

  1. Pingback: 6 persons inside an elevator – the math | AlfaNotes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s