2
$\begingroup$

I'm making some exercises on combinatorics algorithm and trying to figure out how to solve the question below:

Given a group of 25 bits, set (choose) 15 (non-permutable and order NON matters):

n!/(k!(n-k)!) = 3.268.760

Now for every of these possibilities construct a matrix where I cross every unique 25bit member against all other 25bit member where in the relation in between it there must be at least 11 common setted bits (only ones, not zeroes).

Let me try to illustrate representing it as binary data, so the first member would be:

0000000000111111111111111 (10 zeros and 15 ones) or (15 bits set on 25 bits)
0000000001011111111111111 second member
0000000001101111111111111 third member
0000000001110111111111111 and so on....

...
1111111111111110000000000 up to here. The 3.268.760 member.

Now crossing these values over a matrix for the 1 x 1 I must have 15 bits common. Since the result is >= 11 it is a "useful" result.

For the 1 x 2 we have 14 bits common so also a valid result.

Doing that for all members, finally, crossing 1 x 3.268.760 should result in 5 bits common so since it's < 11 its not "useful".

What I need is to find out (by math or algorithm) wich is the minimum number of members needed to cover all possibilities having 11 bits common.

In other words a group of N members that if tested against all others may have at least 11 bits common over the whole 3.268.760 x 3.268.760 universe.

Using a brute force algorithm I found out that with 81 25bit member is possible achive this. But i'm guessing that this number should be smaller (something near 12).

I was trying to use a brute force algorithm to make all possible variations of 12 members over the 3.268.760 but the number of possibilities it's so huge that it would take more than a hundred years to compute (3,156x10e69 combinations).

I've googled about combinatorics but there are so many fields that i don't know in wich these problem should fit.

So any directions on wich field of combinatorics, or any algorithm for these issue is greatly appreciate.

PS: Just for reference. The "likeness" of two members is calculated using:

(Not(a xor b)) and a

After that there's a small recursive loop to count the bits given the number of common bits.

|cite|improve this question
$\endgroup$
  • $\begingroup$ It's a little difficult to understand - for me, at least. Perhaps (besides polishing your english) you should state the problem with smaller numbers. $\endgroup$ – leonbloy Apr 9 '12 at 20:57
  • $\begingroup$ @leonbloy (sorry for the poor English. It's not my native language) Anyway, if you have any suggestions you may eventually try the same problem with small numbers (such as 7 choose 4 matching 3). Despite of all text the focus is on this paragraph: "... a group of N members that if tested against all others may have at least 11 bits common over the whole 3.268.760 x 3.268.760 universe." $\endgroup$ – Paulo Bueno Apr 9 '12 at 21:08
  • 1
    $\begingroup$ Say $A$ is the set of your 3.268.760 elements (25 bits with 15 ones). You want to find some (as small as possible) subset $B \subset A$ such that, for all $a \in A$ there exists some $b \in B$ that it has at least 11 ones in common with $a$. Is this correct? $\endgroup$ – leonbloy Apr 10 '12 at 0:02
  • $\begingroup$ That's correct @leonbloy. This image contains the visual information of the relation strength in between the first 4096 elements. (red meaning high 15bit relation to green meanning 11bit connections). Thanks. $\endgroup$ – Paulo Bueno Apr 10 '12 at 2:23
  • $\begingroup$ This kind of problem is not easy, but a lot of work has been done, in relation to binary codes with error correction. In that context: you want to cover your full code space (vertices of an hypercube of dimension 25 restricted to a fixed 'weight' = 15) with a covering distance of 4 (number of bits that differ). You should look for some specialization of the en.wikipedia.org/wiki/Hamming_bound for fixed weight words. $\endgroup$ – leonbloy Apr 10 '12 at 2:32
2
$\begingroup$

Here's a way to get an estimate of the answer. Given a string, say, $$x=0000000000111111111111111$$ how many of the 3,268,760 strings have 11 or more ones in common with $x$? There are the ones with exactly 11 in common; there are 15-choose-11 times 10-choose-4 of those. Then there are the ones with exactly 12 in common; 15-choose-12 times 10-choose-3 of them. Then exactly 13, 14, 15 in common; similar formulas. Add up the 5 numbers I've described and you have the number with 11 or more in common with $x$. Now divide 3,268,760 by that number, and you get a lower bound on the number you are looking for.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Indeed @Gerry Myerson the lower bound estimate is easy to find and is 3268760/286650 aprox. is near 12. Indeed that is not an answer since: 1st. can't have a proof of that, 2nd it's mostly not true since each element may not fit perfectly without any overlaping. $\endgroup$ – Paulo Bueno Apr 11 '12 at 14:13
  • $\begingroup$ I think the keyphrase for which you want to search is "combinatorial designs". You have a 25-set, and you are looking for the smallest collection $X$ of 15-sets such that every 15-set intersects an element of $X$ in at least an 11-set. Such things have undoubtedly been tabulated somewhere, though perhaps not all the way out to 25-15-11. $\endgroup$ – Gerry Myerson Apr 12 '12 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.