Archive for mathematical puzzle

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)}

Le Monde puzzle [#964]

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

A not so enticing Le Monde mathematical puzzle:

Find the minimal value of a five digit number divided by the sum of its digits.

This can formalised as finding the minimum of N/(a+b+c+d+e) when N writes abcde. And solved by brute force. Using a rough approach to finding the digits of a five-digit number, the question can be easily solved as

pris=1e6
for (i in 1e4:1e5){
 pres=i/sum((i %% 10^{5:1})) %/% 10^{4:0})
 if (pres<pris){
 pris=pres;sol=i}}

which returns N=10999 as its solution. (The solution for six digits is 10999.) The mathematical solution as provided in the newspaper certainly sounded more exciting.

a Simpson paradox of sorts

Posted in Books, Kids, pictures, R with tags , , , , , , , , , on May 6, 2016 by xi'an

The riddle from The Riddler this week is about finding an undirected graph with N nodes and no isolated node such that the number of nodes with more connections than the average of their neighbours is maximal. A representation of a connected graph is through a matrix X of zeros and ones, on which one can spot the nodes satisfying the above condition as the positive entries of the vector (X1)^2-(X^21), if 1 denotes the vector of ones. I thus wrote an R code aiming at optimising this target

targe <- function(F){
  sum(F%*%F%*%rep(1,N)/(F%*%rep(1,N))^2<1)}

by mere simulated annealing:

rate <- function(N){ 
# generate matrix F
# 1. no single 
F=matrix(0,N,N) 
F[sample(2:N,1),1]=1 
F[1,]=F[,1] 
for (i in 2:(N-1)){ 
if (sum(F[,i])==0) 
F[sample((i+1):N,1),i]=1 
F[i,]=F[,i]} 
if (sum(F[,N])==0) 
F[sample(1:(N-1),1),N]=1 
F[N,]=F[,N] 
# 2. more connections 
F[lower.tri(F)]=F[lower.tri(F)]+
  sample(0:1,N*(N-1)/2,rep=TRUE,prob=c(N,1)) 
F[F>1]=1
F[upper.tri(F)]=t(F)[upper.tri(t(F))]
#simulated annealing
T=1e4
temp=N
targo=targe(F)
for (t in 1:T){
  #1. local proposal
  nod=sample(1:N,2)
  prop=F
  prop[nod[1],nod[2]]=prop[nod[2],nod[1]]=
     1-prop[nod[1],nod[2]]
  while (min(prop%*%rep(1,N))==0){
    nod=sample(1:N,2)
    prop=F
    prop[nod[1],nod[2]]=prop[nod[2],nod[1]]=
     1-prop[nod[1],nod[2]]}
  target=targe(prop)
  if (log(runif(1))*temp<target-targo){ 
    F=prop;targo=target} 
#2. global proposal 
  prop=F prop[lower.tri(prop)]=F[lower.tri(prop)]+
   sample(c(0,1),N*(N-1)/2,rep=TRUE,prob=c(N,1)) 
prop[prop>1]=1
  prop[upper.tri(prop)]=t(prop)[upper.tri(t(prop))]
  target=targe(prop)
  if (log(runif(1))*temp<target-targo){
      F=prop;targo=target}
   temp=temp*.999
   }
return(F)}

Eward SimpsonThis code returns quite consistently (modulo the simulated annealing uncertainty, which grows with N) the answer N-2 as the number of entries above average! Which is rather surprising in a Simpson-like manner since all entries but two are above average. (Incidentally, I found out that Edward Simpson recently wrote a paper in Significance about the Simpson-Yule paradox and him being a member of the Bletchley Park Enigma team. I must have missed out the connection with the Simpson paradox when reading the paper in the first place…)