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!