## Even rows

Posted by Karys on November 13, 2010 – 9:17 am

In a 6×6 grid of crosses :

**x x x x x x
x x x x x x
x x x x x x
x x x x x x
x x x x x x
x x x x x x**

1) Remove 6 xs, so that in each column and each row has an even number of xs. Try removing 8 xs instead of 6.

2) How many such possible combinations are there ?

November 23rd, 2010 at 9:52 am

If the crosses were numbered 1-36 starting at 1 at top left and working left to right along each row ending at 36 at bottom right then removing the following six numbered crosses would leave 4 crosses in each of the top three rows and left three columns, the remaining three rows and columns would be unaffected with 6 crosses in each…..

No’s 1,2,8,9,13 & 15.

This general pattern of removed crosses could be repeated anywhere on the grid and could be rotated through 90,180 or 360 degrees.

You could also arrange them so that they were shifted across the rows (ie squares 13 & 15 could just as easily be 19 & 21, 25 & 27 or 31 & 33)

November 23rd, 2010 at 3:52 pm

For the second part of the problem: When removing 6 xs, I believe there are C(6,3)*C(6,3)*3!=(6*5*4/3!)*(6*5*4/3!)*3!=2400 different combinations. When removing 8xs it becomes more complicated and I don’t have time now to compute it

November 24th, 2010 at 6:48 am

Looks correct to me

My proof :

Let’s consider the rows first. I label them 1), 2), 3), 4), 5), 6).

at first we have :

1) 6 crosses

2) 6 crosses

3) 6 crosses

4) 6 crosses

5) 6 crosses

6) 6 crosses

To remove 6 xs from those 36, we have to remove an even number of xs from any row : 0, 2, 4, 6.

We cannot remove all 6 xs in one row, because when we will consider the columns, that will leave 5 xs par column.

We cannot remove 4 xs from one row either, because, once more considering the columns, there will be 4 of them with 5 xs at this time, and with 2 xs left to remove there will be at least 2 columns with 5 xs left.

So in each row, we can either chose to remove 2 xs or not to remove any. We must therefore chose 3 rows among 6 of them which gives C(6,3) possibilities. Same thing with the columns, chose 3. So there are C(6,3)^2 choices.

finally, there will be 9 possible places for xs after we have chosen the rows and columns. You can show that it will give us 3!=6 choices.

November 24th, 2010 at 10:29 am

My proof is almost the same. First, note that the six removed xs form a “snake”, i.e., start with an arbitrary one of the xs. Then, there should be one more xs on the same row. Take any of them. Then there should be at least one more x in the column of the second one. Take it. Then there should be at least one more on the same row. Take it. Then, again there should be at least one more in the same column, and the last one should be in the same row as the one before it and in the same column as the first one, so that we “close the snake”. Now the main thing is how to compute all the different snakes without repeating or forgetting any. As we saw, only three rows are involved and for each “snake” there is exactly one way to go through it from the higher to the lower row. This rout will be the one we consider. Then we have to choose the three rows by C(6,3) different ways and we have to choose the three columns. The order of the columns matter, because we “code” our snake as (highest row, first chosen column), (highest row, second chosen column), (middle row, second column), (middle row, third column), (lowest row, third column), (lowest row, first column). Therefore for the columns we have variations, not combinations of 3 elements among 6, i.e., 3!*C(6,3).

The same idea works for 8xs, i.e., we have at least C(6,4)*C(6,4)*4! snakes. But here we have more cases, since instead of one snake, we can have two disjoint small ones of length 4 each.For example we can take out the leading up-left 2×2 square and the same square at the bottom right. To form such a snake, we need two rows and two columns so C(6,2)*C(6,2). Then we need one more snake that doesn’t have a common x with the first one. And here it is a little complicated and still haven’t thought of it

November 24th, 2010 at 12:45 pm

Actually the case with the 8 xs is much more complicated (which I realized yesterday, but strangely enough forgot in the previous post). With 6xs we go through only 3 rows, so we can guarantee that there is a “snake” always moving from top to bottom, but with 8xs and respectively 4 rows this may not be the case. Therefore the number of even single snakes of length 8 is much more than my C(6,4)*C(6,4)*4! prediction. Just disregard all my remarks for this case – when I have time and will I will probably come up with the correct formula…