Le Monde puzzle [#1015]

A combinatoric Le Monde mathematical puzzle:

A game with N questions and N players is such that each question is solved by all players but three, while any pair of players fails to jointly solve the N questions. What is the maximal number N of players?

N=6;play=1;besz=1
while ((besz>0)||(play<N)){
gamz=matrix(1,N,N)
for (qez in 1:N) gamz[qez,sample(1:N,3)]=0
besz=0;play=1
while ((play<N)&(besz==0)){
besz=max(apply(as.matrix(gamz[,play]+
  gamz[,(play+1):N],ncol=N-play),2,prod))
play=play+1}
}

The output of that code is N=7 in that N=8 does not escape the while loop. (Since there are 3N zeros to distribute in the NxN matrix, either all columns contain 3 zeros or one contains only two, in which case it can only share zeros with 2×2=4 other columns, which makes it impossible. When a column holds three zeros, it can share zeros with 3×2=6 other columns, which brings us back to N=7 as the highest possible case.)

A second game with M>N players and questions sees each question solved by all but four players. There is at least a pair of players jointly solving all questions. What is the minimal number M of players?

Given the simple update to the above R code

for (qez in 1:N) gamz[qez,sample(1:N,5)]=0

running the R code leads to suggest N=11, as the first instance when the loop does not exit. (The above logical argument does not run so well since having four zeros per column should allow for at most 4×3=12 other columns sharing zeros with that column, which leads to 14 as an upper bound for the answer, not 11!) However, the published solution is 14, which shows the limitation of this R code…

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s