Archive for grid

Le Monde puzzle [#1068]

Posted in Books, Kids, R with tags , , , , , , on October 3, 2018 by xi'an

A purely (?) algorithmic Le Monde mathematical puzzle

For the table below, what is the minimal number of steps required to reach equal entries when each step consists in adding ones to three entries sitting in a L, such as (7,11,12) or (5,6,10)? Same question for the inner table of four in yellow.

For the inner table, this is straightforward as there are four possible L’s, three equations like 6+n⁶=7+n⁷,  and two degrees of freedom leading to a unique entry of N=13 (impossible!)  or 16 (feasible). Hence adding 10 L’s. For the entire table, summing up all entries after completion leads to 16N, which is also equal to 1+3+3+…+16+M, where M is the number of added L’s, itself equal to 138+3O, if O denotes the number of ones added. Hence M can only take the values 18, 21, … It took me quite a while to R code an approach to complete the table into 16 18’s, as my versions of simulated annealing did not seem to converge. In the end, I used a simplified version where the table was completed by multinomial draws, like a M(17;3⁻¹,3⁻¹,3⁻¹) for the upper left corner, corresponding to random draws of one of the 36 available L’s, which should be used 50 times in total, and then augmented or reduced of one L depending on the value at a randomly selected entry. Leading to the result

> aneal(grid=c(1,3,3:13,15,15,16),maxT=1e5)
 [1] 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18

Continue reading

Le Monde puzzle [#1061]

Posted in Books, Kids, R with tags , , , , , on July 20, 2018 by xi'an

lemondapariA griddy Le Monde mathematical puzzle:

  1. On a 4×5 regular grid, find how many nodes need to be turned on to see all 3×4 squares to have at least one active corner in case of one arbitrary node failing.
  2.  Repeat for a 7×9 grid.

The question is open to simulated annealing, as in the following R code:

n=3;m=4;np=n+1;mp=m+1

cvr=function(grue){
  grud=grue
  obj=(max(grue)==0)
  for (i in (1:length(grue))[grue==1]){
   grud[i]=0
   obj=max(obj,max((1-grud[-1,-1])*(1-grud[-np,-mp])*
       (1-grud[-np,-1])*(1-grud[-1,-mp])))
   grud[i]=1}
  obj=99*obj+sum(grue)
  return(obj)}

dumban=function(grid,T=1e3,temp=1,beta=.99){
   obj=bez=cvr(grid)
   sprk=grid
   for (t in 1:T){
     grue=grid
     if (max(grue)==1){ grue[sample(rep((1:length(grid))[grid==1],2),1)]=0
      }else{ grue[sample(1:(np*mp),np+mp)]=1}
     jbo=cvr(grue)
     if (bez>jbo){ bez=jbo;sprk=grue}
     if (log(runif(1))<(obj-jbo)/temp){
        grid=grue;obj=cvr(grid)}
     temp=temp*beta
     }
   return(list(top=bez,sol=sprk))}

leading to

>  dumban(grid,T=1e6,temp=100,beta=.9999)
$top
[1] 8
$sol
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    0    1    0
[2,]    0    1    0    1    0
[3,]    0    1    0    1    0
[4,]    0    1    0    1    0

which sounds like a potential winner.

Le Monde puzzle [#932]

Posted in Books, Kids, Statistics, University life with tags , , , , on October 15, 2015 by xi'an

A Sudoku-like Le Monde mathematical puzzle:

A 12×8 grid contains the first 96 integers, as in R matrix(1:96,ncol=12). If one picks 24 of those integers including 3 for each row and 2 for each column, what are the extreme values of the sum of the selected integers?

I obviously rephrased quite strongly the question (and possibly changed it!). Before rushing to the R simulation of a random collection of 24 such integers, I pondered how this sum could vary among random samples since there were the same terms in all samples. More clearly, using the 10×10 grid instead as a basis for reasoning, picking e.g. 20 integers with 2 per row and 2 per colum for all rows and columns, we end up with 2 copies of every integer between 0 and 9 and 2 copies of every decimal between 0 and 90. Random simulation confirms this reasoning:

grid=matrix(1:96,ncol=12)
#pick a subset at random
coleft=sample(rep(1:12,2))
sub7=grid[1,coleft[1:3]]
coleft=coleft[-(1:3)]
for (i in 2:8){
  sub7=c(sub7,grid[i,coleft[1:3]])
  coleft=coleft[-(1:3)]}
resl=sum(sub7)

since repeated call to the above keeps returning the same value, 1164, which is also

> sum(3*(0:7))*12+2*sum(1:12)
[1] 1164