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