Conference rusure::math

In your example, let t be the number of possible outcomes of each 'game';
that is, t=3.

Suppose we want to guarantee at least n-1 correct guesses out of n.
Each 'column' can 'cover' at most n(t-1)+1 of the t^n possible outcomes
(that is, there are n(t-1) outcomes for which the column is correct
for exactly n-1 of them, and 1 outcome for which the column correctly
matches all n games).  Thus, you'll need at least ceiling[ t^n/(n(t-1)+1) ]
columns to guarantee that one of the columns will have at least n-1
correct guesses.

Your "3 out of 4" example had 9 columns.  The above shows that 9 columns
(9 = ceiling[3^4/(4*2+1)]) are necessary.  Your "2 out of 3" example had
5 columns, while the above suggests that only 4 columns (ceiling[3^3/(3*2+1)])
may be needed.

In general, you'll need at least:

	 n     n     n        (n-i)
	t  / Sigma (   ) (t-1)
	      i=k    i

columns to guarantee that some column will have at least k correct guesses.


For t=3, and n=14, this formula gives:

	 k  columns
         1  1.003
         2  1.028
         3  1.117
         4  1.353
         5  1.906
         6  3.223
         7  6.690
         8  17.356
         9  57.360
        10  247.552
        11  1447.191
        12  12170.404
        13  164929.965
        14  4782969 (= 3^14)

Note that those are lower bounds.  For k>0, at least 3 columns are required.

 Re .1

> Your "3 out of 4" example had 9 columns.  The above shows that 9 columns
> (9 = ceiling[3^4/(4*2+1)]) are necessary.  Your "2 out of 3" example had
> 5 columns, while the above suggests that only 4 columns (ceiling[3^3/(3*2+1)])
> may be needed.

 I knew how to compute the lower bound. This demonstrates how good the solution
of 9 columns for "3 of 4" is. In this case the optimal solution IS the lower
bound solution. In the case of 5 columns for "2 of 3", this is still the optimal
solution (I proved it) even if it IS NOT the lower bound. The reason is that
here some columns are covered more than once.

 I think the problem of verifying wether the optimal solution for "k of n"
has x columns is an NP-complete problem. However there are still some
interesting questions:

[1] What's the best algorithm, even if exponential.

[2] What is a good enoufg algorithm (that gives ALMOST the optimal solution -
    for example if you choose [in a loop] the next column which covers most
    uncovered columns, you get 6 columns for the solution of "2 of 3").

Nitsan

    This problem seems to have some similarity with error correcting
    codes.  Perhaps someone familiar with them knows an answer offhand.