Minimum number of elements in all sets

Question

I have an interesting problem:

Several (K) people go to the bookstore to buy books. Each person buys four (different) (more generally, m) books, and every two people share exactly (only) two (more generally, n, where 1 ≤ n ≤ m) of the same books. Now, what is the minimum number of kinds of books that can meet these conditions?

For 2, 3, 4, 5, 6, 7 people with two shared books, we can use a construction method to create the sets as follows:

• Case with 2 People
  • A = {1, 2, 3, 4}
  • B = {1, 2, 5, 6}
• Case with 3 People
  • A = {1, 2, 3, 4}
  • B = {1, 2, 5, 6}
  • C = {3, 4, 5, 6}
• Case with 4 People
  • A = {1, 2, 3, 4}
  • B = {1, 2, 5, 6}
  • C = {1, 3, 5, 7}
  • D = {1, 4, 6, 7}
• Case with 5 People
  • A = {1, 2, 3, 4}
  • B = {1, 2, 5, 6}
  • C = {1, 3, 5, 7}
  • D = {1, 4, 6, 7}
  • E = {2, 3, 6, 7}
• Case with 6 People
  • A = {1, 2, 3, 4}
  • B = {1, 2, 5, 6}
  • C = {1, 3, 5, 7}
  • D = {1, 4, 6, 7}
  • E = {2, 3, 6, 7}
  • F = {2, 4, 5, 7}
• Case with 7 People
  • A = {1, 2, 3, 4}
  • B = {1, 2, 5, 6}
  • C = {1, 3, 5, 7}
  • D = {1, 4, 6, 7}
  • E = {2, 3, 6, 7}
  • F = {2, 4, 5, 7}
  • G = {3, 4, 5, 6}

So, for 2 and 3 people, we need 6 kinds of books; for 4, 5, 6, and 7 people, we need 7 kinds of books. For K >= 8 people, it seems that constructing the sets becomes much more challenging.

One possible solution is:

Fix the shared two kinds of books the same between every two people, then the remaining two books of every person must be different. So the final result is:

1. 2 + K * 2 = 2K + 2

This is indeed the general right construction, and I suspect this is indeed the minimum construction (if K > 7). However, I cannot find any mathematical proof to confirm this or deny this.

So, does anyone have the right answer?

For a more general problem:

K people go to the bookstore to buy books. Each person buys M different books, and every two people share exactly N (where 1 ≤ N ≤ M) of the same books. Now, what is the minimum number of kinds of books that can meet these conditions?

A general construction is like the following:

2. N + (M - N) * K

1. So, is it possible to get an algorithm to construct and verify the problem, and then find the minimum construction?
2. Is there an general method/formula to get the miminum number?
3. Are formula (1) & (2) the miminum or not? What's the right answer?

Answer 1

So, is it possible to get an algorithm to construct and verify the problem, and then find the minimum construction?

To approach the problem systematically, I have had to ask the question in the opposite direction.

In fact, below I show an algorithm that systematically finds solutions in that space [though it's work in progress, see below: which is the main reason why I am posting here, not in Mathematics].

I am not and probably will not be able to go from there to closed counting formulas, if it is possible at all, but someone else might be able to build/improve on it.

The (opposite) question

For L,M,N,K (non-negative) integers, with 0<=N<=M<=L and 0<=K, where:

• L is the number of book titles available;
• M is the number of books every customer buys;
• N is the number of equal book titles every two customers buy;
• K is the number of customers served.

Given L,M,N, find max(K), i.e. the maximum number of customers that can be served.

Preliminary inspection

A preliminary inspection reveals that the only interesting case is 0<N<M<L.

• Case 0=N=M <= L => [].
  // no buying => no buys (i.e. no served)

• Case 0=N < M <= L => [[1..M],[M+1..2M],...,[(k-1)M+1..kM]]
  // no matches, buy some => argmax{k}(kM<=L) buys

• Case 0 < N=M <= L => [[1..M],[1..M],...]
  // all matches, buy some => infinitely many identical buys

• Case 0 < N < M=L => [[1..M]].
  // N<M matches, buy all => 1 buy

• Case 0 < N < M < L => ...non-trivial...
  // N<M matches, buy M<L => finitely many distinct buys

An algorithmic solution

Here is an algorithm that systematically explores the solution space for the case 0<N<M<L: presented in a logic programming style [i.e. the best I have been able to do for now].

Specifically, given 0<N<M<L, up to relabelling of book titles and customers [not sure if 100% correctly], this procedure generates in sequence all the possible customer buys filled to the maximum number of customers that can be served for the subsequent choices the customers make.

--dom:
0. Given 0 < N < M < L:
--base 1:
1. For person k = 1:
  101. Pick the buy B1 := [1,2,...,M].        (WLOG:fixed)
  102. Let S := [M+1,...,L] be the remaining available titles.
--loop 1: (until it fails)
2. For each person k > 1 up to failure:
  --pre 2:
  201. Let [C1,...,C{k-1}] := clone([B1,...,B{k-1}]) be
       the cloned previous buys, for later *marking*.
  202. Let Q := [] be the books *picked* by k.
  203. Let R := [] be the books *excluded* for k.
  --loop 2:
  21. For each Ci, with 1 <= i < k:
    --pre 3:
    211. Mark elements of R in Ci as excluded.
    21201. Let qi := the number of books marked picked in Ci.
    21202. Let si := the number of unmarked books in Ci.
    2121. If qi > N: FAIL!                                ^^REDO^^
    2122. If N-qi > si: FAIL!                             ^^REDO^^
    213. Add N-qi unmarked books of Ci to Q.  (WLOG:l2r)  [CHOICE]
    214. Add any remaining unmarked books of Ci to R.
    --loop 3:
    215. If N-qi > 0 (else do nothing):
      2151. For each Ci', with i <= i' < k:
        21511. Mark elements of Q in Ci' as picked.
        21512. Mark elements of R in Ci' as excluded.
        21513. If the number of books marked picked in Ci' is N:
          215131. Add any remaining unmarked books of Ci' to R.
          215132. (Mark the remaining unmarked books of Ci' as excluded.)
  --post 2:
  220. Let q := the number of books in Q.
  221. If q > M: FAIL!                                    ^^REDO^^
  222. If q < M:
    2220. Let s := the number of books in S.
    2221. If M-q > s: FAIL!                               ^^REDO^^
    2222. Move M-q books from S to Q.         (WLOG:l2r)  [CHOICE]
  223. If B{k-1} > Q: FAIL!                   (WLOG:asc)  ^^REDO^^
  224. Pick the buy Bk := Q.
--end 1: (loop 1 has failed)
3. YIELD [B1,...,B{k-1}].

Some results

An implementation in SWI-Prolog under GPLv3+ is available on my Gist.

Here are some results (slightly reformatted by hand for readability): e.g. for M=4, N=2, a minimum of L=20 available book titles is needed for K=9 people to get served:

[Ideally the procedure should generate solutions in reverse order of length, but that does not work yet: e.g. try pairwise_tt(5, 3, 2). So, these results are more illustrative than anything else...]

?- pairwise_t(20, _, 4, 2, [f]).
 (5,4,2) => [[1,2,3,4]]  (1)
 (6,4,2) => [[1,2,3,4],[1,2,5,6],[3,4,5,6]]  (3)
 (7,4,2) => [[1,2,3,4],[1,2,5,6],[1,3,5,7],
             [1,4,6,7],[2,3,6,7],[2,4,5,7],[3,4,5,6]]  (7)
 (8,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],
             [1,3,5,7],[1,3,6,8],[1,4,5,8],[1,4,6,7]]  (7)
 (9,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],
             [1,3,5,7],[1,3,6,8],[1,4,5,8],[1,4,6,7]]  (7)
(10,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],[1,2,9,10]]  (4)
(11,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],[1,2,9,10]]  (4)
(12,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],[1,2,9,10],[1,2,11,12]]  (5)
(13,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],[1,2,9,10],[1,2,11,12]]  (5)
(14,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],
             [1,2,9,10],[1,2,11,12],[1,2,13,14]]  (6)
(15,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],
             [1,2,9,10],[1,2,11,12],[1,2,13,14]]  (6)
(16,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],
             [1,2,9,10],[1,2,11,12],[1,2,13,14],[1,2,15,16]]  (7)
(17,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],
             [1,2,9,10],[1,2,11,12],[1,2,13,14],[1,2,15,16]]  (7)
(18,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],[1,2,9,10],
             [1,2,11,12],[1,2,13,14],[1,2,15,16],[1,2,17,18]]  (8)
(19,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],[1,2,9,10],
             [1,2,11,12],[1,2,13,14],[1,2,15,16],[1,2,17,18]]  (8)
(20,4,2) => [[1,2,3,4],[1,2,5,6],[1,2,7,8],[1,2,9,10],
  [1,2,11,12],[1,2,13,14],[1,2,15,16],[1,2,17,18],[1,2,19,20]]  (9)
true.