## Le Monde puzzle 

An interesting suduko-like puzzle for this week puzzle in Le Monde that allows for an R resolution (almost!)

A 10×10 grid is filled by a random permutation of {0,…,99}. The 4 largest figures in each row are coloured in yellow and the 4 largest values in each column are coloured in red. What is the range of the number of yellow-and-red figures?

Here is a random grid

> lascases=matrix(sample(0:99),10,10)
> lascases
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    3   95   62   71   68   76   12   39   58    77
[2,]    8   82   79   47   56   84   35   11   34    83
[3,]   99    1   10   64   30   22   75   25   16    52
[4,]   31    5   81   72   45   90   98   18   19    70
[5,]   74   66   78   86   87    0   14   92   97    88
[6,]   41   23   21   80   49    4   48   38   61    37
[7,]   89   55   65   17   54   60   50   32   15     2
[8,]   91    9   94   24   42   53   27   44   51    26
[9,]   33   59   63   46   43    7   28   36   20    67
[10,]   93   40   13   96   69   73   29   57    6    85

whose yellow figures are given by

> apply(lascases,1,rank)>6

> t(apply(lascases,1,rank)>6)
[[,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10]
[1,] FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE FALSE FALSE  TRUE
[2,] FALSE  TRUE  TRUE FALSE FALSE  TRUE FALSE FALSE FALSE  TRUE
[3,]  TRUE FALSE FALSE  TRUE FALSE FALSE  TRUE FALSE FALSE  TRUE
[4,] FALSE FALSE  TRUE  TRUE FALSE  TRUE  TRUE FALSE FALSE FALSE
[5,] FALSE FALSE FALSE FALSE  TRUE FALSE FALSE  TRUE  TRUE  TRUE
[6,] FALSE FALSE FALSE  TRUE  TRUE FALSE  TRUE FALSE  TRUE FALSE
[7,]  TRUE  TRUE  TRUE FALSE FALSE  TRUE FALSE FALSE FALSE FALSE
[8,]  TRUE FALSE  TRUE FALSE FALSE  TRUE FALSE FALSE  TRUE FALSE
[9,] FALSE  TRUE  TRUE  TRUE FALSE FALSE FALSE FALSE FALSE  TRUE
[0,]  TRUE FALSE FALSE  TRUE FALSE  TRUE FALSE FALSE FALSE  TRUE

and red figures by

> apply(lascases,2,rank)>6
[,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10]
[1,] FALSE  TRUE FALSE FALSE  TRUE  TRUE FALSE  TRUE  TRUE  TRUE
[2,] FALSE  TRUE  TRUE FALSE  TRUE  TRUE FALSE FALSE FALSE  TRUE
[3,]  TRUE FALSE FALSE FALSE FALSE FALSE  TRUE FALSE FALSE FALSE
[4,] FALSE FALSE  TRUE  TRUE FALSE  TRUE  TRUE FALSE FALSE FALSE
[5,] FALSE  TRUE  TRUE  TRUE  TRUE FALSE FALSE  TRUE  TRUE  TRUE
[6,] FALSE FALSE FALSE  TRUE FALSE FALSE  TRUE FALSE  TRUE FALSE
[7,]  TRUE FALSE FALSE FALSE FALSE FALSE  TRUE FALSE FALSE FALSE
[8,]  TRUE FALSE  TRUE FALSE FALSE FALSE FALSE  TRUE  TRUE FALSE
[9,] FALSE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[0,]  TRUE FALSE FALSE  TRUE  TRUE  TRUE FALSE  TRUE FALSE  TRUE

hence resulting in the yellow-and-red figures

> t(apply(lascases,1,rank)>6)*(apply(lascases,2,rank)>6)
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    0    1    0    0    0    1    0    0    0     1
[2,]    0    1    1    0    0    1    0    0    0     1
[3,]    1    0    0    0    0    0    1    0    0     0
[4,]    0    0    1    1    0    1    1    0    0     0
[5,]    0    0    0    0    1    0    0    1    1     1
[6,]    0    0    0    1    0    0    1    0    1     0
[7,]    1    0    0    0    0    0    0    0    0     0
[8,]    1    0    1    0    0    0    0    0    1     0
[9,]    0    1    0    0    0    0    0    0    0     0
[0,]    1    0    0    1    0    1    0    0    0     1

Therefore computing the number of yellow-and-red figures is simply done by

> sum((t(apply(lascases,1,rank)>6))*(apply(lascases,2,rank)>6))
 29

So it is enought to cycle through random allocations to monitor the range of this sum.
miny=99
maxy=0

for (t in 1:10^5){
lascases=matrix(sample(0:99),10,10)
res=sum(t(apply(lascases,1,rank)>6)*(apply(lascases,2,rank)>6))

if (res>maxy) maxy=res
if (res<miny) miny=res
}

With 105 simulations, I find a range of (24,39)… However, if I apply the computation to the matrix filled row-wise by 0:99, the number of yellow-and-red figures is

>   lascases=matrix(0:99,10,10)
>   sum(t(apply(lascases,1,rank)>6)*(apply(lascases,2,rank)>6))
 16

which sounds reasonable as a lower value since the larger values  are concentrated on one single 4×4 square. I think the upper value should be 40 as there cannot be more than 4 yellow-and-red figures on each row and 39 is really close… Simulation (as done above) is simply too costly to reach the whole range.

### 4 Responses to “Le Monde puzzle ”

1. robinryder Says:

Here is a matrix which reaches the upper bound of 40: $\begin{tabular}{cccccccccc} 99&98&97&96&x&x&x&x&x&x\\ x & 95& 94& 93& 92&x&x&x&x&x\\x&x&91&90&89&88&x&x&x&x\\x&x&x&87&86&85&84&x&x&x\\x&x&x&x&83&82&81&80&x&x\\x&x&x&x&x&79&78&77&76&x\\x&x&x&x&x&x&75&74&73&72\\71&x&x&x&x&x&x&70&69&68\\67&66&x&x&x&x&x&x&65&64\\63&62&61&x&x&x&x&x&x&60\end{tabular}$

where the x’s represent the numbers from 0 to 59.

• xi'an Says:

Robin really looked at the problem! And, as always, found the solution! Merci.

2. Simon Says:

Hi Christian,

Thanks very much for your many interesting posts, I follow them with pleasure.

If I understand this puzzle correctly I think there may be an error in your program – I believe the overall lower limit should be 16, and for the example you gave the red-and-yellow squares number 32, rather than 21. The problem may be to do with taking one of the rank matrix transposes by mistake.

With 10^5 iterations I get a range of (24,39), suggesting the lower bound is hardest to find with this random search, but it’s interesting to think how you might more efficiently find the limits…

Many thanks again,

Simon

• xi'an Says:

Uh-oh! Thank you Simon for pointing out the mistake. I keep forgetting this feature of R that does not always return the matrix of transforms when using apply()… I should have realised something was wrong when hitting 0 as a lower bound since this was clearly impossible!

This site uses Akismet to reduce spam. Learn how your comment data is processed.