Sit next to me
Example of an arrangement that follows the rule.
In a 4 × 4 grid, each cell is colored either pink or blue such that each cell shares an edge with at least two cells of the same color.
Is it necessarily true that there is a 2 × 2 square in the grid of one color?
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.
4 solutions
This problem, the way it is worded, is incorrect. There exists a solution that satisfies the condition that "each cell is colored either pink or blue such that each cell shares an edge with at least two cells of the same color." And does not have a 2x2 square of one color. That solution is trivial and is given by setting all the squares to the same color! The way to make this problem interesting is to add the condition that at least one square of each color is present. Before asking a logical question please make sure your logic is accurate and does not contain trivial counter examples!
Log in to reply
I agree. That's why I got it wrong. I saw other solutions of 2 2x2 squares. And all one color.
By saying that does this contain a 2 by 2 square, I do not necessarily mean that this square cannot be contained in larger square or a rectangle. There is no reason to assume this.
Correct! The problem should have stated that both colors were present.
Log in to reply
But if only one colour was present, there would for sure be a 2 × 2 grid of one colour.
Isn't square 12 required to be pink since squares 10 and 11 must share edges with two other pink boxes?
Now, this still makes your result hold since that results in a 2x2 square in the center of pink.
Log in to reply
Yes, that is a condition that means that the answer is "Yes". I simply decided to use other factors to prove it. I could have done this, and this furthermore reinforces the answer
This is more a challenge on how to create assumptions that remove ambiguity from the question.
rule does not state there must be two colors represented, just that they could be either color. All blocks of each color fulfills the requirement and makes the not necessarily answer at least as correct as the answers posted. Ambiguous question, no clear correct answer
Log in to reply
What Trea said. The squares must be pink or blue, but no requirement that there be at least one of each color.
Ditto Trea; it is an ambiguity in the problem as stated.
If all cells are blue, then it is necessarily true there is a 2x2 block of blue. Or if all cells are pink then it is necessarily true that there is a 2x2 block of pink. I guess you misunderstood "There is a 2x2 block of one color" to mean "There are 2x2 blocks of both colors" ?
However, if only 1 colour was represented, this would make the answer "Yes it's true" automatically
Just saw that you have the exact same objection. I answered "incorrectly" because of this in precise statement of the problem.
I think you misunderstood the rule of this question. In example, it was possible to make 4x4 square.
Log in to reply
I think the question should be rephrased, all blue or pink meet the criteria without a 2x2. It is a trivial solution but correct.
You can make this same argument just using cells 0,1,2, then 4,10,11, then 12,13,14,15
Good explanation
how about putting the pink squares in 2, 4, 12 and 13?
Log in to reply
Then, each pink would only have 1 other pink neighbour, not 2 as required
This was my approach exactly. Amazing!
i think you are very skillful in power point.
I looked at the pink section. There is a 2x2 square.
Very neatly done. I knew that this was the right answer, that you 'tied yourself in knots' by trying it, and that it couldn't be done, but I didn't answer the question as precisely as this. Very good. Regards, David
"each cell shares an edge with at least two cells of the same color" could be changed to "each cell shares an edge with at least two cells of the same color as that cell" for more clarity.
Here is some alternative reasoning. Assume for sake of contradiction that there does not exist a 2x2 square, all the same color. Then consider a group of cells, all connected and all the same color. Since this group cannot contain a 2x2 square, this group must be form a "loop". But this loop must enclose another, smaller group of connected cells, all of one color (a different one). And since this smaller group can't contain a 2x2 square either, it's a loop. We can't do this forever, so clearly there is a contradiction.
Note that this neatly generalizes to larger grids.
The answer is "not necessarily true," because all blue or all pink would fulfill the requirements of this scenario. Nowhere does it say that both colors must be included.
Log in to reply
On the contrary. I believe you are interpreting the problem as such: "If we choose some color, either blue or pink, must it be true that there must exist a 2x2 subgrid, all of that one color?"
However, this interpretation is awkward in the assumption that you may choose what color to use, and furthermore, it makes the problem way too trivial for the exact reason you came up with. A better interpretation would be: "Does there exist a 2x2 subgrid, all of one color?" In this interpretation, the "all pink" configuration is satisfied, since there is obviously a 2x2 subgrid of pink cells, and the "all blue" configuration is satisfied likewise.
Consider a square of four adjacent small squares instead of this square. For this condition to be true, there must be at least three adjacent squares of the same colour to share an edge. But if we do like this, the remaining square will not have any adjacent squares of the same colour. The same is applicable to the square mentioned in this problem. Hence the condition is necessarily true.
what about if there is only one color there is no requirement to have two colors
Just because your reasoning works for the 2x2 case, does not mean you can extend it to the 4x4... Can you explain how your reasoning also applies to the 4x4?
Aren't you getting lost in needless complexity? The original presentation includes the desired result, therefore it IS possible, rendering all the below gyrations moot. Or am I missing something?
It asks if it is necessarily true. That means in any configuration that fulfills the conditions, not just the one shown.
Log in to reply
Top 8 pink, bottom 8 blue is a true configuration (there are 4 such configurations). While the argument might be that those patterns contain a 2x2 square within them, the question does not specify whether the evaluated shape is the perimeter of the color field or a matchable pattern from the colored blocks; as such, the term "necessarily" implies both methods of evaluation must be contested to make this absolutely true. In the perimeter test, the only shapes that exist in these 4 patterns are 2 2x4 rectangles so the correct answer should have been "No, not necessarily".
Log in to reply
I have no idea what you mean by "the perimeter test" here.
Perhaps you are thinking of interpreting it as "rectangle such that each of the corners has the same color"? That would require a different text. The corners of a 2 by 3 rectangle are not in any sense a 2 by 2 block.
The original presentation is only one example of 2 1 6 (65536) possible presentations where 16 cells are involved. If among the 2 1 6 possible presentations you can find a presentation where "each cell shares an edge with at least two cells of the same color" is satisfied without using "2x2 grid of cells with the same color" then such a grid would be indeed unnecessary. However no such presentation exists among the 2 1 6 possible presentations, therefore such a grid is indeed necessary to satisfy the condition.
We will prove this by avoiding having a 2 × 2 sub-grid at all costs (contradiction), and seeing if there becomes a case when there needs to be one.
Without loss of generality, let us make the top left corner blue. Even if I called it pink, the outcome would be the same, only having the colours reversed.
In the above diagram, look at the squares labelled 1 and 2. The square already coloured must have at least two neighbours of the same colour (blue). As it has only 2 vertical/horizontal neighbours, both squares 1 and 2 must also be blue:
Now, the square labelled 4 cannot be blue as this would create a 2 × 2 sub-grid (which we are trying to avoid). Therefore, square 4 is pink. Looking at squares 1 and 2, we see that they only have 1 neighbour of the same colour. As they both each only have 1 neighbour square yet to be coloured, squares 3 and 5 must satisfy this condition, hence making them blue:
As the corner squares of the grid only have two neighbours, and each square needs to have at least two neighbours of the same colour, each corner square is the same as its neighbours. Hence, squares 6 and 7 from the diagram are also blue. Also, the neighbours of squares 6 and 7 are blue, shown as 8 and 9 in the below diagram:
Now considering squares 10 and 11, if either of them were blue, then the top right or bottom left sub-grids would be all of one colour. Therefore, they must be pink:
Square 12 cannot now be pink, as the central sub-grid would be all one colour. Hence it is blue:
The squares now named 13 and 14 cannot be pink, as it wouldn't be possible for them each to have at least two pink neighbours, with the children seated as they currently are. Hence, they are blue:
This final diagram gives us 1 square left to fill, square 15. It cannot be pink as it wouldn't have two similar neighbours. However, if it was blue, then the bottom right sub-grid would be all blue.
By filling the squares using this logic, we can see that not having a sub-grid is impossible, hence there must always be a 2 × 2 grid such that everyone is of the same gender. Notes: Rotating the grid by a quarter turn can be done, as well as swapping the colours. However, this will not affect the logic whatsoever.