How many answer sheets must you submit to a 10-question true/false quiz to be sure one of them scores at...

combinatorics/true.false.quiz New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

How many answer sheets must you submit to a 10-question true/false quiz
to be sure one of them scores at least 8 out of 10?

Suppose you have true/false quiz with 10 questions and you would be
happy to receive a score of at least 8 out of 10 correct.  What's the
fewest number of separate answer sheets that you would need to submit
to be sure of achieving this score on at least one of them?

-- mborden <mborden@baynetworks.com>

Show solution

64 is sufficient to guarantee at least one with 8 or more answers
right; i.e. I've found a set of 64 answer sheets that cover all 1024
possible patterns of right answers.  I haven't shown that to be
minimal, however...

It wasn't.  The following set of 32 answer sheets will do the trick.
(Each is a ten-bit number in hexadecimal.  Put "TRUE" where the number
has a one-bit and "FALSE" where it has a zero-bit.)  I think this is
the smallest possible set.

0c6 3b7 341 010 02f 3a8 17a 2dd 346 28a 0b1 10d 1db 27c 1e4 263
316 2a4 17d 0fe 213 1a2 3d8 069 085 331 36f 248 194 017 2fa 18b

-- Paul Filseth <pgf@lsil.com>

[ Editor: no proof that 32 is the minimum was found in the collected
postings. ]