Le Monde puzzle [40]

[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.

The puzzle in Le Monde this week[end] is called the “square five” (sic!):

Two players each have twenty-five cards with five times each of the digits 1,2,3,4,5. They alternate putting one card on top of the pile, except that they can instead take an arbitrary number of consecutive cards from the top of the pile whose product is a squared number. In which case the corresponding player wins! What is the maximum number of moves and who can find a winning strategy?

At any time, a player cannot put a 1 or a 4 because those are squared numbers. The choice is therefore always among 2,3,5, with a prohibition of squares in the sequence. Testing blindly for the longest possible sequence can be done via the following R code

#testing for squares
whole=function(x,tol = .Machine$double.eps^0.5) abs(x - round(x)) < tol

#Monte Carlo loop
maxl=1
for (t in 1:10^4){

counter=matrix(5,ncol=2,nrow=5)
#random start
rounds=1
pile=sample(c(2,3,5),1)
counter[pile,1]=counter[pile,1]-1
cont=TRUE
playr=2
while (cont){

 if (max(whole(sqrt(cumprod(pile[rounds:1]))))==1){
 cont=FALSE
 }else{
 if (sum(counter[c(2,3,5),playr])==0){
 newt=4 #game over!
 }else{
 newt=sample(c(2,3,5)[counter[c(2,3,5),playr]>0],1)
 }
 pile=c(pile,newt)
 counter[newt,playr]=counter[newt,playr]-1
 rounds=rounds+1
 playr=3-playr
 }
 }
if (rounds>maxl)
 sek=pile
maxl=max(maxl,rounds)
}

which gives a maximum length of 8, a figure that makes sense since picking any sequence of length 8 from 2,3,5 leads to a square by a tree decomposition. It does not seem there is a winning strategy for the second player if the first one plays in an optimal manner…


Filed under: R, Statistics, University life Tagged: Le Monde, mathematical puzzle

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.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)