4
$\begingroup$

There are 20 meetings. each neeting has 8 attendees. However, no pair of attendees appear more than once. What is the minimum number of people? To be more specific once a specific pair of people appear in a meeting, this pair will not appear again in any of the other meetings.

My soluton 8C2=28 So there are at leat 28×20=560 distinct pairs Minimum number of people for there to be 560 distinct pairs= 34 But textbook ans is 35???

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or closed. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$ Mar 13, 2021 at 7:41
  • 1
    $\begingroup$ Your textbook answer is wrong; the correct answer is $49$. What book is that? $\endgroup$
    – user14111
    Feb 20 at 0:31

2 Answers 2

1
$\begingroup$

As you calculated, the 20 meetings generate 560 pairs of people, and each pair can only appear once in all meetings. Imagine that there was a solution with only 34 people, resulting in 561 possible pairs of people. Then apart from one pair $(p_1,p_2)$, each pair should appear exactly once. This means that there certainly is one person (for example $p_3$) who had meetings with every of the 33 other persons.
However, the meetings of $p_3$ should now partition all 33 people in groups of 7, but clearly this is impossible since 7 doesn't divide 33.

Of course, this reasoning does not imply that a schedule could effectively be made with 35 people.

$\endgroup$
1
  • $\begingroup$ The Johnson bound implies that for $35$ people the number of meetings is at most $$\left\lfloor\frac{35}{8}\left\lfloor\frac{34}{7}\right\rfloor\right\rfloor = 17.$$ $\endgroup$
    – RobPratt
    Feb 26 at 22:10
1
$\begingroup$

The correct answer is $49$.

Such a configuration of meetings is impossible if there are only $48$ people. Let $n_i$ be the number of meetings attended by the $i^\text{th}$ person; so $\sum_{i=1}^{48}n_i=20\cdot8=160$. Since no two people attend the same two meetings, we must have $$\sum_{i=1}^{48}\binom{n_i}2\le\binom{20}2=190.\tag1$$ Now the quantity $\sum_{i=1}^{48}\binom{n_i}2$ is minimized, subject to the constraint $\sum_{i=1}^{48}n_i=160$, when the natural numbers $n_i$ are as nearly equal as possible, i.e., they are all $3$ or $4$, so we have $$\sum_{i=1}^{48}\binom{n_i}2\ge32\binom32+16\binom42=192\gt190=\binom{20}2$$ contradicting $(1)$.

With $49$ people we can even have $21$ meetings with each meeting attended by $8$ people and no two people meeting together more than once. To see this, consider the projective plane $\mathrm{PG}(2,7)$; it has $57$ points and $57$ lines, $8$ points on each line and $8$ lines through each point, any two lines intersecting in just one point. If we regard the points as "people" and the lines as "meetings", we have $57$ people and $57$ meetings. Now let $\Omega$ be a set of $8$ points such that no three are collinear; such a set exists and is called an oval. By the in-and-out formula, the number of lines incident with at least one point of $\Omega$ is $\binom81\cdot8-\binom82\cdot1=36$. Thus there are $57-36=21$ lines/meetings among the $57-8=49$ points/people not in $\Omega$.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .