BMAD Posted February 3, 2015 Report Share Posted February 3, 2015 Is it possible to fill a rectangular table with black and white squares (only) so, that the number of black squares will equal to the number of white squares, and each row and each column will have more than 75% squares of the same colour? Quote Link to comment Share on other sites More sharing options...
0 k-man Posted February 9, 2015 Report Share Posted February 9, 2015 (edited) 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 February 9, 2015 by k-man 1 Quote Link to comment Share on other sites More sharing options...
0 k-man Posted February 3, 2015 Report Share Posted February 3, 2015 It's not possible, but <=75% is possible. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted February 3, 2015 Report Share Posted February 3, 2015 Only in case the table's dimensions are rational: length/width = p/q. Now for the head scratching. Quote Link to comment Share on other sites More sharing options...
0 gavinksong Posted February 8, 2015 Report Share Posted February 8, 2015 X - BLACK O - WHITE XXXO OXOO OOXO OXXX Quote Link to comment Share on other sites More sharing options...
0 gavinksong Posted February 9, 2015 Report Share Posted February 9, 2015 i think kman is right. interesting. Quote Link to comment Share on other sites More sharing options...
0 BMAD Posted February 9, 2015 Author Report Share Posted February 9, 2015 X - BLACK O - WHITE XXXO OXOO OOXO OXXX This is a good attempt but is only equal to. Quote Link to comment Share on other sites More sharing options...
0 BMAD Posted February 9, 2015 Author Report Share Posted February 9, 2015 It's not possible, but <=75% is possible. Is this claim for any nxm table or only when n = m ? Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted February 10, 2015 Report Share Posted February 10, 2015 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? Quote Link to comment Share on other sites More sharing options...
0 BMAD Posted February 10, 2015 Author Report Share Posted February 10, 2015 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? Quote Link to comment Share on other sites More sharing options...
0 gavinksong Posted February 10, 2015 Report Share Posted February 10, 2015 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? Quote Link to comment Share on other sites More sharing options...
0 BMAD Posted February 10, 2015 Author Report Share Posted February 10, 2015 his answer is right. i was just asking if it extends. If i marked "answered" then no one would look at this question any more. 1 Quote Link to comment Share on other sites More sharing options...
Question
BMAD
Is it possible to fill a rectangular table with black and white squares (only) so, that the number of black squares will equal to the number of white squares, and each row and each column will have more than 75% squares of the same colour?
Link to comment
Share on other sites
11 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.