Le Monde puzzle [#869]
A Le Monde mathematical puzzle once again in a Sudoku mode:
In an nxn table, all integers between 1 and n appear n times. If max denotes the maximum over the numbers of different integers on all rows and columns, what is the minimum value of max when n=7? when n=11?
I tried to solve it by the following R code (in a pre-breakfast mode in my Reykjavik Airbnb flat!):
#pseudoku n=7 T=10^4 vals=rep(1:n,n) minmax=n for (t in 1:T){ psudo=matrix(sample(vals),ncol=n) maxc=maxr=max(sapply(apply(psudo,1,unique),length)) if (maxc<minmax) maxr=max(sapply(apply(psudo,2,unique),length)) minmax=min(minmax,max(maxc,maxr)) }
but later realised that (a) the
sapply(apply(psudo,1,unique),length)
failed when all rows or all columns had the same number of unique terms and (b) I did not have to run the whole matrix:
vals=rep(1:n,n) minmax=n for (t in 1:T){ psudo=matrix(sample(vals),ncol=n) maxc=max(length(unique(psudo[1,])),length(unique(psudo[,1]))) i=1 while((i<n)&(maxc<minmax)){ i=i+1 maxc=max(maxc, length(unique(psudo[i,])), length(unique(psudo[,i])))} minmax=min(minmax,maxc) }
gaining a factor of 3 in the R execution. With this random exploration, the minimum value returned was 2,2,2,3,4,5,5,6,7,8 for n=2,3,4,5,6,7,8,9,10,11. Half-hearted simulating annealing during one of the sessions of AISTATS 2014 did not show any difference…
April 28, 2014 at 7:53 pm
I think the answer may be ceiling(n/2) for n > 2. Consider n=6 and psudo=matrix(c(rep(rep(1:3, each=2), 3), rep(rep(4:6, each=2), 3)), nrow=6); For n=7, psudo=cbind(rbind(psudo, c(1,2,3,7,7,7)), c(4,7,5,7,6,7,7)).
April 28, 2014 at 9:00 pm
Thanks, Cole! I did not look at the math side of the puzzle,
April 27, 2014 at 2:12 am
[…] article was first published on Xi'an's Og » R, and kindly contributed to […]