Le Monde puzzle [#1021]

[This article was first published on R – Xi'an's Og, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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
  remz=1:N;conz=NULL
  while (length(remz)>0){
    seatz=order(-hist(votz[remz,],
    breaks=(0:M)+0.5,plot=FALSE)$density)[1]
    conz=c(conz,seatz);nuremz=NULL
    for (v in remz)
      if (!(seatz%in%votz[v,])) nuremz=c(nuremz,v)
    remz=nuremz}
  solz=length(conz)
#exploration at random
   kandz=matrix(0,N,M)
   for (i in 1:N) kandz[i,votz[i,]]=1
   for (t in 1:1e3){
#random choice of councillors
    zz=sample(c(0,1),M,rep=TRUE)
    while (min(kandz%*%zz)!=1)
      zz=sample(c(0,1),M,rep=TRUE)
    solz=min(solz,sum(zz))
#random choice of remaining councillor per voter
    remz=1:N;conz=NULL
    while (length(remz)>0){
      seatz=sample(votz[remz[1],],1)
      conz=c(conz,seatz);nuremz=NULL
      for (i in remz)
        if (!(seatz%in%votz[i,])) nuremz=c(nuremz,i)
      remz=nuremz}
    solz=min(solz,length(conz))}
maxz=max(solz,maxz)}

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!

Filed under: Books, Kids, R Tagged: binary integer linear programming, competition, Le Monde, linear programming, mathematical puzzle, R

To leave a comment for the author, please follow the link and comment on their blog: R – Xi'an's Og.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)