Learning starts with a question. Asking is a signal for knowledge request!
First time here? Checkout the FAQs!

*Math Image Search only works best with SINGLE, zoomed in, well cropped images of math. No selfies and diagrams please :)

0 like 0 dislike
On an arbitrarily large rectangular table, \(n\) cells are given. Prove that it is possible to colour these cells with two colours (red and blue) so that in each row or column the number of red squares differs from the number of blue squares by at most 1 .
in Data Science & Statistics by Platinum (102k points) | 145 views

1 Answer

0 like 0 dislike
Best answer
The statement is trivial for \(n=0\) or \(n=1\) (the word "trivial" should be used with great care, but here it might be appropriate). For larger values of \(n\), we distinguish three cases:

1. Four of the given cells form a rectangle. Then we colour all the other cells according to our rule (which is possible by the induction hypothesis) and colour two diagonally opposite cells of the rectangle red and the others blue, which yields a feasible colouring.

2. Three of the given cells are the corners of a rectangle (the fourth is not among the given cells). Remove these three cells, add the fourth corner of the rectangle instead, and colour the cells according to the induction hypothesis. If the added cell is red (blue), we colour the adjacent corners of the rectangle red (blue) and the opposite corner blue (red), which again yields a feasible colouring.

3. If none of the above cases applies, choose any row or column that contains more than one given cell (if there is no such row or column, we can colour the cells arbitrarily). The squares of this row (column) are coloured in such a way that the number of red cells differs from the number of blue cells by at most 1. All the other cells are unaffected, so that we can colour them in a feasible way according to the induction hypothesis again.
by Platinum (102k points)

Related questions

0 like 0 dislike
1 answer
1 like 0 dislike
1 answer
0 like 0 dislike
1 answer
1 like 0 dislike
1 answer
3 like 0 dislike
1 answer
asked Apr 13, 2021 in General Knowledge by anonymous | 1.2k views
1 like 0 dislike
1 answer
1 like 0 dislike
0 answers
1 like 0 dislike
1 answer
asked Aug 25, 2020 in Life Sciences by CT Silver Status (24.7k points) | 247 views
0 like 0 dislike
1 answer

Join MathsGee Q&A, where you get instant answers to your questions from our AI, AstraNova and verified by human experts. We use a combination of generative AI and human experts to provide you the best solutions to your problems.

On the MathsGee Q&A, you can:

1. Get instant answer to your questions

2. Convert image to latex

3. AI-generated answers and insights

4. Get expert-verified answers

5. Vote on questions and answers

6. Tip your favorite community members

7. Join expert live video sessions (Paid/Free)

8. Earn points by participating

9. Take a course

10. Enjoy our interactive learning resources

Posting on the MathsGee Q&A

1. Remember the human

2. Act like you would in real life

3. Find original source of content

4. Check for duplicates before publishing

5. Read the community guidelines

MathsGee Q&A Rules

1. Answers to questions will be posted immediately after moderation

2. Questions will be queued for posting immediately after moderation

3. Depending on the number of messages we receive, you could wait up to 24 hours for your message to appear. But be patient as posts will appear after passing our moderation.

MathsGee Q&A


Social Proof

Web Analytics