Le Monde puzzle [42]

October 24, 2010
By

(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 105 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

To leave a comment for the author, please follow the link and comment on his blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , , , ,

Comments are closed.