Le Monde puzzle [42]

October 24, 2010

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

An interesting suduko-like puzzle for this week puzzle in Le Monde thi

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

whose yellow figures are given by

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

and red figures by

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

hence resulting in the yellow-and-red figures

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

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

> sum((apply(lascases,1,rank)>6)*(apply(lascases,2,rank)>6))
[1] 21

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((apply(lascases,1,rank)>6)*(apply(lascases,2,rank)>6))

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

With 10⁵ simulations, I find a range of (5,30)… 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((apply(lascases,1,rank)>6)*(apply(lascases,2,rank)>6))
[1] 40

while, if

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

so the range is (0,40) since there cannot be more than 4 yellow-and-red figures on each row… Simulation (as done above) is simply too costly to reach the whole range.

Filed under: R, Statistics Tagged: Le Monde, mathematical puzzle, sudoku