# Thread: Boolean Matrix : Minimum number of columns

1. ## Boolean Matrix : Minimum number of columns

Hi all,

I was trying to solve a programming problem.. and it narrowed down to this question.

I am given N and M (both non-zero integers and M<N).. I need to construct a boolean matrix such that
1. Number of rows have to be equal to N
2. Every column must have M 1's exactly(rest 0)
3. No two rows should be the same.

I need to get the minimum number of columns for it, given N and M.

For eg: Assume, I am given (4,2)..
I can have a matrix like,
00
01
10
11

satisfying all the above conditions. So the answer here would be 2 columns.

2. Originally Posted by narjunkumar
Hi all,

I was trying to solve a programming problem.. and it narrowed down to this question.

I am given N and M (both non-zero integers and M<N).. I need to construct a boolean matrix such that
1. Number of rows have to be equal to N
2. Every column must have M 1's exactly(rest 0)
3. No two rows should be the same.

I need to get the minimum number of columns for it, given N and M.

For eg: Assume, I am given (4,2)..
I can have a matrix like,
00
01
10
11

satisfying all the above conditions. So the answer here would be 2 columns.
You need to construct the matrix AND get the minimum number of columns, or would it be enough just to get the minimum number of columns?

There is an easy lower bound which is ceil(log(N)/log(2)).

The lower bound can't also be the answer though because consider (N,M)=(5,4)

Each column has exactly one 0. Therefore if we try to construct with lower bound of 3 columns, we must have at least two rows filled with 1's, thus we need 4 columns.

Possibly a generalization can be found from here.

3. We need to get the minimum number of columns only. Since there could be multiple matrices with the same conditions as above. Let me put down the original question.. so that we can think of the approach.

The question is that I have N cards.. each card having M numbers.. (M<N).. you think of a number.. and I show you each card asking whether your number is there or not.. so that I can guess the number. Given, N and M, what is the minimum number of cards I need so that I can correctly guess the number in your mind.

4. Originally Posted by narjunkumar
We need to get the minimum number of columns only. Since there could be multiple matrices with the same conditions as above. Let me put down the original question.. so that we can think of the approach.

The question is that I have N cards.. each card having M numbers.. (M<N).. you think of a number.. and I show you each card asking whether your number is there or not.. so that I can guess the number. Given, N and M, what is the minimum number of cards I need so that I can correctly guess the number in your mind.
What kind of "numbers" are we talking about? Must they be distinct? The problem is terribly vague.

Maybe if you gave a concrete example with N=4 or N=5 we would be able to understand what you mean.

5. Let me give you an example with N=4, and M=2. Now, you can think of any number from 1 to 4. I am going to show you cards, with each card having 2 numbers in it, where each number is between 1 to 4. (Since M=2). For this problem, I know that 2 cards would be enough.
I show you Card1(1,2) and Card2(2,3).. and ask you whether the number you thought of is there or not. And based on your answer I can ascertain what number you thought of. (00 - 4; 01 = 3; 10 - 1; 11 - 2).

For a case, where N=3, and M=1.. the answer is that I would have to show you two cards at least.. each card having 1 number written in it.. to make the guess.

So for any N and M.. my idea was that.. assume you need minimum K cards.. so I would get a boolean number as answer. Every answer, I map to a particular number in N.. (lets say... 000111.. (length K) is mapped to 1). Thus you would have N possible answers, which means the boolean matrix will have N rows.. and it will have K columns.. with each column having exactly M 1's. (since every card has M numbers in it).

6. Originally Posted by narjunkumar
Let me give you an example with N=4, and M=2. Now, you can think of any number from 1 to 4. I am going to show you cards, with each card having 2 numbers in it, where each number is between 1 to 4. (Since M=2). For this problem, I know that 2 cards would be enough.
I show you Card1(1,2) and Card2(2,3).. and ask you whether the number you thought of is there or not. And based on your answer I can ascertain what number you thought of. (00 - 4; 01 = 3; 10 - 1; 11 - 2).

For a case, where N=3, and M=1.. the answer is that I would have to show you two cards at least.. each card having 1 number written in it.. to make the guess.

So for any N and M.. my idea was that.. assume you need minimum K cards.. so I would get a boolean number as answer. Every answer, I map to a particular number in N.. (lets say... 000111.. (length K) is mapped to 1). Thus you would have N possible answers, which means the boolean matrix will have N rows.. and it will have K columns.. with each column having exactly M 1's. (since every card has M numbers in it).
Thanks, it's a lot clearer now. I think you successfully came up with an equivalent problem to the original.

Let f(N,M) represent the minimum number of columns. We can simplify by noticing that f(N,M)=f(N,N-M) and thus we only need to consider M up to floor(N/2).

While drawing diagrams to get a handle on things, note that: switching any two rows of the matrix has no effect. Thus we can assume that all the 1's in the first column appear in the upper left, with the rest of the cells in that column being zero.

Also, switching columns has no effect, so we can draw our diagrams basically working from the upper left to the lower right.

This is what I draw for (N,M)=(7,3)

This suggests a possible algorithm, which may or may not be suitable for the constraints of the problem. Please give more information about the constraints on N, and number of test cases.

Also I'm curious to know where this problem came from. I am fairly active on SPOJ these days, plus some other sites sometimes.