10
$\begingroup$

Using a pool of problems, 16 tests will be formed, following certain conditions:

  • Every test should have the same number of problems.
  • Any problem should be included in at most 8 tests.
  • Every group of 4 tests must share at least 1 problem.
  • Each test may not use a single problem more than once.
  • Some tests may have exactly the same problems.

What is the minimum number of problems in this pool?

As an example:

If this problem asked for 8 tests, where any problem could be included in at most 4 tests and at least 1 problem must be common to every 2 tests, then the answer would be 6 problems:

(1-2-6), (1-3-5), (1-3-5), (1-4-6), (2-3-6), (2-4-5), (2-4-5), (3-4-6)

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Welcome to Puzzling! Is this a question from some other source? $\endgroup$ – Deusovi♦ Nov 19 '20 at 15:42
  • 2
    $\begingroup$ Unfortunately, this is a question from puzzleup.com/2020/?home, a competition which explicitly the use of outside help :( Shame on you, helloworldx! $\endgroup$ – Boluc Papuccuoglu Dec 17 '20 at 8:40
6
$\begingroup$

UPDATE: Found optimal solution

Simple upper bound:

70: Group the tests in 8 pairs and create a problem for each group of 4 pairs. 8-choose-4 is 70.

Better upper bound:

50: Rows are tests, columns are problems, "X" means problem is part of test, "." means not. 

 XXXXXXXX........X.X.....XX..XXXXX.X.....XX..XXXXX.
 XXXXXXXX.........X.X......XXXXXX.X.X......XXXXXXX.
 ........XXXXXXXXX.X.....XX..XXXX.X.X......XXXXXXX.
 ........XXXXXXXX.X.X......XXXXXXX.X.....XX..XXXXX.
 XXXX....XXXX....XXXXX.X.....XX..XXXXX.X.....XX...X
 XXXX....XXXX....XXXX.X.X......XXXXXX.X.X......XX.X
 ....XXXX....XXXXXXXXX.X.....XX..XXXX.X.X......XX.X
 ....XXXX....XXXXXXXX.X.X......XXXXXXX.X.....XX...X
 XX..XX..XX..XX..XX..XXXXX.X.....XX..XXXXX.X.....X.
 XX..XX..XX..XX....XXXXXX.X.X......XXXXXX.X.X....X.
 ..XX..XX..XX..XXXX..XXXXX.X.......XXXXXX.X.X....X.
 ..XX..XX..XX..XX..XXXXXX.X.X....XX..XXXXX.X.....X.
 X.X.X.X.X.X.X.X.....XX..XXXXX.X.....XX..XXXXX.X..X
 X.X.X.X.X.X.X.X.......XXXXXX.X.X......XXXXXX.X.X.X
 .X.X.X.X.X.X.X.X....XX..XXXXX.X.......XXXXXX.X.X.X
 .X.X.X.X.X.X.X.X......XXXXXX.X.X....XX..XXXXX.X..X

Optimal solution:

30: Found using a simple stochastic greedy algorithm on a partial, hand crafted preset. Right panel is the same as left but with rows and columns rearranged as to make structural features easier to pick out. 

 XXXXXXXX.........XX..XXX...XX.    XXXX....XXXX....XXXX....X.X.X.
 X.X..X.X.X.XX.X..XX..X..XXX..X    XXXX........XXXX....XXXXX.X.X.
 .X.XX.X.X.X..X.X.XX..X..XXX..X    ....XXXXXXXX........XXXXX.X.X.
 ........XXXXXXXX.XX..XXX...XX.    ....XXXX....XXXXXXXX....X.X.X.
 XXXX....XXXX.....X.XX.XXXX....    XX..XX..XX..XX..XX..XX..X..X.X
 XX....XX..XXXX..X.X.X..X.XX.X.    XX..XX....XX..XX..XX..XXX..X.X
 ..XXXX..XX....XXX.X.X..X.XX.X.    ..XX..XXXX..XX....XX..XXX..X.X
 ....XXXX....XXXX.X.XX.XXXX....    ..XX..XX..XX..XXXX..XX..X..X.X
 XX..XX..XX..XX..X..X.X.XX.XX..    X.X.X.X.X.X.X.X.X.X.X.X..XX..X
 X..X.XX.X..X.XX.X..X.XX..X..XX    X.X.X.X..X.X.X.X.X.X.X.X.XX..X
 .XX.X..X.XX.X..XX..X.XX..X..XX    .X.X.X.XX.X.X.X..X.X.X.X.XX..X
 ..XX..XX..XX..XXX..X.X.XX.XX..    .X.X.X.X.X.X.X.XX.X.X.X..XX..X
 X.X.X.X.X.X.X.X..X.XX.....XXXX    X..X.XX.X..X.XX.X..X.XX..X.XX.
 X..XX..X.XX..XX.X.X.X.X.X..X.X    X..X.XX..XX.X..X.XX.X..X.X.XX.
 .XX..XX.X..XX..XX.X.X.X.X..X.X    .XX.X..XX..X.XX..XX.X..X.X.XX.
 .X.X.X.X.X.X.X.X.X.XX.....XXXX    .XX.X..X.XX.X..XX..X.XX..X.XX.

Structure and function:

Going by the right panel we can split the tests into four groups of four and the problems into the first 24 and the last 6. The last 6 in handle all 4-tuples that are covered by at most two test groups, i.e. those that distrbute 4-0-0-0, 3-1-0-0 or 2-2-0-0 over the four test groups. Note the pattern of all six 2-subsets of 4 which we'll also see prominently on the 24 first problems. The 24 deal with the remaining cases 2-1-1-0 and 1-1-1-1. They naturally split into 3 groups of 8 which differ by the way each group of four is split into two. The 3 groups are actually identical up to shuffling rows. There is also symmetry between the two upper and the two lower groups of 4 tests. Either pair is identical up to rearrangment of tests. Let us look a bit into how it covers both 2-1-1-0 and 1-1-1-1 creating some synergy. The obvious strategyof handling 1-1-1-1 is to cover each of the four test groups with a quarter of the allowed number of problem copies. In our case that would be 2, so 2 problems are needed to cover a test group and since there are 4 groups a total of $2^4 = 16$ problems is required. This is what I have done manually in the non-optimal example above. The 2-1-1-0 on the other hand has the additional requirement that one of test group features 2 times such that a simply covering the group is no longer enough. Instead all 6 2-subsets must be made available. Doing the naive thing --- using the 16-cover 3 times (one for each 2/4 covering) would require 48 problems, clearly too many, so how does this solution get away with half that? It uses a reduced version of 16-cover which doesn't reliably work since it uses only $2^3$ problems which is enough to cover 3 groups but not necessarily 4. The trick here is that it will always happen to work in one of the three groups of 8 because they cover all possible splits of a test group into two, in particular the one split that doesn't split the two tests from the same group.

Optimal because:

We need only slightly improve @AxiomaticSystems's lower bound (26). Achieving 26 would amount to perfectly splitting the 16 tests into groups of 8 such that each group of 4 is contained in exactly one group of 8. Consider three tests a,b,c. They must share a problem with each of the remaining 13 tests. Because problems can only be used in 8 tests (5 other than a,b,c) a,b,c must have at least 3 problems in common. These three would optimally cover 15 tests other than a,b,c but since there are only 13 we waste two of them at a ratio of 15:13.

Improve this answer
$\endgroup$
  • $\begingroup$ How did you arrive to this by a software? $\endgroup$ – Prince Deepthinker Nov 20 '20 at 11:45
  • $\begingroup$ @PrinceDeepthinker Mostly by hand, but I used the computer (Python itertools and numpy) to check and make sure all groups of four a covered and also to set up regular subpatterns. For example, the first 16 columns are 4 groups of two pairs each. This gives 2^4 combinations. Those I let the computer generate. $\endgroup$ – Paul Panzer Nov 20 '20 at 11:51
  • 1
    $\begingroup$ @PrinceDeepthinker I'm certainly spending way too much time on this site. That said, this one wasn't that bad; I just checked out a few ideas, and I don't expect this to be optimal. $\endgroup$ – Paul Panzer Nov 20 '20 at 12:00
  • 1
    $\begingroup$ +1 for the effort $\endgroup$ – Prince Deepthinker Nov 20 '20 at 12:02
  • 2
    $\begingroup$ @tehtmi It matters not since I have now found an optimal solution. And I checked the row and column sums. Still need to understand how it works, though. $\endgroup$ – Paul Panzer Nov 21 '20 at 12:22
0
$\begingroup$

It's easy to show that the minimal number of problems is at least

26

because

if each number can appear at most 8 times, then it can be the common question for at most $\binom{8}{4}=70$ sets of 4 tests. However, there are $\binom{16}{4}=1820=70 \times 26$ of these in total.

Improve this answer
$\endgroup$
  • 5
    $\begingroup$ This doesn't answer the question though. $\endgroup$ – Bass Nov 19 '20 at 17:04

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