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

Home > General
Elections in Graphistan (Posted on 2020-02-14) Difficulty: 3 of 5
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.

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.)
re: First thoughts | Comment 2 of 4 |
(In reply to First thoughts by tomarken)

Part a) Each candidate must be on the debate stage with 19 other candidates, across all the debates.  If a candidate was in only 2 debates, them he would be debating at most 18 other candidates.  Therefore, each candidate must be in at least 3 debates.  Therefore, a lower bound on the minimum number of debates is 6.  (20*3/10).  And Tomarken has demonstrated that 6 is possible.

Part b) By a parallel argument, 6 is a lower bound on the minimum number of debates.  Not sure if it is achievable.

  Posted by Steve Herman on 2020-02-14 16:29:29
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information