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?
(In reply to
re: First thoughts by Steve Herman)
Steve H's lower bound to the minimum number of debates that are needed is certainly solid, but most interesting is the question of achievability.
Consider the problem of 4 candidates total, with debates of 3 persons at a time. The lower limit is then 2 debates to assure each candidate meets 3 others, and yet, this is unachievable with 2 debates. Three are needed.
A geometrical way to think of this is that the four candidates are the vertices of a square which has 6 lines total when the diagonals are included. The debates are triangles, and you can not cover all 6 lines with two triangles.
To broaden the analogy: n candidates make a polygon of n sides with n(n-1)/2 lines with the diagonals included. Finding the minimum required number of m-person debates means finding the set of m-sided polygons made from a subset of the n points that cover all the lines. Sometimes it is S.H.'s minimum, sometimes not. I have started a table... I think the achievable minimum number is to be found under the study of polygrams and factorization within modulus n, but, I certainly have not found the solution.
Edited on February 16, 2020, 8:05 am
re(2): First thoughts
