## 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 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

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