A probability problem by karandeep singh ludhar
A 7 × 7 grid is given with its four corners deleted. All 45 squares are initially white. What is the smallest number of squares which should be colored black so that an uncolored (white) 5-square cross cannot be found?
Note: A 5-square cross is also known as the X-pentomino .
Note : Adapted from bulgaria olympiad.
The answer is 7.
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.
1 solution
We claim that the answer is 7 . To do this, we need to show that 7 is enough, but 6 isn't.
The first part of the proof, showing 7 is enough, is simple:
The second part of the proof, showing 6 is not enough, is substantially harder.
First, we can pack 6 X-pentominoes into the grid such that none overlaps. (Ignore the circle.)
One black square must be in each of these pentominoes (otherwise the pentomino is fully white, contradicting the conditions), so all other unused squares must remain white. By rotating the grid and trying in all four directions, we obtain the following squares (blue) which must be white, and thus the central square must be black (to avoid a pentomino in the center).
Note that this black square contributes to the middle green X-pentomino in the previous picture (marked with the circle), and thus the other squares of that pentomino must be white as well (if there are two black squares there, there are not enough black squares to cover the remaining pentominoes). Once again rotating around in four directions, this gives no less than 32 squares guaranteed to be white, leaving only 12 undecided squares. There are 5 black squares among these.
Now consider the 6 pentominoes with centers marked above. Each pentomino has two undecided squares; one of them must be black. No two pentominoes share any undecided squares, so each remaining black squares can be mapped to a pentomino. But there are only 5 black squares while there are 6 pentominoes, contradiction.
This proves that 7 squares is the minimum.