Friday, September 28, 2012

Problem #2 - How big is this Group ?

Don't worry, it's nothing about Group Theory. The following is an interesting combinatorics problem that I got few moments ago from one of my friend, Leonardo

"If every week $5$ person from a group are to meet with each other and they are assigned such that a person $x$ need to attend the meeting at most once a month and he/she will not see the same people ( either of the people) from previous meeting for at least $3$ months, what is the minimum number of the people in such group?" (1 month = 4 weeks)

Some clarification :
- If $A$ attends a meeting at week $W$, he can only attend again at least at week $W+4$ (so not only once a month)
- If both $A$ and $B$ meet at a meeting in week $W$, they can only meet again at week $W+13$

One simple fact is the group must have 20 distinct people to be assigned into 4 weeks of the first month (5 people each). The challenge is to find the minimum number of people in such group. Equivalently, if that minimum number is $N$, there will be no configurations satisfying the requirements in the problem with $N-1$ people.

See Solution

2 comments:

  1. If "once a month" is really once a month, this question is easy and the answer is $25$, haha =p
    $\begin{tabular}{ccccc}
    1 & 2 & 3 & 4 & 5\\
    6 & 7 & 8 & 9 & 10\\
    11 & 12 & 13 & 14 & 15\\
    16 & 17 & 18 & 19 & 20\\\hline
    1 & 6 & 11 & 16 & 21\\
    2 & 7 & 12 & 17 & 22\\
    3 & 8 & 13 & 18 & 23\\
    4 & 9 & 14 & 19 & 24\\\hline
    5 & 10 & 15 & 20 & 25\\
    1 & 7 & 13 & 19 & 25\\
    2 & 8 & 14 & 20 & 21\\
    3 & 9 & 15 & 16 & 22\\\hline
    4 & 10 & 11 & 17 & 23\\
    5 & 6 & 12 & 18 & 24\\
    1 & 8 & 15 & 17 & 24\\
    2 & 9 & 11 & 18 & 25\\\hline
    3 & 10 & 12 & 19 & 21\\
    4 & 6 & 13 & 20 & 22\\
    5 & 7 & 14 & 16 & 23\\
    1 & 9 & 12 & 20 & 23\\\hline
    2 & 10 & 13 & 16 & 24\\
    3 & 6 & 14 & 17 & 25\\
    4 & 7 & 15 & 18 & 21\\
    5 & 8 & 11 & 19 & 22\\\hline
    1 & 10 & 14 & 18 & 22\\
    2 & 6 & 15 & 19 & 23\\
    3 & 7 & 11 & 20 & 24\\
    4 & 8 & 12 & 16 & 25\\\hline
    5 & 9 & 13 & 17 & 21
    \end{tabular}$

    ReplyDelete
  2. haha yup, btw somehow tabular can't work with that comment hm.. let me find out how to write those in here..

    ReplyDelete