Problem 1021
In this country, which is advanced in terms of democracy, municipal elections make it possible to elect councilors in a very particular way in each commune. The size of the municipal council, fixed by decree, depends on that of the municipality. The applications are individual. Once the number of candidates has been validated, it is decided for how many of them each elector is obliged to vote (no blank votes nor null votes are allowed).This choice has its origin in the following rule: after the vote, a summary is made by a computer program that determines the municipal council with a condition that does not suffer any exception: whatever the vote of the voters, each voter will find at least one of the candidates for whom he voted in the council.
In the last election, in the small town where Alice lives, to elect 10 councilors, each voter had to vote for 10 of the 25 candidates.
- 1A. What was, at most, the number of voters in the city of Alice?
- 2A. What was, at least, this number?
This problem has occupied me more than any other problem, perhaps even all the other problems together, the reason being that it is extremely difficult. I did not manage to solve it, but neither did the organizers, and it was not noted.
In the following, we note:
Here is a program that exhaustively enumerates on small values of N and E. The compute_votes_possibles() function builds a 2-dimensional array, in which each line represents a choice of E values among N (implanted in the form of a booleen array). This array therefore has C(N, E) rows (number of combinations of E values among N). The function explore_vote() is then called for increasing values of V until it returns false: in this case, it indicates that whatever the combination of V votes, and whatever the elected candidates, there is at least a vote for which no candidate choice is elected. The explore_vote() function simply enumerates all the possible combinations of votes (there are C(C(N, E), V)) and then checks the constraint in question.
For example, for NB_MAX_ELUS = 6 (maximum value of E), we get: (E varies on one line, N on one column)
Let's look at some of these values in more detail. The case N < 2 × E is trivial and not enumerated (we can just take the first E candidates). Cases N = 2 × E are also easy (E = 2, N = 4, E = 3, N = 6): if there are C(N, E) voters, then all votes are possible, and in this case there is exactly one vote that does not respect the constraint whatever the choice of the elected. If, on the other hand, there are C(N, E) − 1 voters, then all the votes except 1 can be obtained, and in this case, it is enough to choose the candidates which are the complement of those of the missing vote (we can observe that 5 = C(4, 2) − 1 and that 19 = C(6, 3) − 1). For E = 2 and N ≥ 6, we can see that the maximum number of electors is 2, because with 3 voters, there can be totally disjoint votes
. The exhaustive enumeration does not allow to go much further. But we can already see that the designers solution is wrong: here is a program implementing it, for which we find the value of 1358 for the question 1 (E = 10, N = 25). For the values E = 3, N = 7, it is observed that the value obtained by the solution of the designers (10) is different from the value obtained by the exhaustive method (11).
I then tried different techniques (heuristics) to try not to go back on a vote once it is selected (none worked). I present one here: the idea for choosing a new vote is to spread the votes between the candidates w.r.t. the votes already existing. Thus, the notion of similarity between 2 votes is defined as the number of candidates in common among these two votes. When choosing a vote, we look for all possible votes, the similarity with all existing votes, and we choose the one that minimizes the maximum of similarity. If this maximum is reached by several possible votes, we take the one that reaches the minimum the least number of times. Then, if there are still several possible votes, we look at the next maximum by repeating the process.
So, for example, if we consider 5 existing votes and 4 example votes having the following similarities:
1: 2 1 0 1 2
2: 3 1 1 0 1
3: 3 3 0 1 2
4: 0 1 1 2 1
We start by sorting the possible votes by their similarity, to obtain:
1: 0 1 1 2 2
2: 0 1 1 1 3
3: 0 1 2 3 3
4: 0 1 1 1 2
Then we go through the columns (starting from the right), and we eliminate the possible votes when their similarity is not equal to the minimum. In this example, there remain the votes 2 and 4 when we look at the last column, after which only the possible vote 4 is retained.
Finally, when the number of existing votes is small, several possible votes have the same similarities. We then choose one at random. Nevertheless, one realizes quite quickly that this does not work and gives a very rough upper bound of the number of voters (for example, for E = 3 and N = 7, I found 17 instead of 11).
We can also see on a very simple example why it does not work. Consider the case with E = 2 and N = 5. The exhaustive search tells us that the maximum number of voters is 3, while the heuristic above gives 4. Consider the two sets of 4 votes below: on the left, a example that shows that 4 voters is not possible, and on the right, the case built by the presented heuristic.
We see that the two 4th votes have the same similarity (1 0 1 and 1 1 0), but the one on the right admits a solution (candidates 1 and 3) unlike the one on the left. I did not find a criterion differentiating these two figures.
We can also recursively explore all the possible votes with the minimum similarity when there are several (this assumes that the optimal solution meets this criterion even if it is no longer the only one, but it is not even sure), but the calculations explode completely from a combinatorial point of view (this is even worse than the exhaustive one). One could probably find quite close bounds by randomly testing a few votes at the top of the exploration tree. The code is here.
In the following, we note:
- N : the number of candidates
- E : the number of persons in the council
- H : the number of votes on a ballot
- V : the number of voters
Here is a program that exhaustively enumerates on small values of N and E. The compute_votes_possibles() function builds a 2-dimensional array, in which each line represents a choice of E values among N (implanted in the form of a booleen array). This array therefore has C(N, E) rows (number of combinations of E values among N). The function explore_vote() is then called for increasing values of V until it returns false: in this case, it indicates that whatever the combination of V votes, and whatever the elected candidates, there is at least a vote for which no candidate choice is elected. The explore_vote() function simply enumerates all the possible combinations of votes (there are C(C(N, E), V)) and then checks the constraint in question.
For example, for NB_MAX_ELUS = 6 (maximum value of E), we get: (E varies on one line, N on one column)
Max voters for given values of N and E:
0 1 2 3 4 5
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
0 | . . . . . .
1 | . . . . . .
2 | . . . . . .
3 | . . -1 . . .
4 | . . 5 -1 . .
5 | . . 3 -1 -1 .
6 | . . 2 19 -1 -1
7 | . . 2 11 -1 -1
0 1 2 3 4 5
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
0 | . . . . . .
1 | . . . . . .
2 | . . . . . .
3 | . . -1 . . .
4 | . . 5 -1 . .
5 | . . 3 -1 -1 .
6 | . . 2 19 -1 -1
7 | . . 2 11 -1 -1
Let's look at some of these values in more detail. The case N < 2 × E is trivial and not enumerated (we can just take the first E candidates). Cases N = 2 × E are also easy (E = 2, N = 4, E = 3, N = 6): if there are C(N, E) voters, then all votes are possible, and in this case there is exactly one vote that does not respect the constraint whatever the choice of the elected. If, on the other hand, there are C(N, E) − 1 voters, then all the votes except 1 can be obtained, and in this case, it is enough to choose the candidates which are the complement of those of the missing vote (we can observe that 5 = C(4, 2) − 1 and that 19 = C(6, 3) − 1). For E = 2 and N ≥ 6, we can see that the maximum number of electors is 2, because with 3 voters, there can be totally disjoint votes
. The exhaustive enumeration does not allow to go much further. But we can already see that the designers solution is wrong: here is a program implementing it, for which we find the value of 1358 for the question 1 (E = 10, N = 25). For the values E = 3, N = 7, it is observed that the value obtained by the solution of the designers (10) is different from the value obtained by the exhaustive method (11).
I then tried different techniques (heuristics) to try not to go back on a vote once it is selected (none worked). I present one here: the idea for choosing a new vote is to spread the votes between the candidates w.r.t. the votes already existing. Thus, the notion of similarity between 2 votes is defined as the number of candidates in common among these two votes. When choosing a vote, we look for all possible votes, the similarity with all existing votes, and we choose the one that minimizes the maximum of similarity. If this maximum is reached by several possible votes, we take the one that reaches the minimum the least number of times. Then, if there are still several possible votes, we look at the next maximum by repeating the process.
So, for example, if we consider 5 existing votes and 4 example votes having the following similarities:
1: 2 1 0 1 2
2: 3 1 1 0 1
3: 3 3 0 1 2
4: 0 1 1 2 1
We start by sorting the possible votes by their similarity, to obtain:
1: 0 1 1 2 2
2: 0 1 1 1 3
3: 0 1 2 3 3
4: 0 1 1 1 2
Then we go through the columns (starting from the right), and we eliminate the possible votes when their similarity is not equal to the minimum. In this example, there remain the votes 2 and 4 when we look at the last column, after which only the possible vote 4 is retained.
Finally, when the number of existing votes is small, several possible votes have the same similarities. We then choose one at random. Nevertheless, one realizes quite quickly that this does not work and gives a very rough upper bound of the number of voters (for example, for E = 3 and N = 7, I found 17 instead of 11).
We can also see on a very simple example why it does not work. Consider the case with E = 2 and N = 5. The exhaustive search tells us that the maximum number of voters is 3, while the heuristic above gives 4. Consider the two sets of 4 votes below: on the left, a example that shows that 4 voters is not possible, and on the right, the case built by the presented heuristic.
We see that the two 4th votes have the same similarity (1 0 1 and 1 1 0), but the one on the right admits a solution (candidates 1 and 3) unlike the one on the left. I did not find a criterion differentiating these two figures.
We can also recursively explore all the possible votes with the minimum similarity when there are several (this assumes that the optimal solution meets this criterion even if it is no longer the only one, but it is not even sure), but the calculations explode completely from a combinatorial point of view (this is even worse than the exhaustive one). One could probably find quite close bounds by randomly testing a few votes at the top of the exploration tree. The code is here.
- 1A. 1358. The city of Alice has a maximum population of 1358 inhabitants.
Let E1 be the number of voters, each voting for 10 candidates. Thus, the total number of votes is 10E1.
Since there are 25 candidates in total, the number of votes of the candidate C1 who obtains the most votes is greater than or equal to 10E1 / 25. At least 40% of the electors (rounded to the next integer V1) are therefore satisfied by his election.
Reasoning is repeated for voters who did not vote for C1 (they are at most E2 = E1 - V1), and whose votes are shared by 24 candidates. The C2 candidate elected by them gets at least V2 votes (V2 ≥ 10E2 / 24), which satisfies in all V1 + V2 voters.
We continue iteratively to satisfy all voters. This will be the case after a finite number of operations. But it has to be in 10 steps at most, since only 10 councilors are elected. We show that this is the case when E1 ≤ 1358, but it is no longer safe from 1359 electors where a distribution of votes only satisfies all voters with 11 elected. - 2B. 14. The number of votes for each voter in Bob's city must be 14 to satisfy the requirement.
In the city of Bob, we operate in the same way starting from E1 = 55,555 and substituting 25 by 33. We can see that the more votes each elector receives, the more steps that follow. everyone will be satisfied (so the minimum number of elected) decreases. Thus, with 13 votes, we have to wait until the fifteenth elected to satisfy everyone.
The two numbers meet with 14 votes (and 14 elected).