All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Table's peculiarity (Posted on 2015-11-29) Difficulty: 3 of 5
Prove that no matter how each cell of a 5 x 41 table is filled with a 0 or 1, one can choose 3 rows and 3 columns which intersect in 9 cells filled with identical numbers.

Prove that 41 is the lowest possible n for 5 x n table; i.e., the statement is not true for a 5 x 40 table.

Source: Colorado math contest.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution A little hand-waving (spoiler) | Comment 1 of 6
Well, it is clear that 40 is not enough.  There are 10 ways to arrange 3 0's and 2 1's, and another 10 ways to arrange 3 1's and 2 0's.  If we have 2 of each of those in a 5 by 40 grid, there are clearly not three rows and columns that intersect in 9 identical numbers.

It is not hard convince myself that 41 is enough, with a little hand-waving.  No matter what 41st row is added to the above grid, there are three rows and columns that intersect in 9 identical numbers.  And the situation can hardly get better if any of the above rows are changed to 4 or 5 identical numbers.  Not a rigorous proof, I know.

  Posted by Steve Herman on 2015-11-29 11:07:53
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information