Help: Bijection in combinatorics
I came across one of Yu Fei Zhao's combinatorics handout problems as follows:
Form a 2000×2002 screen with unit screens. Initially, there are more than 1999× 2001 unit screens which are on. In any 2 × 2 screen, as soon as there are 3 unit screens which are off, the 4th screen turns off automatically. Prove that the whole screen can never be totally off.
Can someone help me on this problem? I suppose that there's a bijective proof, but maybe there's other ways of proving it?
Note by
ChengYiin Ong
1 year, 7 months ago
No vote yet
1 vote
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"\(...\)or\[...\]to ensure proper formatting.2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
I'm going to refer to screens that are on or off as white and black screens respectively.
Let a white or black region be a set of white or black screens such that any two screens from this set can be linked, by moving in steps from one screen to a screen that shares a side and repeating such moves.
Consider a black region and imagine drawing the smallest possible rectangle that contains all screens from this region and lies along the grid lines.
?1 In the process of turning screens off, the black region expands. However, it will never expand beyond the boundary of its rectangle. This is because in order to turn off a screen outside the rectangle, there would have to be a 2×2-square with all other screens turned off. This can't happen because any such square will contain at least one other screen outside the rectangle, which is off (as it would be part of the region otherwise).
This means that any region can only expand inside its rectangle. For the entire screen to be turned off, any screen must be inside some rectangle. Hence the black regions have to span the entire screen in both directions (left-right and top-bottom).
?2 So, there must be at least 2000+2002−1=4001, however we are only allowed to use 2000⋅2002−1999⋅2001−1=4000 black screens. Since this isn't enough, the screen can never be completely turned off.
Log in to reply
There are still two gaps in my reasoning, marked with ? at the beginning of those paragraphs.
?1 Sometimes a region can in fact expand beyond its rectangle when there are single black screens just outside the rectangle.
?2 Obviously there must be at least 2002 black screens so that each row and column has at least one of them. But why do we need almost twice as many to actually cover the entire screen with rectangles?
Log in to reply
Maybe we can consider if the rectangle has no black screens at its sides outside of it, then the black region will surely won't expand out of the rectangle because given any square outside of the rectangle, it must have at most 2 white screens and 2 black screens. So, the rectangle is actually just the whole 2000x2002 screen and we need to prove that we need at least 2000+2002-1=4001 black screens to turn off the whole screen. My recent reasoning is as follows:
Consider the smallest case when the screen is a 2x4 screen and we are given at most 2x4-1x3-1=4 black screens. Clearly, we can't fill the entire screen in every single possible way of placing the black screens. However, we can find out that we can at most turn off 2x3 unit screens by placing 3 black screens on the first column and the last screen on the first row, second column since by what we concluded before the black region or the rectangle must be the whole screen which means every row must have at least 1 black screen but if that's the case, we will find that every square in the rectangle will only have 2 black screens. Thus, we must add 1 more black screen to one of the squares in the rectangle so that the 4th white screen will turn black and it's in a different row with the added black screen. Then, the another square will have three black screens and this process continues until the whole screen is turned off!
Consider the case when we have k(k+2) unit screens and we are given at most k(k+2)-(k-1)(k+1)-1=2k black screens. Then by the same reasoning as the smallest case, place k black screens on the first column and fill the first row with the remaining k black screens but we will lack of a black screen since we can only fill the first row with k+1 black screens, which means we can only turn off at most k(k+1) unit screens. Again, by the same reasoning as the smallest case we considered, we need at least k(k+2)-(k-1)(k+1)=2k+1 black screens in order to turn off the entire screen. Thus, when we have (k+1)(k+3) unit screens, we can conclude that we need at least 2(k+1)+1 black screens but we are only given 2(k+1) unit screens, so the whole screen can't be turned off.
At last when k=2000, the whole screen cannot be turned off with more than 1999x2001 unit screens turned on. Q.E.D.
Correct me if there's any mistake.
Log in to reply
I think this is the complete proof! Now, what did you have in mind when you thought of a possible bijective proof? Do you have any ideas about what kind of bijection we could use?
Log in to reply
I haven't came up a bijective proof yet, but I think the proof is good enough, anyway, thx for your idea!