Le Monde puzzle [#1021]

A puzzling Le Monde mathematical puzzle for which I could find no answer in the allotted time!:

A most democratic electoral system allows every voter to have at least one representative by having each of the N voters picking exactly m candidates among the M running candidates and setting the size n of the representative council towards this goal, prior to the votes. If there are M=25 candidates, m=10 choices made by the voters, and n=10 representatives, what is the maximal possible value of N? And if N=55,555 and M=33, what is the minimum value of n for which m=n is always possible?

I tried a brute force approach by simulating votes from N voters at random and attempting to find the minimal number of councillors for this vote, which only provides an upper bound of the minimum [for one vote], and a lower bound in the end [over all votes]. Something like

for (i in 1:N) votz[i,]=sample(1:M,n)
#exploration by majority
  while (length(remz)>0){
    for (v in remz)
      if (!(seatz%in%votz[v,])) nuremz=c(nuremz,v)
#exploration at random
   for (i in 1:N) kandz[i,votz[i,]]=1
   for (t in 1:1e3){
#random choice of councillors
    while (min(kandz%*%zz)!=1)
#random choice of remaining councillor per voter
    while (length(remz)>0){
      for (i in remz)
        if (!(seatz%in%votz[i,])) nuremz=c(nuremz,i)

which leads to a value near N=4050 for the first question, with 0% confidence… Obviously, the problem can be rephrased as a binary integer linear programming problem of the form

n= \max_A \min_{c;\,\min Ac=1}\mathbf{1}^\text{T}c

where A is the NxM matrix of votes and c is the vector of selected councillors. But I do not see a quick way to fix it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.