All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Elections in Graphistan (Posted on 2020-02-14)
In this year's presidential election of Graphistan, 20 nominees compete for the position of head of state. It is your job to schedule a series of public debates between them on national television. There are some constraints you must consider:

1. We do not want it too crowdy, so at most 10 contenders may appear in the same TV show.

2. It is an accepted custom, that candidates shall not attack anyone who is absent. Therefore, ensure that every pair of candidates appears in at least one show together.

Questions:
a) How can you schedule the events with the minimum number of shows?

b) What if there are 22 candidates and the limit is raised to 11 candidates per show?

 No Solution Yet Submitted by JLo Rating: 3.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 First thoughts | Comment 1 of 5
At first glance, it seems we need to create a total of 20 * 19 / 2 = 190 total pairs meeting.  In a single debate we can add at most a total of 10 * 9 / 2 = 45 new pairs.  So we'd need at least 5 debates to ensure every possible pair of candidates has shared a stage.

It seems easy enough to cover all possible pairs with 6 debates, e.g.:

Debate 1: Candidates 1 - 10
Debate 2: Candidates 11 - 20
Debate 3: Candidates 1 - 5 & 11 - 15
Debate 4: Candidates 6 - 10 & 11 - 15
Debate 5: Candidates 1 - 5 & 16 - 20
Debate 6: Candidates 6 - 10 & 16 - 20

Not sure if there's a way to condense that into 5 debates, though.

 Posted by tomarken on 2020-02-14 08:59:30

 Search: Search body:
Forums (0)