Proving Existence of 2-2 Block in 9-9 Board with 46 Random Red Squares

[vaishakh]

There is 9-9 board of which 46 random squares are selected and colored red. Can anyone of you help me to provehere that there exists a 2-2 block in the board of 4 squares of which 3 are colored red.
Well I proved it. I just wanted to see whether there is any alternative approach. Divide the board into 9 groups of 3-3 blocks. One of the blocks must thus contain 6 squares. If the given condition is not valid in the this block then the middle row must be completely unfilled. There should be atleast one adjoining blocks to one of the completely filled rows. The adjacent row of the other block will thus contain no red squares. Thus the maximum number of red squares the other block will contain is 3. Thus 9 red squars in 2 blocks. 37 red squares are to be remained in the 7 remaining blocks. So 2 more blocks must contain 6 red squares because if any block contain 7 or more red squares then the given condition goes valid. Now there are three sets containing 6 red squares. One block containind three red squares can be adjacent block to two of the blocks but not to the third block. So now there is 1 more block with three red squares. So there 22 remaining red squares in the remaining 4 blocks. So two of the next boxes contain 6 red squares and also the next one contains 3 red squares since 2 blocks of three red squares cannot themselves be adjacent to 5 blocks. And thus now one block is remaining and there are 7 red squares in tat block. So we are done.

 

[neurocomp2003]

yes your proof is fine...its known i believe as the more generalized PIGEONHOLE PRINCIPLE...where 1 of the 9 3x3's contains 6...however I'd shorten your proof...Your explanation after that statement begins to get confusing...Just show that in that 3x3 with 6 reds the 2x2 with 3 reds holds true.

 

[0rthodontist]

Well, the 2x2 with 3 reds does not necessarily hold true in the 3x3 with 6 reds, because as he explained you can have the format
RRR
BBB
RRR

I am unable to prove Vaishakh's problem but I can say that his proof is in need of a lot of refinement. For example, vaishakh, when you're talking about the first 3x3 block of 6 and the other block of 3, the two could be in any of the following four distinct arrangements (each entry is a 3x3 grid as part of a 9x9):
63X
XXX
XXX

36X
XXX
XXX

XXX
63X
XXX

XXX
36X
XXX

In particular, if it's the third of the fourth arrangement, then you can't necessarily say that the other blocks of 6 necessarily have their own blocks of 3. The arrangement could be like this:
X6X
606
X6X
Where the "0" is the "3" earlier--remember that it only has to have AT MOST 3 and could have less.

Your proof needs to be refined some.

 

[neurocomp2003]

ah yeah i forgot about that ...still can be done proving that way...
a little harder because of all the configurations
but nonetheless can be done. Just use a tree structure to show it
start off by stating that the max reds in a 3x3 is 6..show that then branch off each configuration of such a 3x3 with respect to the other 3x3 blocks
RRR
000
RRR

There is only so many configs till it becomes a symmetrical prove...
then "step by step" prove each config type like the way he was doing it.

Might I suggest using a smaller nxm block size. May make the proof easier

 

[vaishakh]

can you please help. I understand. The one adjacent need not be even 3, it could be even 0. I don't understand how to proceed. Probably a small advice from you mighthelp me.

 

[vaishakh]

I found it after disconnecting yesterday. So I couldn't post it.
Anyway my proof does npt goes wrong, because I am just saying that there can be a maximum number of 3 red squares on the block adjacent to the block containing 6 red squares since it has to contain one column without red squares. If it can have one more column without red squares then it is in a special condition. Then the block adjacent to that column can contain 6 red squares. Here adjacent means adjacent to the columns. The block simply being adjacent does not imply anything. But since the adjacent block can contain only atmost 3 red squares, there are still two more blocks with 6 red squares. If it had been less than 3 in that block then I am done anyway because I have already proved that on block can contain utmost 6 red squares if it has not to satisfy the condition. So the one block containing three red squares can imply the existence of utmost only two blocks containing 6 red squares. So there exists one more block containing less than or equal to three red squares. The only condition is the existence of a columnwithout red squres. I am not at all concerned with the column containing red squares in the 3-block.

 

[neurocomp2003]

my suggestion would be to exam 2x2 OR 2x3 blocks

but if you choose to show the 3x3s

show first the configuration neighbouring 6-block, then show whether
3 6 blocks can form an L shape.

Next for the entire 9x9...show where one 6-block can go...orientation specific
(there are only 18)...then realize that you can group some of them because they are identical...count them make sure they add to 18.

then show where the 3-blocks must go relative to that 6 block

I suggestion starting with a blank sheet(writing length-wise for more room) and building a tree...labelling your proof stepps alphanumerically.

once you begin drawing this tree structure you shoudl realize that certain branches
become redundant. And just say see this branch node(A#) to complete the proof of this other branch.

The starting point I suggest is the 6 block in the middle that is the easiest
to prove