# combinatorics question from the real world

This is a real world scenario - please help. My brain hurts and I can't figure it out on my own.

Suppose I host an event with the following constraints

• There will be exactly 5 lectures
• There will be exactly 125 participants
• Each participant has signed up for exactly 3 mandatory, unique lectures (so each lecture has exactly 75 participants)
• There are exactly 5 rooms available, each room holds 25 people (so each lecture has to be held at least 3 times)

Assuming a lecture will last one hour (including pauses), will I be able to finish the event in 3 hours? How do I calculate this?

Thanks for your help...I need it :-)

-
"Each participant has signed up for exactly 3 mandatory, unique lectures (so each lecture has exactly 75 participants)" What if all participants signed up in the first 3 lectures and lectures have such numbers of participants - 125, 125, 125, 0, 0? Or I misunderstood and they is additional constraint about exactly 75 participants in every lecture? – zaarcis Feb 18 '13 at 17:54
If someone solves this problem, will they be invited to the event? – Asaf Karagila Feb 18 '13 at 17:55
@AsafKaragila Nice joke. – Harald Hanche-Olsen Feb 18 '13 at 17:58
@zaarcis Remember, a lecture requires a room, which only holds 25 people. The lectures are only held 3 times (unique) so only 75 people can take a given lecture. – Alexander Gruber Feb 18 '13 at 17:59
Damn, my brain buggy. @AlexanderGruber, it seems you're right. – zaarcis Feb 18 '13 at 18:00

Suppose that lecture 1 takes place in room 1, lecture 2 in room 2, etc. and the lectures do not change rooms between hours.

Suppose that persons 1 through 25 go to lecture 1 the first hour, 26 through 50 go to lecture 2 the first hour, etc. Then persons 1 through 25 go to lecture 2 the second hour, persons 26 through 50 go to lecture 3, and persons 101 - 125 go to the lecture 1. Third hour, we rotate again: 1 through 25 go to lecture 3, 26-50 to lecture 4, etc. Everybody has gone to 3 unique lectures and all lectures have been held with three sets of 25 distinct participants.

So a solution exists.

We can use that to consider the general case: all that matters is that the set of people is different for each lecture. If you've capped the signup at 75 per lecture, you can schedule the people in these groups of 25 for the first hour, then permute the people between different groups for the next hour. The labels 1 through 25 are arbitrary, so you can make them whatever you want, just as long as they're different.

-
Thanks for your answer Alexander. This seems plausible. Accepted! – sustainablepace Feb 19 '13 at 12:56

You can hold each lecture at each hour for three hours. This will allow you to finish the event in 3 hours, but you will have to add the following constraints:

• Each lecture can only be attended by 75 participants. Thus, some participants may not get to attend the first three choices.

• There can only be 25 people to attend each lecture each hour. This may result in participants having further difficulties in attending their three favorite lectures.

If you allow open registration on a first come - first serve basis, limit each person to reigstering for only one lecture per hour and make sure to cap enrollment in each lecture at 25 people, then you will be guaranteed to have everyone signed up for three lectures. But keep in mind that, for example, the last person to register will not have any choice, he will have to take the one remaining lecture slot at each hour. So it is possible that he will attend the lectures that he ranks #3, #4 and #5.

-
Thanks for your answer Michael. Very much appreciated. Alexander's answer below had a little more meat for me, so I accepted his answer. But I will upvote your answer as well once I have enough points. – sustainablepace Feb 19 '13 at 12:58