Archive for rank statistics

Le Monde puzzle [#1010]

Posted in Books, Kids with tags , , , , on June 2, 2017 by xi'an

An arithmetic Le Monde mathematical puzzle (or two independent ones, again!):

  1. Take the integers from 1 to 19, pick two of them with identical parity at random and replace the pair with their average. Repeat 17 times to obtain a single integer. What are the values between 1 and 19 that cannot be achieved?
  2.  Take the integers from 1 to 19, pick four of them at random so that the average is an integer and replace the quadruplet with their average. Repeat 5 times to obtain a single integer. What are the values between 1 and 19 that can be achieved?

The first question seems pretty open to brute force simulation. Here is an R code I wrote

numbz=1:M
for (t in 2:M){
 numbz=sample(numbz);count=0
 while((count<100)&(sum(numbz[1:2])%%2>0)){
   numbz=sample(numbz);count=count+1}
if (count==100) break()
 numbz[1]=as.integer(mean(numbz[1:2]))
 numbz=numbz[-2]}

with the stopping rule resulting from the fact that the remaining two digits may sometimes be of opposite parity (a possibility omitted in the wording of the puzzle, along with a mistake in the number of repetitions). However, the outcome of this random exploration misses the extreme possible values. For instance, 10⁶ attempts produce the range

4 5 6 7 8 9 10 11 12 13 14 15 16 17

while the extremes should be 2 and 18 according to this scratch computation:

which appears to have too low a probability of occurring for being part of the 10⁶ instances. Running the code a mere (!) 10⁷ iterations managed to reach 3 as well. (Interestingly, the above sequence uses 2 the most and 19 the least, but weights 19 the most and 2 the least!)

The second puzzle is also open to random exploration with a very similar R code:

utcome=NULL
for (z in 1:1e6){
numbz=1:19
for (t in 1:6){
  numbz=sample(numbz);count=0
  while ((sum(numbz[1:4])%%4>0)&(count<100)){
    numbz=sample(numbz);count=count+1}
  if (count==100) break()
  numbz[1]=as.integer(mean(numbz[1:4]))
  numbz=numbz[-(2:4)]}
if (count<100) utcome=c(utcome,numbz)}

returning the values

4 7 10 13 16

Le Monde puzzle [#1009]

Posted in Books, Kids with tags , , , , on May 26, 2017 by xi'an

An incomprehensible (and again double) Le Monde mathematical puzzle (despite requests to the authors! The details in brackets are mine.):

  1. A [non-circular] chain of 63 papers clips can be broken into sub-chains by freeing one clip [from both neighbours] at a time. At a given stage, considering the set of the lengths of these sub-chains, the collection of all possible sums of these lengths is a subset of {1,…,63}. What is the minimal number of steps to recover the entire set {1,…,63}?  And what is the maximal length L of a chain of paper clips that allows this recovery in 8 steps?
  2.  A tri-colored chain of 200 paper clips starts with a red, a blue and a green clip. Removing one clip every four clips produces a chain of 50 removed clips identical to the chain of 50 first clips of the original chain and a chain of remaining 150 clips identical to the 150 first clips of the original chain. Deduce the number of green, red, and blue clips.

The first question can be easily tackled by random exploration. Pick one number at random between 1 and 63, and keep picking attached clips until the set of sums is {1,…,63}. For instance,

rebreak0]
 sumz=cumsum(sample(difz))
 for (t in 1:1e3)
  sumz=unique(c(sumz,cumsum(sample(difz))))
 if (length(sumz)<63)
    brkz=rebreak(sort(c(brkz,sample((1:63)[-brkz],1))))
 return(brkz)}

where I used sampling to find the set of all possible partial sums. Which leads to a solution with three steps, at positions 5, 22, and 31. This sounds impossibly small but the corresponding lengths are

1 1 1 4 8 16 32

from which one can indeed recover by summation all numbers till 63=2⁶-1. From there, a solution in 8 steps can be found by directly considering the lengths

1 1 1 1 1 1 1 1 9 18=9+8 36=18+17+1 72 144 288 576 1152 2303

whose total sum is 4607. And with breaks

10 29 66 139 284 573 1150 2303

The second puzzle is completely independent. Running another R code reproducing the constraints leads to

tromcol=function(N=200){
  vale=rep(0,N)
  vale[1:3]=1:3
  while (min(vale)==0){
    vale[4*(1:50)]=vale[1:50]
    vale[-(4*(1:50))]=vale[1:150]}
  return(c(sum(vale==1),sum(vale==2),sum(vale==3)))}

and to 120 red clips, 46 blue clips and 34 green clips.

Le Monde puzzle [#1008]

Posted in Books, Kids with tags , , , , on May 16, 2017 by xi'an

An arithmetic Le Monde mathematical puzzle (or two independent ones, rather):

  1. The set of integers between 1 and 2341 is partitioned into sets such that a given set never contains both n and 3n. What is the largest possible size of one of these sets?
  2.  Numbers between 1 and 2N are separated in two sets A and B of size N. Alice takes the largest element out of A and the smallest element out of B, records the absolute difference as S, and then repeats the sampling, adding the absolute difference to S at each draw. Bob does the same with numbers between 1 and 2P, with P<N, obtaining a total value of R. Alice points out that S-R=2341. What are the values of N and P?

The first question seems hard to solve by brute force simulation. My first idea is to take all prime numbers [except 3!] less than 2341, which is itself a prime number, and all combinations of these numbers less than 2341, since none of those is divisible by 3. Adding 3 as a final item keeps the constraint fine if 1 is not part of it (but 1 is not a prime number, so this is under control). Adding instead 1 to the set has the same impact but seems more natural. The number of prime numbers is 346, while the total size of the set thus constructed is 1561. Equal to 1+2×2340/3. However, the constraint in the puzzle does not exclude m and 9m. Or m and 9²m, or m and 9³m. Considering such multiples within {1,…,2341} leads to a set with 1765 integers.

The second puzzle is indeed independent and actually straightforward when one realises that the sums S and R are always equal to N² and P², respectively. (This is easily proven by invariance under a permutation turning the lowest entries to B and the largest ones to A. But there must be a rank statistic identity behind this result!) Hence it boils down to figuring out a pair (N,P) such that N²-P²=2341. Since 2341=(N-P)(N+P) is prime, this implies N=P+1. And N²-(N-1)²=N²-N²+2N-1=2341. Which leads to (N,P)=(1171,1170) as the only solution.