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.
October 27, 2010 at 2:15 pm
Here is a matrix which reaches the upper bound of 40:
where the x’s represent the numbers from 0 to 59.
October 27, 2010 at 2:20 pm
Robin really looked at the problem! And, as always, found the solution! Merci.
October 25, 2010 at 3:16 am
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
October 25, 2010 at 8:22 am
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!