5
$\begingroup$

My high school is celebrating 30 years since graduating its first class and is planning to invite for lunch 20 alumni, 600 in all, from each of those classes.

Hosts are planning to sit everyone in tables with the same number of alumni. They also wish to make sure that for any two classes, say years X and Y, at least one student from each of those two classes sit together in at least one of the tables.

For social distancing purposes, it is also desired to sit as few alumni as possible in each table.

How few can that be?

Improve this question
$\endgroup$
3
  • $\begingroup$ A lower bound of $3$ is easy to prove and I believe it's the answer. The remaining problem is the following: given $30$ people, each day we divide them into $10$ groups of three, is it possible that within $20$ days any two people has been put into the same group at least for one day? I believe the answer is "yes" but didn't find a simple construction. $\endgroup$
    – WhatsUp
    Commented Sep 28, 2021 at 21:55
  • $\begingroup$ Here's an algorithm for Steiner Triple Systems: mathoverflow.net/questions/72084/… $\endgroup$
    – Dr Xorile
    Commented Sep 28, 2021 at 22:08
  • $\begingroup$ That doesn't entirely solve it though, given the other constraints... $\endgroup$
    – Dr Xorile
    Commented Sep 28, 2021 at 22:33

1 Answer 1

Reset to default
5
$\begingroup$

If the number of people per table is $p$, then to cover each pair we must have $$\frac{600}{p} \binom{p}{2} \ge \binom{30}{2},$$ which implies that $p \ge \lceil 49/20 \rceil = 3$. The following set of $200$ triples of years covers every pair and contains each year exactly $20$ times:

{{1,2,22},{1,3,5},{1,3,7},{1,4,20},{1,6,8},{1,7,15},{1,9,10},{1,11,12},{1,11,22},{1,12,13},{1,12,
21},{1,14,17},{1,14,18},{1,14,19},{1,16,18},{1,23,25},{1,24,29},{1,25,28},{1,26,29},{1,27,30},{2,3
,15},{2,4,23},{2,5,20},{2,6,26},{2,7,24},{2,7,25},{2,7,27},{2,7,30},{2,8,29},{2,9,28},{2,10,28},{2
,11,25},{2,11,28},{2,12,23},{2,13,24},{2,14,30},{2,15,18},{2,16,21},{2,17,19},{3,4,13},{3,6,28},{3
,8,28},{3,9,21},{3,10,18},{3,11,29},{3,12,20},{3,12,25},{3,14,15},{3,14,28},{3,15,16},{3,17,23},{3
,19,20},{3,22,30},{3,24,28},{3,26,28},{3,27,29},{4,5,23},{4,6,13},{4,6,17},{4,7,21},{4,8,13},{4,9,
25},{4,10,29},{4,11,27},{4,12,14},{4,15,16},{4,18,25},{4,18,29},{4,19,23},{4,21,22},{4,21,30},{4,
24,26},{4,28,30},{5,6,12},{5,7,10},{5,8,15},{5,8,16},{5,9,20},{5,10,20},{5,11,21},{5,13,28},{5,14,
25},{5,15,21},{5,15,27},{5,16,22},{5,16,27},{5,17,18},{5,19,30},{5,21,26},{5,24,29},{6,7,22},{6,9,
16},{6,10,15},{6,10,26},{6,10,29},{6,11,30},{6,14,23},{6,14,27},{6,16,25},{6,18,27},{6,19,23},{6,
20,26},{6,21,23},{6,24,25},{7,8,28},{7,9,10},{7,9,30},{7,11,21},{7,12,23},{7,13,29},{7,14,22},{7,
15,20},{7,16,17},{7,18,19},{7,22,26},{8,9,25},{8,10,12},{8,11,19},{8,11,21},{8,12,24},{8,14,24},{8
,15,19},{8,16,26},{8,17,25},{8,18,20},{8,18,30},{8,22,24},{8,23,27},{9,11,17},{9,12,15},{9,13,15},
{9,13,27},{9,14,21},{9,17,30},{9,18,22},{9,19,27},{9,20,26},{9,23,29},{9,24,26},{10,11,25},{10,12,
14},{10,13,14},{10,13,22},{10,16,30},{10,17,21},{10,18,24},{10,19,27},{10,23,29},{11,13,27},{11,14
,23},{11,15,23},{11,16,18},{11,20,30},{11,24,30},{11,26,27},{12,14,18},{12,14,26},{12,16,22},{12,
16,29},{12,17,30},{12,19,20},{12,27,28},{13,15,22},{13,16,18},{13,17,27},{13,19,20},{13,19,26},{13
,21,27},{13,23,30},{13,25,30},{14,16,20},{14,19,29},{15,17,25},{15,21,24},{15,26,30},{15,28,29},{
16,17,24},{16,19,28},{16,22,23},{17,18,21},{17,20,21},{17,20,24},{17,22,30},{17,23,28},{17,26,29},
{18,23,24},{18,24,29},{18,26,28},{19,21,28},{19,22,28},{19,24,25},{19,24,27},{20,22,28},{20,23,26}
,{20,25,27},{20,26,29},{21,25,29},{22,25,26},{22,25,27},{22,29,30}}

The pair $\{3,28\}$ appears $5$ times. For a more balanced coverage, with each pair appearing at most twice, use:

{{1,2,3},{1,3,6},{1,4,5},{1,4,17},{1,5,26},{1,6,7},{1,8,9},{1,9,18},{1,10,11},{1,12,13},{1,14,15},
{1,16,24},{1,16,30},{1,17,21},{1,18,24},{1,19,27},{1,20,26},{1,22,25},{1,23,29},{1,28,30},{2,4,6},
{2,5,7},{2,5,23},{2,7,27},{2,8,10},{2,8,17},{2,9,11},{2,10,22},{2,12,22},{2,13,15},{2,14,24},{2,15
,19},{2,16,20},{2,16,28},{2,18,25},{2,21,27},{2,23,26},{2,24,28},{2,29,30},{3,4,7},{3,5,19},{3,5,
21},{3,8,11},{3,9,10},{3,12,15},{3,12,26},{3,13,14},{3,13,29},{3,16,23},{3,17,22},{3,18,20},{3,18,
23},{3,19,30},{3,20,28},{3,24,26},{3,25,27},{3,25,30},{4,6,24},{4,8,12},{4,9,13},{4,10,14},{4,11,
16},{4,11,21},{4,12,30},{4,13,26},{4,15,21},{4,18,27},{4,19,26},{4,20,22},{4,20,25},{4,22,28},{4,
23,27},{4,23,29},{5,6,25},{5,7,20},{5,8,13},{5,9,12},{5,9,24},{5,10,15},{5,11,14},{5,11,22},{5,16,
27},{5,17,20},{5,18,30},{5,21,29},{5,23,28},{5,27,28},{6,8,24},{6,9,15},{6,10,12},{6,11,13},{6,13,
21},{6,14,21},{6,15,27},{6,16,17},{6,17,23},{6,18,19},{6,19,22},{6,20,29},{6,22,30},{6,26,27},{6,
28,30},{7,8,21},{7,9,14},{7,10,13},{7,11,23},{7,12,28},{7,15,18},{7,15,24},{7,16,25},{7,16,30},{7,
17,26},{7,18,28},{7,19,30},{7,20,23},{7,22,27},{7,24,29},{8,9,29},{8,10,26},{8,13,22},{8,14,20},{8
,15,25},{8,15,28},{8,16,19},{8,17,23},{8,18,21},{8,18,29},{8,24,25},{8,27,30},{9,10,30},{9,14,24},
{9,15,28},{9,16,26},{9,17,19},{9,20,22},{9,21,23},{9,21,25},{9,22,29},{9,27,28},{10,11,25},{10,13,
24},{10,16,29},{10,17,20},{10,17,27},{10,18,22},{10,19,29},{10,21,26},{10,21,28},{10,23,25},{11,12
,20},{11,12,27},{11,15,26},{11,16,18},{11,17,27},{11,19,23},{11,19,28},{11,20,30},{11,24,25},{11,
26,29},{12,14,23},{12,16,21},{12,17,28},{12,18,26},{12,19,24},{12,21,30},{12,22,29},{12,24,27},{12
,25,29},{13,16,17},{13,17,25},{13,18,23},{13,19,21},{13,19,26},{13,20,27},{13,25,28},{13,29,30},{
14,15,19},{14,16,18},{14,16,27},{14,17,29},{14,18,25},{14,19,25},{14,20,21},{14,22,30},{14,26,28},
{14,28,29},{15,16,22},{15,16,23},{15,17,30},{15,20,25},{15,27,29},{17,18,24},{17,18,29},{19,20,24}
,{19,20,28},{21,22,24},{21,22,26},{22,23,26},{23,24,30},{25,26,30}}
Improve this answer
$\endgroup$
4
  • $\begingroup$ Can you sketch the algorithm you used to generate this? $\endgroup$
    – Dr Xorile
    Commented Sep 29, 2021 at 0:21
  • 2
    $\begingroup$ I used integer linear programming, with a binary decision variable for each of the $\binom{30}{3}=4060$ possible triples, a linear $\ge 1$ constraint for each pair, and a linear $=20$ constraint for each year. $\endgroup$
    – RobPratt
    Commented Sep 29, 2021 at 0:23
  • $\begingroup$ @RobPratt I wonder: What are the fewest and most alumni the school can invite from each of the classes (the same number from each class) so that 3 remains the least number that can be fitted in a single table. And are all values in between possible? $\endgroup$
    – Bernardo Recamán Santos
    Commented Sep 29, 2021 at 20:16
  • 1
    $\begingroup$ Let $k$ be the number per class. Then we must have $\frac{30k}{p}\binom{p}{2} \ge \binom{30}{2}$, equivalently, $k(p-1) \ge 29$, so $k<29 \implies p \ge 3$. Also, $p=3$ implies $k \ge 15$. It turns out that all $k\in\{15,\dots,28\}$ yield a minimum of $3$ per table. For $k=29$, the minimum per table is $2$ (one table for each pair of years). $\endgroup$
    – RobPratt
    Commented Sep 29, 2021 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.