## Le Monde puzzle [#990]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , on January 12, 2017 by xi'an

To celebrate the new year (assuming it is worth celebrating!), Le Monde mathematical puzzle came up with the following:

Two sequences (x¹,x²,…) and (y¹,y²,…) are defined as follows: the current value of x is either the previous value or twice the previous value, while the current value of y is the sum of the values of x up to now. What is the minimum number of steps to reach 2016 or 2017?

By considering that all consecutive powers of 2 must appear at least one, the puzzles boils down to finding the minimal number of replications in the remainder of the year minus the sum of all powers of 2. Which itself boils down to deriving the binary decomposition of that remainder. Hence the basic R code (using intToBits):

```deco=function(k=2016){
m=trunc(log2(k))
while (sum(2^(0:m))>k) m=m-1
if (sum(2^(0:m))==k){ return(rep(1,m+1))
}else{
res=k-sum(2^(0:m))
return(rep(1,m+1)+as.integer(intToBits(res))[1:(m+1)])
```

which produces

```> sum(deco(2016))
[1] 16
> sum(deco(2017))
[1] 16
> sum(deco(1789))
[1] 18
```

## untangling riddle

Posted in Statistics with tags , , on December 23, 2016 by xi'an

This week riddle is rather anticlimactic [my rewording]:

N wires lead from the top of a tower down to the ground floor. But they have become hopelessly tangled. The wires on the top floor are all labelled, from 1 to N. The wires on the bottom, however, are not.

You need to figure out which ground-floor wire’s end corresponds to which top-floor wire’s end. On the ground floor, you can tie two wire ends together, and you can tie as many of these pairs as you like. You can then walk to the top floor and use a circuit detector to check whether any two of the wires at the top of the tower are connected or not.

What is the smallest number of trips to the top of the tower you need to take in order to correctly label all the wires on the bottom?

Indeed, first, if N=2, the wires cannot be identified, if N=3, they can be identified in 2 steps, and if N=4, they can also be identified in 2 steps (only pair two wires first, which gives their values and the values of the other two up to a permutation, then pair one of each group). Now, in general,  it seems that, by attaching the wires two by two, one can successively cut the number of wires by two at each trip. This is due to the identification of pairs: if wires a and b are connected in one step, identifying the other end of a will automatically determine the other end of b if one keeps track of all connected pairs at the top. Hence, if $N=2^k$, in (k-2) steps, we are down to 4 wires and it takes an extra 2 steps to identify those 4, hence all the other wires. Which leads to identification in N trips. If N is not a power of 2, things should go faster as “left over” wires in the binary division can be paired with set-aside wires and hence identify 3 wires on that trip, then further along the way… Which leads to a $2^{\lfloor \log_2(N) \rfloor}$ number of trips maybe (or even less). Continue reading

## Le Monde puzzle [#940]

Posted in Kids, Statistics, Travel, University life with tags , , , on November 11, 2016 by xi'an

A sudoku-like Le Monde mathematical puzzle:

On a 3×3 grid, all integers from 1 to 9 are present. Considering all differences between adjacent entries, the value of the grid is the minimum difference. What is the maximum possible value?

In a completely uninspired approach considering random permutations on {1,..,9}, the grid value can be computed as

neigh=c(1,2,4,5,7,8,1,4,2,5,3,6)
nigh=c(2,3,5,6,8,9,4,7,5,8,6,9)
perm=sample(9)
val<-function(perm){
min(abs(perm[neigh]-perm[nigh]))}

which produces a value of 3 for the maximal value. For a 4×4 grid

neigh=c(1:3,5:7,9:11,13:15,1+4*(0:2),2+4*(0:2),3+4*(0:2),4*(1:3))
nigh=c(2:4,6:8,10:12,14:16,1+4*(1:3),2+4*(1:3),3+4*(1:3),4*(2:4))
perm=sample(16)
val<-function(perm){
min(abs(perm[neigh]-perm[nigh]))}

the code returns 5. For the representation

[,1] [,2] [,3] [,4]
[1,] 8 13 3 11
[2,] 15 4 12 5
[3,] 9 14 6 16
[4,] 2 7 1 10

## The CS detective

Posted in Books, Kids, Travel, University life with tags , , , , , , , on October 29, 2016 by xi'an

A few weeks ago, I received a generic email from No Starch Press promoting The CS Detective, and as I had liked their earlier Statistics Done Wrong, I requested a review copy of the book. Which I received in Warwick while I was there, last week. And read over my trip back to Paris. As it is a very quick read.

“The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.” T. Pratchett

The idea of the book is to introduce some concepts of tree searching algorithms through a detective-cum-magic story, a very shallow story if somewhat à la Terry Pratchett. (While this reference does not appear in the book, there are enough mentions made of turtles to suspect the filiation. Even though it is turtles all the way down. Hence I could not swear Frank Runtime was 100% inspired from Sam Vimes. But it rhymes.) I cannot say I am a bit fan of this approach as the story is an hindrance rather than an help, I do not find it particularly funny or enticing, and I keep wishing for the next concept to appear to end the current chapter and its inane plot. Of course, once the story is set aside, the book contains not that much in terms of search algorithms, because they all are limited to discrete tree structures. Namely, exhaustive, binary, breadth- and depth-first, iterative deepening, best-first, search algorithms, along with the notions of arrays, queues, stacks, and heaps. This fills about 50 pages of technical vignettes found at the end of each chapter…

So I end up wondering at what age this book would appeal to a young reader. Trying to remember from my own experience with summer vacation riddle and puzzle books, I would think the range 10-12 could be most appropriate although mileage will vary. Since the author, Jeremy Kubica, animates the Computational Fairy Tales blog with stories of the same flavour, you may start by tasting and testing this approach to popular science before getting the entire book

## Le Monde puzzle [#977]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , , on October 3, 2016 by xi'an

A mild arithmetic Le Monde mathematical puzzle:

Find the optimal permutation of {1,2,..,15} towards minimising the maximum of sum of all three  consecutive numbers, including the sums of the 14th, 15th, and first numbers, as well as the 15th, 1st and 2nd numbers.

If once again opted for a lazy solution, not even considering simulated annealing!,

```parme=sample(15)
max(apply(matrix(c(parme,parme[-1],
parme[1],parme[-(1:2)],parme[1:2]),3),2,sum))
```

and got the minimal value of 26 for the permutation

14 9 2 15 7 1 11 10 4 12 8 5 13 6 3

Le Monde gave a solution with value 25, though, which is

11 9 7 5 13 8 2 10 14 6 1 12 15 4 3

but there is a genuine mistake in the solution!! This anyway shows that brute force may sometimes fail. (Which sounds like a positive conclusion to failing to find the proper solution! But trying with a simple simulated annealing version did not produce any 25 either…)

## Le Monde puzzle [#967]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , , , , on September 30, 2016 by xi'an

A Sudoku-like Le Monde mathematical puzzle for a come-back (now that it competes with The Riddler!):

Does there exist a 3×3 grid with different and positive integer entries such that the sum of rows, columns, and both diagonals is a prime number? If there exist such grids, find the grid with the minimal sum?

I first downloaded the R package primes. Then I checked if by any chance a small bound on the entries was sufficient:

```cale<-function(seqe){
ros=apply(seqe,1,sum)
cole=apply(seqe,2,sum)
dyag=sum(diag(seqe))
dayg=sum(diag(seqe[3:1,1:3]))
return(min(is_prime(c(ros,cole,dyag,dayg)))>0)}
```

Running the blind experiment

```for (t in 1:1e6){
n=sample(9:1e2,1)
if (cale(matrix(sample(n,9),3))) print(n)}
```

I got 10 as the minimal value of n. Trying with n=9 did not give any positive case. Running another blind experiment checking for the minimal sum led to the result

```> A
[,1] [,2] [,3]
[1,] 8 3 6
[2,] 1 5 7
[3,] 2 11 4
```

with sum 47.

## Le Monde puzzle [#965]

Posted in Kids, R with tags , , , on June 14, 2016 by xi'an

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)<max(sol))
sol=solvant(piles)
return(sol)}

resolvant <- function(piles){
sol=disolvant(piles)
lasol=sol;maxle=length(sol)
for (t in 1:piles){
sol=disolvant(piles)
if (length(sol)>maxle){
lasol=sol;maxle=length(sol)}}
return(lasol)}
```