Le Monde puzzle [42]

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))
[1] 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))
[1] 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 [42]”

  1. 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.

  2. 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

    • 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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 670 other followers