Combinations - Course choosing

Question

Someone asked me this question:

Suppose there are $n$ students. Each student must choose 4 courses, and every two students can only have a maximum of one common course. How many courses are needed to satisfy this condition?

I tried to convert this into a graph theory problem but failed to figure it out.

I get a bizarre pattern, which I am not 1-- percent sure is correct. Starting with $n=1$, my pattern is $4,7,8,10,10,11,12$ — Sidd Singal, Apr 23 '14 at 16:12
@mathguy I get something different, I get $4,7,9,10,10,11,12$. I don't see how to do it with $8$ in the third step. — G. Bach, Apr 23 '14 at 16:17
@baudolino That fails at $n+1=2$ whether we read it as $(x_n+n)\mod 4$ or as $x_n+(n\mod4)$. — G. Bach, Apr 24 '14 at 15:15

score 0 · Answer 1 · answered Nov 04 '16 at 16:01

I presume that what is wanted is the minimum number of courses needed.

For $n=1\;thru\; 4,$ the pattern is $4,7,9,10$. The pattern for $n=5$ is shown below:

$\boxed{1,2}\;\boxed{1,3}\;\boxed{1,4}\;\boxed{1,5}\;\boxed{2,3}\;\boxed{2,4}\;\boxed{2,5}\;\boxed{3,4}\;\boxed{3,5}\;\boxed{4,5}\;$ and it repeats in cycles of $5$

Let number of courses needed for $(n\;mod\; 5)\;be\; k_i,\; i = 1\; thru\; 4$

Then minimum number of courses needed for $n$ students = $10\times \left[int\left(\dfrac{n}{5}\right)\right] + k_i$

Combinations - Course choosing

1 Answers1