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]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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
}

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 their blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.



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.

Search R-bloggers

Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)