There are nine 3 × 3 sub-grids in the 5 × 5 grid. If at most 5 out of 9 unit squares are shaded blue in any 3 × 3 sub-grid, what is the maximum number of unit squares in the 5 × 5 grid that can be shaded blue?
Note : An example of how the grid can be shaded is shown to the right.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
This solution uses a common technique in solving logic puzzles informally called a critical point . Generally, a critical point is one where a particular assumption directly leads to a contradiction (either immediately or through a chain of steps), allowing us to know the opposite must be true. Critical points tend to be found at "extreme values" that represent some maximum or minimum; in this case, the center is part of every one of the 3 by 3 sub-grids, so is a very good candidate.
That's a very fast proof, and nice variant of the optimal shading!
Note: I think what you mean is "If the centre square is white, then there have to be at least three white squares in each of the yellow and green regions.
Log in to reply
Typo corrected. Thanks. My optimal grid has exactly five blues in each sub-grid, unlike Jon's.
I find it interesting that three of the 3-by-3 squares fail to have the maximum of five blue squares possible for this correct solution.
I will show that the maximum is 18. FIrst, the diagram below shows that 18 is possible
Now, we will show that we cannot select 19 or more squares. Suppose not.
Let
a
,
b
,
…
,
i
denote the number of blue squares in the regions shown below.
Then a + e + h + i e + b + i + f h + i + d + g i + f + g + c ≤ 5 , ≤ 5 , ≤ 5 , ≤ 5 , so a + b + c + d + 2 e + 2 f + 2 g + 2 h + 4 i ≤ 2 0 .
Suppose there were at least 19 blue squares, so 1 9 ≤ a + b + c + d + e + f + g + h + i . Then from the two inequalities above, e + f + g + h + 3 i ≤ 1 . This tells us i = 0 , so e + f + g + h ≤ 1 . But a , b , c , and d are all at most 4, so a + b + c + d + e + f + g + h + i ≤ 4 + 4 + 4 + 4 + 1 + 0 = 1 7 , contradiction. Therefore, 18 is the maximum.
The Qiana Kong
Whilst the answer is correct, the diagram appears to be incorrect.
Log in to reply
What is wrong with the (top?) diagram? It satisfies the condition of "at most 5 out of 9 unit squares are shaded blue".
Log in to reply
I was reading as 5 out of 9 being shaded blue, which Mark's diagram below shows, so yes reading at most 5 out of 9 then yes it is correct, my misreading of it.
Problem Loading...
Note Loading...
Set Loading...
If the centre square is blue, there have to be at least four white squares in the yellow region, and at least another four in the green region. Thus there would have to be at least eight white squares, which means that the number of blue squares could not exceed 1 7 .
If the centre square is white, then there have to be at least three white squares in each of the yellow and green regions. This means that there have to be at least seven white squares, and hence at most 1 8 blue squares. The second diagram shows that 1 8 blue squares are possible.