Ten employees of an organization worked on an assignment wherein a total of 'n' presentations were prepared. It is known that each presentation was prepared by five employees among the ten and each pair of employees prepared the same number of presentations. Find the smallest possible value of 'n'.
Ten employees, $n$ presentations, ..., find smallest possible value of $n$
-
0@ Gerry Sure I would do that. – 2012-05-29
2 Answers
Keep a counter that increases by 1 each time an employee contributes to a presentation. In other words, it increases by 5 for each presentation. The question says that 'each pair of employees prepared the same number of presentations'. In other words, all employees prepared the same number of presentations. Let this number be x. 10x=5n. We don't know x, but we do know n. So the condition is that 10 must divide 5n. You can easily check that 2 is the least n which satisfies this. In this case, it is easy to check that this happens when 5 employees work on one presentation and the remaining 5 work on the other one.
EDIT: As noted, we want each pair working together in the same number of presentations, not just generally. First note that all employees must still occur in same number of presentations else pairs that have them will be disadvantaged. So 2 must still divide n. Additionally, if we look at the n/2 pairs where we have a given employee, say a1, look at the 4(n/2) places left in these. They must be equally distributed among the other 9 employees. So 9 must divide 4(n/2) = 2n. In other words, 2 divides n and 9 divides 2n implies that 18 must divide n. This surely necessary, to see it is sufficient we only need to look at how the presentation which involve a given employee look. If we can do this, then we can do the rest by symmetry. Now, number the employees from 1 to 10. We will try to make 9 presentations that satisfy the condition for 1. Easily done like this:
1 2 3 4 5
1 2 3 9 10
1 2 4 8 9
1 2 5 8 10
1 3 4 7 9
1 3 5 6 7
1 4 5 6 10
1 6 7 8 10
1 6 7 8 9
Extending just this seems to be a bit hard because even within this the pairs of eg. 6 and 7 should be somewhat balanced, but the following distribution seems to work:
1 2 4 6 9
1 2 5 7 10
1 2 6 7 8
1 2 3 8 10
1 3 5 7 9
1 3 5 9 10
1 3 4 6 8
1 4 5 7 8
1 4 6 9 10
2 3 5 7 9
2 3 5 6 9
2 3 4 8 9
2 4 5 7 10
2 4 6 8 10
2 4 6 8 10
3 4 6 8 10
3 6 7 8 10
4 5 7 8 9
5 6 7 9 10
-
0You've repeated 2,4,6,8,10. I haven't checked whether it works out after you delete one of those. – 2012-05-30
I think you're trying to construct a balanced incomplete block design. In the notation of the Wikipedia essay, your set $X=\{{1,2,3,4,5,6,7,8,9,10\}}$ has $v=10$ points (the employees), your blocks have $k=5$ points each (5 employees per presentation), and you want to minimize $b$, the number of blocks (which you're calling $n$). Necessary (but not sufficient) conditions are $bk=vr$ (where $r$ is the number of presentations each employee works on) and $\lambda(v-1)=r(k-1)$ (where $\lambda$ is the number of presentations any given pair of employees works on). Also, $b\ge v$.
For us, that's $5b=10r$, $9\lambda=4r$, and $b\ge10$. The smallest numbers that work here are $b=18$, $r=9$, $\lambda=4$; 18 presentations, each employee works on 9, each pair of employees works on 4. These are the same numbers as in Wonder's answer. If you or Wonder can construct a BIBD with those parameters, then that's the answer - but, as noted, these are necessary but not sufficient conditions.
There are tabulations of BIBDs available online, if you search for the keywords I've used.
EDIT: Here is a database of $t$-designs. If you go down to the line that starts 2 10 18 9 5 4 and click on "download", you will get two solutions to the problem. I'll write one of them out without any attempt to format nicely:
01257, 01349, 01468, 01679, 02347, 02389, 02456, 03578, 05689, 12368, 12459, 12789, 13458, 13567, 23569, 24678, 34679, 45789.