Yesterday was a guest, where Dobble was shown to my kid . It has a set of cards with carved pictograms, the main thing is that on any two cards there is always one and only one common pictogram.

From a mathematical point of view, this means - there are many of N elements; you need to build as many subsets as possible of M < N elements with the property that every two subsets have one and only one common element.

How to solve this problem? What algorithm will generate these subsets? Let at least for some non-trivial options - for 3 and 2 , as you understand, the solution is trivial :), like a solution with a single common element for all.

I would be grateful for a ready-made solution, and for any ideas.

  • for N and 2 , as you understand, the decision is trivial. For N> 3, I don’t see a solution that uses more than 3 elements from N. So here it’s far to triviality ... - Akina
  • @Akina Yes, I lost my temper ... I will correct it :) - Harry

4 answers 4

The answer is the first - not true, because he underestimated the charm of the problem

I suppose that it is possible not to go into the jungle of intersections of sets, but simply selecting two subsets, which is no longer so difficult, to “mix in” with them the same value, which is not included in them. ( one of any ideas )

The answer of the second - unfortunately not mine, was not held back, I spied on the Internet.

 \#define PRINT(x) printf("%2d ", (x)+1) main() { int i, j, k, r = 0, n = 7; // first card printf ("Card %2d: ", ++r); for (i = 0; i <= n; i++) { PRINT (i); } printf ("\n"); // n following cards for (j = 0; j < n; j++) { printf ("Card %2d: ", ++r); PRINT (0); for (k = 0; k < n; k++) { PRINT (n+1 + n*j + k); } printf ("\n"); } // n*n following cards for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { printf ("Card %2d: ", ++r); PRINT (i+1); for (k = 0; k < n; k++) { PRINT (n+1 + n*k + (i*k+j)%n); // Good for n = prime number } printf ("\n"); } } }

And here you can see the solution in action.

  • Those. Do you propose to create non-intersecting subsets and add new elements to them? Could you clarify with a specific example? Your idea is not very clear. - Harry
  • you have 100 different people, you choose (randomly, from the end, from the beginning) of them two groups of 10 (different) people. In the initial hundred, 80 are left. Of the 80, randomize one more and include it in both groups. Now in each group of 11 people and 1 in each group is in both groups. - TimurVI
  • Where did 2 subsets come from when there are a lot of them? - Yuri Negometyanov
  • subsets are obtained :) - Harry
  • @Harry updated, thanks for the question - TimurVI

there are many of N elements; you need to build as many subsets as possible of M <N elements with the property that every two subsets have one and only one common element.

Let's think. What do we have? We have N items. Each group must have M elements.

Create the first group. Suppose it includes items with numbers from 1 to M.

Create a second group. It should have only 1 common element from the first one. Let it be element 1. Then the second group contains element 1 and elements from M + 1 to 2 * M-1.

Create a third group. It should have with each of the previously created only 1 common element. Well option when it is element 1 again, we will mark as trivial (but not as impossible !!!). Then these will be elements 2 (intersect with group 1) and M + 1 (intersect with group 2), and the rest are elements with numbers from 2 * M to 3 * M-3.

I hope the technique is clear? Well, then - on your own ... until you jump out for N, or until the options run out.

Ps. I smell the smell of perfect numbers ...

  • The idea is clear, but for some reason it seems that it will be very far from optimal ... - Harry
  • And it seems to me that the technique is optimal. The fact is that it has no branches ... the generation of the next group is uniquely determined by the already generated set. Ps. In the text, I refuse the option of duplicating a common element - it is easy to check that even if you roll up to this branch, it will not change the maximum total number of groups generated from a given number of elements, regardless of whether N equals the maximum number of elements that can be used, or less. - Akina
  1. Reserve the first element from N.
  2. We divide the remaining elements into groups of M-1 elements.
  3. Add a reserved item to each group.
  • This solution is N / M, roughly speaking. Not enough, judging by the game :), and trivial. - Harry
  • so requires condition - Yuri Negometyanov
  • it reminds me of something - TimurVI
  • @YuriNegometyanov Is this exactly "as many subsets as possible"? - Harry
  • one
    @YuriNegometyanov could at least mention my answer in my answer (it’s kind of accepted here), but it’s somehow strange and funny - TimurVI

Accidentally I saw in my head at bedtime such an option for the case N=M(M-1)/2 . Moreover, the number of subsets of M , and their size M-1 .

We number the elements of the original set by numbers from 1 to N , and the generated sets are denoted by A1 , A2 , ..., AM .

Take the element 1 and put it in the sets A1 and A2 . Take the element 2 and put it in the sets A1 and A3 , then the element 3 in A1 and A4 and so on to A1 and AM . Then, as it were, we return to the beginning and put the next element (with the number M ) in the sets A2 and A3 , then (the element M+1 ) in A2 and A4 , etc. Example for N=6 and M=4 :

 123 145 426 563

An example for N=10 and M=5 (instead of 10 wrote 0 ):

 1234 1567 5289 6830 7904

Proof to invent, unfortunately, there is no time.