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

7 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
  • 0

While this doesn’t answer the question with randomly placed 1s, I think it does give an upper bound to the number of columns that can be removed.

What is the smallest number of remaining columns that would allow (a) the 30 rows to be distinct, (b) each row to have 5 1-bits, and (c) all remaining columns to be distinct?

7 columns: 7!/2!5! = 21, too few distinct rows
8 columns: 8!/3!5! = 56, that’s enough.

The first 12 columns in each of the 30 rows should be one of these patterns:
11000 00000 00 
01100 00000 00
00110 00000 00
00011 00000 00
00001 10000 00

00000 11000 00
00000 01100 00
00000 00110 00
00000 00011 00
00000 00001 10

00000 00000 11
10000 00000 01

The last 8 columns should be chosen from the C(8,5) possible patterns.

The resulting matrix satisfies the requirements because:
(a) the last eight columns differentiate the 30 rows
(b) the first twelve columns are distinct by design
(c) the last eight columns are distinct because of the distinct patterns chosen from the C(8,5)
(d) all row sums are 7 before column removal, and 5 afterwards

Share this post


Link to post
Share on other sites
  • 0
On 12/11/2018 at 9:00 PM, CaptainEd said:

While this doesn’t answer the question with randomly placed 1s, I think it does give an upper bound to the number of columns that can be removed.

 

  Hide contents

 

What is the smallest number of remaining columns that would allow (a) the 30 rows to be distinct, (b) each row to have 5 1-bits, and (c) all remaining columns to be distinct?

7 columns: 7!/2!5! = 21, too few distinct rows
8 columns: 8!/3!5! = 56, that’s enough.

The first 12 columns in each of the 30 rows should be one of these patterns:
11000 00000 00 
01100 00000 00
00110 00000 00
00011 00000 00
00001 10000 00

00000 11000 00
00000 01100 00
00000 00110 00
00000 00011 00
00000 00001 10

00000 00000 11
10000 00000 01

The last 8 columns should be chosen from the C(8,5) possible patterns.

The resulting matrix satisfies the requirements because:
(a) the last eight columns differentiate the 30 rows
(b) the first twelve columns are distinct by design
(c) the last eight columns are distinct because of the distinct patterns chosen from the C(8,5)
(d) all row sums are 7 before column removal, and 5 afterwards

 

 

I agree

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.

×