Le Monde puzzle [#817]
[This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
The weekly Le Monde puzzle is (again) a permutation problem that can be rephrased as follows:
Find
where
denotes the set of permutations on {0,…,10} and
is defined modulo 11 [to turn {0,…,10} into a torus]. Same question for
and for
This is rather straightforward to code if one adopts a brute-force approach::
perminmax=function(T=10^3){
mins=sums=rep(500,3)
permin=matrix(0:10,ncol=11,nrow=3,byrow=TRUE)
for (t in 1:T){
perms=sample(0:10)
adde=perms+perms[c language="(11,1:10)"][/c]
sums[1]=max(adde)
adde=adde+perms[c language="(10,11,1:9)"][/c]
sums[2]=max(adde)
adde=adde+perms[c language="(9:11,1:8)"][/c]+perms[c language="(8:11,1:7)"][/c]
sums[3]=max(adde)
for (j in 1:3)
if (sums[j]<mins[j]){
mins[j]=sums[j];permin[j,]=perms}
}
print(mins)
print(permin)
}
(where I imposed the first term to be zero because of the invariance by permutation), getting the solutions
> perminmax(10^5)
[1] 11 17 28
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
[1,] 0 10 1 6 5 4 7 3 8 2 9
[2,] 0 10 4 3 5 1 9 6 2 8 7
[3,] 0 2 9 6 7 3 1 4 10 8 5
for 2, 3, and 5 terms. (Since 10! is a mere 3.6 million, I checked with an exhaustive search, using the function permutation from the gtools package.)
Filed under: Books, Kids, R Tagged: gtools, Le Monde, mathematical puzzle, permutations, R
To leave a comment for the author, please follow the link and comment on their blog: Xi'an's Og » R.
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.