Jump to content
BrainDen.com - Brain Teasers
  • 0

Black and white square table


BMAD
 Share

Question

11 answers to this question

Recommended Posts

  • 0

 

It's not possible, but <=75% is possible.

Is this claim for any nxm table or only when n = m ?

 

 

For any nxm. I don't have a rigorous proof, but I think it would go along these lines...

Suppose that there is a way to fill a rectangle as per OP requirements. Every row and every column will have a dominant color. Rearranging rows and columns doesn't change the number or ratio of black/white squares in each row/column, so we can rearrange rows in such a way that all black-dominant rows are on top and all white-dominant rows are on the bottom. Similarly, we can rearrange columns, so that all black-dominant columns are on the left and white are on the right. Using gavinksong's notation the rectangle would look like this:

 

XXXO

XXOX

XOOO

OXOO

 

Now, four quadrants have been established. Those quadrants will not necessarily have the same size, and that's where the proof gets tricky, but the idea is that the top left quadrant is all black and bottom right quadrant is all white. The other 2 quadrants are mixed colors. Let's look at the top right quadrant. It belongs to the black-dominant rows and to white-dominant columns, so to achieve balance it should be a 50/50 mix of black/white. Of course, the actual distribution of colors may be off balance especially if the whole black/white quadrants are not the same size, but since the total number of black squares equals the total number of white squares, it can be shown that if one color exceeds 75% in every row then the opposite color will be less than 75% in some columns or vice versa.

Edited by k-man
  • Upvote 1
Link to comment
Share on other sites

  • 0

 

 

It's not possible, but <=75% is possible.

Is this claim for any nxm table or only when n = m ?

Does OP ask for every nxm, or a particular nxm?

 

 

Fair question! The way I wrote the OP, I only asked if one exists.  I am seeking to extend the OP to see if the above conjecture(s) extends to any nxm and if not, what nxm does it work for?

Link to comment
Share on other sites

  • 0

 

 

 

It's not possible, but <=75% is possible.

Is this claim for any nxm table or only when n = m ?

Does OP ask for every nxm, or a particular nxm?

 

 

Fair question! The way I wrote the OP, I only asked if one exists.  I am seeking to extend the OP to see if the above conjecture(s) extends to any nxm and if not, what nxm does it work for?

 

 

Hmm. So is k-man's answer not correct?

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...