Jump to content
BrainDen.com - Brain Teasers
  • 0
BMAD

the distinguished matrix

Question

Imagine you have several distinguishable rows composed of several distinguishable columns

The intersection of the rows and columns either have a 1 or a 0.

Each row sums to the same value and the question is how many of the columns can you eliminate assuming the the 1's in each row are randomly distributed across the columns

Example, there are 30 rows and 20 columns with each row containing 7 randomly dispersed 1's. How many columns can be eliminated reducing the total in each row by no more than 2.

Share this post


Link to post
Share on other sites

5 answers to this question

  • 0

After elimination of columns, do the row totals all still have to be equal (although maybe equal to 6 or 5?)

Share this post


Link to post
Share on other sites
  • 0

No they just need to be distinguishable.

Edited by BMAD

Share this post


Link to post
Share on other sites
  • 0

This sounds a lot, but not exactly, like eliminating variables from sets of equations. Is that the idea?

Share this post


Link to post
Share on other sites
  • 0
On 6/4/2018 at 6:00 AM, bonanova said:

This sounds a lot, but not exactly, like eliminating variables from sets of equations. Is that the idea?

yes.

Share this post


Link to post
Share on other sites
  • 0

Scratching the surface...

when we start, the average column sum is 210/20 = 10.5

we are moving from row sums of 7 down to row sums no less than 5. This implies we are removing columns totaling no more than 60. So a rough estimate of the number of columns removed is 60/10.5, or roughly 6.

Another way of visualizing this argument is to imagine the first step in the removal. Pick a row, pick two of the 7 1-cells, and remove those columns. Now, to avoid reducing this row sum below 5, we must “freeze” the other 5 columns. 

Now pick another row, and two of its 7 1-cells, and remove those two columns. Now we have removed four columns, and frozen 10. There are only 6 left, so we can do the same once more, resulting in 6 columns removed.

I admit, there might be some overlap between frozen columns, so that there might be more than 6 columns left after removing four columns, but it seems like at least 6 can be removed.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.

×