1
$\begingroup$

Mark paints squares of a white $10 \times 10$ board. He can either paints some vertical row of squares blue or some horizontal row red.(Every row is painted at most once).

If blue paint is put on top of the red paint, it becomes a blue square. If red paint is put on the blue paint, the squares react and lose their color, and a white square is made.

Could there be $33$ red squares some time?

I tried considering small cases $n=2k$ for small $k$'s, and I feel it's done by induction, but I couldn't do it. How is it done?

$\endgroup$
0
3
$\begingroup$

No, it's impossible. To see this, we argue by contradiction. First, note that the order of the blue and red paint doesn't matter; in either case, an overlap of blue and red paint will result in a loss of one red square.

Now suppose that Mark paints $r$ red horizontal rows and $b$ blue vertical rows. Then at the end, the total number of red squares will be: $$ 33 = 10r - rb = r(10 - b) $$

Thus, since $r \in \{0, 1, 2, \ldots, 10\}$ and $r$ is a factor of $33$, we know that either $r = 1$ or $r = 3$. In the former case, we have that $10 - b = 33$ so that $b = -23$, which is absurd. In the latter case, we have that $10 - b = 11$ so that $b = -1$, which is also absurd. So it's impossible to get $33$ red squares.

$\endgroup$
2
$\begingroup$

This answer is pretty much the same as Adriano's, with more words and less notation.

First notice the parenthetical comment that each row (horizontal row) or column (vertical row) is painted at most once. That's important, because it means that after Mark is done painting, every square has been painted in one of five ways:

  1. Not at all (so it's white)
  2. Once, with blue
  3. Once, with red
  4. Twice, first red, then blue (so it's blue)
  5. Twice, first blue, then red (so it's white)

A first try at solving the problem might be to figure out how many squares there are in each of these categories, given a description of what Mark painted, say "He painted row 1, column 2, column 4, row 3, column 3, row 8, and row 7, in that order."

  1. Squares whose row and column were both never painted
  2. Squares whose column was painted, but whose row was not.
  3. Squares whose row was painted, but whose column was not.
  4. This is complicated.
  5. This is complicated.

Fortunately, only #3 leaves a square red, so we don't have to figure out the complicated stuff. The number of squares in category #3 are only in rows that were painted, and there are the same number of them in each of those rows: $10$ minus the number of columns that were painted.

So the total number of red squares is (number of rows painted)$\times$($10-$ number of columns painted). If there are $33$ red squares, these two factors have to multiply to $33$, but each factor is between $0$ and $10$, and that's impossible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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