Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have got a big chess board ($N \times N$).
We choose any correct combination of $2N-1$ fields (let's call them special). At least one field is chosen in each row and column.

Prove that

1) we can color some of the special fields such that in each row and each column the number of colored fields is odd

At least one special field must be coloured in each row and column.


Consider a chessboard $4 \times 4$.

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Then we chosse $2n-1 = 7$ special points on chessboard. (Let be special point 1).

1 0 0 1
0 1 0 0
1 1 1 0
0 0 0 1

Now we can color some special point with $(1)$ or $(2)$ condition. In this example it will be $(1)$.

So, the solution is :

2 0 0 1
0 2 0 0
1 1 2 0
0 0 0 2

So, it's possible to color some of 7 points with $(1)$ or $(2)$ condition :)

Explain by Brian M. Scott :

You have a binary $n \times n$ matrix with $2n−1$ ones. The claim is that you can always find a subset S of the ones such that S hits every row and every column, and either every row and column contains an odd number of members of S, or every row and column contains an even number of members of S. (The ones are the special points, and S is the set of special points that you color.)

One more example (for n = 3 ):

0 0 0 0
0 0 0 0
0 0 0 0

We choose $2n-1$ points :

1 0 0 1
1 1 0 1
0 1 0 0

Then we can color it simple like this :

2 0 0 1
1 1 0 2
0 2 0 0


share|improve this question

closed as not a real question by joriki, Michael Joyce, Hagen von Eitzen, Brian M. Scott, Thomas Oct 21 '12 at 23:47

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

There must be something missing -- the number of special fields in each row and column doesn't depend on how we colour them. –  joriki Oct 21 '12 at 20:21
number of special fields is in each row and column is any number > 0. –  John Smith Oct 21 '12 at 20:25
I’m sorry, but I’m still confused. Can you give a small example, say with $n=3$? –  Brian M. Scott Oct 21 '12 at 20:31
Surely (2) is impossible, because each row must have at least two coloured fields, but we only have $2N-1$ special fields? What a mess... –  TonyK Oct 21 '12 at 21:14
I've now voted to close as not a real question. Unfortunately all efforts at clarifying the question have only led to further confusion. The second example clearly does not fulfill the requirements; it doesn't even show an $N\times N$ board. From comments under Alan's answer, it appears that the conditions are to be fulfilled only for some choice of special fields, in which case the question would be trivial. @John, if you still have a question you want answered, please make a far more careful effort to express it in a form in which it will be comprehensible to others. –  joriki Oct 21 '12 at 22:10

1 Answer 1

I may be misunderstanding the question, but I see two interpretations, one of which makes the problem trivial while the other makes it impossible by making the claim false.

First intepretation - Not obligated to color at least one special field in each row and column: In this case, the assertion is trivial, since one can just leave everything uncolored, and so every row and column has an even number (zero) of colored special fields.

Second interpretation - Obligated to color at least one special field in each row and column: In this case, the OP's assertion is not always true. For example, consider the 6-by-6 grid given by

1 1 0 0 0 0 
1 1 1 1 0 0
0 0 1 1 0 0
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 0 1

where the 1's denote special fields. This grid has 11 special fields, so it satisfies the hypotheses of the problem. I claim one cannot color the special fields to satisfy either (1) or (2). To see this, observe that one is forced to color the special fields in the bottom three rows. But now the rightmost column has an odd number (one) of colored fields whereas the adjacent column has an even number (two).

share|improve this answer
Your second interpretation is good. But it's not correct. We assume that we choose any combination of 2n-1 special points not one case. It's clear? –  John Smith Oct 21 '12 at 21:48
@John: That makes no sense. If you're saying that you just want to prove that there is some choice of special fields such that the colouring is possible, that's entirely obvious (the choice just has to include the diagonal); also in that case there would be no need for case 2). –  joriki Oct 21 '12 at 21:54
there's no need for case 2, i deleted it. –  John Smith Oct 21 '12 at 21:57
assume that combination is correct. It's make sanse again :) –  John Smith Oct 21 '12 at 22:01
@JohnSmith: What do you mean by "correct"? –  Alan Guo Oct 21 '12 at 22:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.