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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We are given an $18*18$ table, all of whose cells may be black or white. Initially all the cells are colored white. We may perform the following operation: Choose one column or one row and change the colour of all cells in this column or row. Is it possible by repeating the operation to obtain a table with exactly $16$ black cells?

I know that this question is based on invariant principle but I am not getting the invariant.

share|cite|improve this question
2  
The smallest values you can get are: $0,18,34,36,50,54,64,66,72$ – Henry Jan 16 at 1:14

First notice that the order in which we perform the row/column operations doesn't matter and that using two times the same column/row does nothing. Now suppose we can make $16$ black cells using $r$ row-moves and $c$ column-moves. Imagine to color the columns and rows we used, every coloured cell is now black, except the cells coloured 'two times' that are white. The total number of coloured cells is $$18(r+c)-rc.$$ The number of cells coloured two times are $rc$. So the total number of black cells are $$18(r+c)-2rc.$$ Now we have to solve (for $0\le r,c\le18$) $$18(r+c)-2rc=16$$ that can be rewritten as $$r=9-\frac{73}{9-c}.$$ Since $r$ must be a integer, we have that $(9-c) \mid 73$, the only possibility is $c=8$, but we would have $r<0$. Hence there are no solutions.

EDIT: As pointed out by @filipos we must consider also the case $c=10$, which gives $r>18$ and so it has to be discarded.

share|cite|improve this answer
4  
At the last step, you should also consider $c=10$. This also fails because then $r > 18$. – filipos Jan 15 at 16:06
3  
You can also write it as $(9-r)(9-c)=73$, if you want to avoid rational numbers. – filipos Jan 15 at 16:10
1  
But why are we limiting ourselves to two recolorings? If we choose Row 1 and turn them all black, then Col 1 and turn them all black, but making (1, 1) white, then choose Col 3 making all of (x, 3) black except (1, 3) which becomes white again, then choose Row 1 a second time, making (1, y) all white except (1, 1) and (1, 3) which become black, we can change the number of black cells considerably through these types of iterations. That's not reflected in your equation, and I didn't see it as a rule in the OP. – Jesse Williams Jan 15 at 16:56
4  
@JesseWilliams, note that the sequence of operations you describe does the same as just choosing columns 1 and 3 (and not row 1 at all). That's what the answer means when it says "First notice that the order in which we perform the row/column operations doesn't matter and that using two times the same column/row does nothing.". – msh210 Jan 15 at 17:51
    
I have tried this on smaller grids and get a different formula for the number of black cells left. My reasoning is this: – Harry Weston Jan 20 at 18:52

Well, mrprottolo gave a similar answer, but not identical, and I already typed this out, so I'll hit "Post" anyway!


First of all, note that these operations commute with each other! Second, by shuffling the rows and columns as necessary, we can assume that only the first $m$ rows and the first $n$ columns are flipped.

So how many black cells are there? Measure the two rectangles: $$n(18-m)+m(18-n)=18m+18n-2mn$$ Setting that equal to $16$, we get: $$9m+9n-mn=8$$ Conclude that both $m$ and $n$ are even, and neither is a multiple of $3$. So $m\geq 2$, and by symmetry, we can assume $m\leq 9$, which forces $m\leq 8$. But $$n=\frac{9m-8}{m-9}$$ is negative on that range, a contradiction.

share|cite|improve this answer

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.