Le Monde puzzle [#965]

June 13, 2016
By

(This article was first published on R – Xi'an's Og, and kindly contributed to R-bloggers)

A game-related Le Monde mathematical puzzle:

Starting with a pile of 10⁴ tokens, Bob plays the following game: at each round, he picks one of the existing piles with at least 3 tokens, takes away one of the tokens in this pile, and separates the remaining ones into two non-empty piles of arbitrary size. Bob stops when all piles have identical size. What is this size and what is the maximal number of piles?

First, Bob can easily reach a decomposition that prevents all piles to be of the same size: for instance, he can start with a pile of 1 and another pile of 2. Looking at the general perspective, an odd number of tokens, n=2k+1, can be partitioned into (1,1,2k-1). Which means that the decomposition (1,1,…,1) involving k+1 ones can always be achieved. For an even number, n=2k, this is not feasible. If the number 2k can be partitioned into equal numbers u, this means that the sequence 2k-(u+1),2k-2(u+1),… ends up with u, hence that there exist m such that 2k-m(u+1)=u or that 2k+1 is a multiple of (u+1). Therefore, the smallest value is made of the smallest factor of 2k+1. Minus one. For 2k=10⁴, this value is equal to 72, while it is 7 for 10³. The decomposition is impossible for 2k=100, since 101 is prime. Here are the R functions used to check this analysis (with small integers, if not 10⁴):

solvant <- function(piles){
 if ((length(piles)>1)&((max(piles)==2)||(min(piles)==max(piles)))){
  return(piles)}else{
   i=sample(rep(1:length(piles),2),1,prob=rep(piles-min(piles)+.1,2))
   while (piles[i]<3)
    i=sample(rep(1:length(piles),2),1,prob=rep(piles-min(piles)+.1,2))
   split=sample(rep(2:(piles[i]-1),2),1,
        prob=rep(abs(2:(piles[i]-1)-piles[i]/2)+.1,2))
   piles=c(piles[-i],split-1,piles[i]-split)
   solvant(piles)}}

disolvant <- function(piles){
 sol=solvant(piles)
 while (min(sol)maxle){
 lasol=sol;maxle=length(sol)}}
 return(lasol)}

Filed under: Kids, R Tagged: Le Monde, mathematical puzzle, R, recursive function

To leave a comment for the author, please follow the link and comment on their blog: R – Xi'an's Og.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Sponsors

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)