Archive for mathematical puzzle

Le Monde sans puzzle [& sans penguins]

Posted in Books, Kids, R, University life with tags , , , , , on April 12, 2014 by xi'an

As the Le Monde mathematical puzzle of this week was a geometric one (the quadrangle ABCD is divided into two parts with the same area, &tc…) , with no clear R resolution, I chose to bypass it. In this April 3 issue, several items of interest: first, a report by Etienne Ghys on Yakov Sinaï’s Abel Prize for his work “between determinism and randomness”, centred on ergodic theory for dynamic systems, which sounded like the ultimate paradox the first time I heard my former colleague Denis Bosq give a talk about it in Paris 6. Then a frightening fact: the summer conditions have been so unusually harsh in Antarctica (or at least near the Dumont d’Urville French austral station) that none of the 15,000 Adélie penguin couples studied there managed to keep their chick alive. This was due to an ice shelf that did not melt at all over the summer, forcing the penguins to walk an extra 40k to reach the sea… Another entry on the legal obligation for all French universities to offer a second chance exam, no matter how students are evaluated in the first round. (Too bad, I always find writing a second round exam a nuisance.)

Le Monde puzzle [#860]

Posted in Books, Kids, R with tags , , , , on April 4, 2014 by xi'an

A Le Monde mathematical puzzle that connects to my awalé post of last year:

For N≤18, N balls are placed in N consecutive holes. Two players, Alice and Bob, consecutively take two balls at a time provided those balls are in contiguous holes. The loser is left with orphaned balls. What is the values of N such that Bob can win, no matter what is Alice’s strategy?

I solved this puzzle by the following R code that works recursively on N by eliminating all possible adjacent pairs of balls and checking whether or not there is a winning strategy for the other player.

topA=function(awale){
# return 1 if current player can win, 0 otherwise

  best=0
  if (max(awale[-1]*awale[-N])==1){
  #there are adjacent balls remaining

   for (i in (1:(N-1))[awale[1:(N-1)]==1]){

    if (awale[i+1]==1){
      bwale=awale
      bwale[c(i,i+1)]=0
      best=max(best,1-topA(bwale))
      }
  }}
  return(best)
 }

for (N in 2:18) print(topA(rep(1,N)))

which returns the solution

[1] 1
[1] 1
[1] 1
[1] 0
[1] 1
[1] 1
[1] 1
[1] 0
[1] 1
[1] 1
[1] 1
[1] 1
[1] 1
[1] 0
[1] 1
[1] 1
[1] 1
<pre>

(brute-force) answering the question that N=5,9,15 are the values where Alice has no winning strategy if Bob plays in an optimal manner. (The case N=5 is obvious as there always remains two adjacent 1′s once Alice removed any adjacent pair. The case N=9 can also be shown to be a lost cause by enumeration of Alice’s options.)

Le Monde puzzle [#857]

Posted in Books, Kids, R with tags , , , , , , , on March 22, 2014 by xi'an

A rather bland case of Le Monde mathematical puzzle :

Two positive integers x and y are turned into s=x+y and p=xy. If Sarah and Primrose are given S and P, respectively, how can the following dialogue happen?

  • I am sure you cannot find my number
  • Now you told me that, I can, it is 46.

and what are the values of x and y?

In the original version, it was unclear whether or not each person knew she had the sum or the product. Anyway, the first person in the dialogue has to be Sarah, since a product p equal to a prime integer would lead Primrose to figure out x=1 and hence s=p+1. (Conversely, having observed the sum s cannot lead to deduce x and y.) This means x+y-1 is not a prime integer. Now the deduction of Primrose that the sum is 46 implies p can be decomposed only once in a product such that x+y-1 is not a prime integer. If p=45, this is the case since 45=15×3 and 45=5×9 lead to 15+3-1=17 and 5+9-1=13, while 45=45×1 leads to 45+1-1=45.  Other solutions fail, as demonstrated by the R code:

 > for (x in 1:23){
 + fact=c(1,prime.factor(x*(46-x)))
 + u=0;
 + for (i in 1:(length(fact)-1))
 + u=u+1-is.prim(prod(fact[1:i])+prod(fact[-(1:i)])-1)
 + if (u==1) print(x)}
 [1] 1
 

Busser and Cohen argue much more wisely in their solution that any non-prime product p other than 45 would lead to p+1 as an acceptable sum s, hence would prevent Primrose from guessing s.

Le Monde puzzle [#855]

Posted in Books, Kids, Statistics with tags , , , , , , on March 7, 2014 by xi'an

A Le Monde mathematical puzzle that reminds me of an earlier one:

Given ten tokens with different unknown weights, and a scale that can rank three tokens at a time, starting with ranking three tokens, what is the minimum number of actions necessary to rank the ten of them if (a) one token at a time is added, (b) one or two tokens are added? If no restriction is imposed on the token introduction, is there a more efficient strategy?

It indeed relates to earlier posts on sorting and ternary sorting. Checking further on StackOverflow I found this reply to a question about ternary sorting:

Average number of comparisons:

in ternary search = ((1/3)*1+(2/3)*2)*ln(n)/ln(3)~1.517*ln(n)
in binary search  =                 1*ln(n)/ln(2)~1.443*ln(n)

Worst number of comparisons:

in ternary search = 2*ln(n)/ln(3)~1.820*ln(n)
in binary search  = 1*ln(n)/ln(2)~1.443*ln(n)

albeit with no reference. So this somewhat answers part (c) of the question. (If asymptotically since this does not work for n=10! Even for n=100, it is way too large.) Looking for a solution to part (a), I looked at the performances of a dyadic sorting algorithm, partitioning recursively the already sorted part of the sample into three parts to locate each time the proper position of the new token. This led me to the following code

rang=function(x,ranj,taken){

  mag=max(ranj)-min(ranj)+1
  i1=ranj[1]-1+trunc(mag/3)
  i2=ranj[1]-1+trunc(2*mag/3)
  locrk=rank(c(taken[c(i1,i2)],x))

  if (locrk[3]==1) return(ifelse(i1>3,
     1+rang(x,ranj=1:(i1-1),taken),
     1+(i1>1)))
  if (locrk[3]==2) return(ifelse(i2-i1>4,
     1+rang(x,ranj=(i1+1):(i2-1),taken),ranj=1:(i1-1),taken),
     1+(i1>1)))
  if (locrk[3]==3) return(ifelse(mag-i2>2,
     1+rang(x,ranj=(i2+1):mag,taken),ranj=1:(i1-1),taken),
     1+(i1>1)))
}

ternone=function(toke){

toke[1:3]=sort(toke[1:3])
counter=1
for (ul in (4:length(toke))){

  counter=counter+rang(toke[ul],1:(ul-1),toke)
  toke[1:ul]=sort(toke[1:ul])
  }

return(counter)
}

ternone(sample(1:10))

which produces a minimum of eight (of course!) and a maximum of 20 uses of the scale (based on 10⁶ random permutations of (1,…,10)). Unsurprisingly, the solution proposed in Le Monde the week after does better as it obtains 16 as the worst case figure. Repeating the experiment with n=100 values, the maximum was 303 (with a mean of 270 and a minimum of 240 ternary comparisons).

Moving to an insertion two tokens at a time, I tested a scheme where two new tokens were tested against the current median, then the median of one half, and so on until they split on both sides of this median. Here is the corresponding R code

ring=function(x,y,ranj,taken){

mag=max(ranj)-min(ranj)+1
i1=ranj[1]-1+trunc(mag/2)
locrk=rank(c(taken[i1],x,y))

if (locrk[1]==3) return(ifelse(i1>2,
    1+ring(x,y,ranj=1:(i1-1),taken),
    1+(i1==2)))
if (locrk[1]==2) return(ifelse(mag>4,
    1+rang(min(x,y),ranj=min(ranj):(i1-1),taken)
    +rang(max(x,y),(i1+1):max(ranj),taken),1))
if (locrk[1]==1) return(ifelse(mag-i1>2,
    1+ring(x,y,ranj=(i1+1):mag,taken),
    1+(mag-i1>1)))
}

terntwo=function(toke){

toke[1:3]=sort(toke[1:3])
counter=1+rang(toke[4],1:3,toke)
toke[1:4]=sort(toke[1:4])

for (ul in -1+2*(3:(length(toke)/2))){

  counter=counter+ring(toke[ul],toke[ul+1],1:(ul-1),toke)
  toke[1:ul]=sort(toke[1:ul])
  ul=ul+1
  }

return(counter)
}

leading to a value of 13.

This Feb. 19 issue of Le Monde Science&Médecine leaflet also contains a two page report on growing psychological work-related issues like stress, burn-out and depression, in research labs, mostly connected with the increase in administrative duties and grant writing, duties most of us have not been trained for. There is also a short column by Etienne Gys telling about the short lived claim by Moukhtarbaï Otelbaev to have solved the Navier-Stokes problem. Until Terry Tao wrote a paper stating why the proof could not work.

Le Monde puzzle [#854]

Posted in Books, Kids, Statistics with tags , , on February 21, 2014 by xi'an

A Le Monde mathematical puzzle that sounds similar to earlier ones:

Find all integers x between 1000 and 9999 and N≥1 such Nx has the reverse sequence of digits compared with i.  

For N=1, the appropriate integers x are such that the four digits are symmetrical, as in x=3553. For N≥1, I ran the following R code:

for (i in 10^3:(5*10^3)){
 dig=rev(intToDigits(i))
 for (N in 2:8){
  if (N*i>9999) break()
  if (max(abs(intToDigits(N*i)-dig))<.1)
      print(c(i,N,N*i))
      }}

and only found the single entry

[1] 2178    4 8712

where the intToDigits function was suggested to me by Pierre Pudlo:

intToDigits <- function(x) {
 if (length(x) != 1) {
   warning( "x should be of length 1. Using only x[1]")
   x <- x[1]
   }
 m <- floor(log10(x)) + 1
 pow10 <- 10^(1:m)
 xpow <- x * pow10 / (10^m)
 xrep <- trunc(xpow) / pow10
 digits <- c(xrep[1], xrep[-1]-xrep[-m]) * pow10
 digits
 }
Follow

Get every new post delivered to your Inbox.

Join 551 other followers