Tell me more ×
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.
up vote 1 down vote favorite

Some points on (integer, rectangular) grid in a plane are colored white, some black and some are not colored.
In each step, one vertical or horizontal line can be selected, and all colored points on that line would toggle their color.
Prove there is a finite sequence of steps after which on every vertical or horizontal line number of black and number of white points differs by 1 at most.

share|improve this question
What is a line? Is it a line segment of an arbitrary finite length, a fixed finite length, length one, or of infinite length? – Qiaochu Yuan Aug 12 '10 at 3:09
Very likely, it's a m-by-n grid, vertical line' means all points (x,y) for some x and $1 \le y \le n$, horizontal line' means all points (x,y) for some y and $1 \le x \le m$. – rgrig Aug 12 '10 at 8:40
Where'd you get the question from? – Casebash Aug 12 '10 at 11:09
If we assume that a particular grid can be solved - unlike in the counter-example I posted below - the maximum number of moves to solve would be $\lfloor \frac m2 \rfloor + \lfloor \frac n2 \rfloor$. The monochromatic grids of size m-by-n satisfy this bound. – Joshua Shane Liberman Aug 12 '10 at 11:53
@Casebash Colleague gave it to me. Maybe I missed something, I'll check with him. – n0vakovic Aug 12 '10 at 12:41

1 Answer

up vote 5 down vote accepted

What sequence of horizontal or vertical steps would lead

B W

W W

to have the number of black and white points almost even?

share|improve this answer
2  
+1. It is a very nice counterexample! Any row or column toggle will preserve the 1-to-3 ratio, and so there can be no solution in this case. – JDH Aug 12 '10 at 4:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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