4
$\begingroup$

Assume a standardized test has $15$ multiple choice questions, with $3$ options each. A school has some students and wishes for at least one of the students to get $10$ correct answers. Since no one in the school knows any math they are going to cheat and tell each student which answers he has to give without knowing what the actual correct answers are.

The problem is to find a small number of students $n$ such that it is possible to do this and guarantee at least one of the students gets at least $10$ correct.

For example one way to do it is with $n=3\cdot2^{15}-1$ students, where we do all possible exams with at most two different options, since one of the options appears at most \$5\$ times we can get at least one test with $10$ correct solutions.

Another possible $n$ is $a^5$ where we can get a set of $a$ tuples of length $3$ such that for every option of length $3$ there is a tuple in the set that matches in at least two positions (so basically a solution to the problem with length $3$ and at least $2$ correct). It seems that the vectors $(1,1,1),(2,2,2),(3,3,3)$ along with $(0,1,1),(1,2,2),(2,0,0)$ is guaranteed to get at least two correct for each sequence of three answers, so $6^5$ is also a valid $n$.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ What is the question here? Do you want someone to provide an answer to "The problem"? What is the purpose of the two paragraphs after you present the problem? $\endgroup$
    – bobble
    May 26, 2021 at 17:01
  • 1
    $\begingroup$ It's examples of two different values of $n$ for which we can show an arrangement exists. We want to get $n$ as low as possible. $\endgroup$
    – user10001
    May 26, 2021 at 17:04
  • $\begingroup$ Ah, I see. I was confused because normally (in my experience) optimization problems don't present possible nonoptimal solutions. $\endgroup$
    – bobble
    May 26, 2021 at 17:06
  • $\begingroup$ Oh, I'm not really expecting for anyone to find an optimal solution with proof, but that would be awesome. $\endgroup$
    – user10001
    May 26, 2021 at 17:07
  • $\begingroup$ I didn't quickly understand the last paragraph explaining 9^5. But my first thought was you could concentrate on 10 questions only and permutate answers to them. Then you would need 3^10 students, which is the same as 9^5 :-) $\endgroup$
    – puck
    May 26, 2021 at 17:32

2 Answers 2

Reset to default
4
$\begingroup$

The upper bound for $K_3(13,3)$ here yields

$1215$.

This guarantees $10$ correct out of the first $13$ questions, so we can surely do better by considering all $15$ questions.

A lower bound is the sphere covering bound $$\left\lceil \frac{3^{15}}{\sum_{i=0}^5 \binom{15}{i}2^i}\right\rceil = 118.$$

Improve this answer
$\endgroup$
9
  • $\begingroup$ Nice, thanks! we have it withing an order of magnitude! $\endgroup$
    – user10001
    May 27, 2021 at 2:51
  • $\begingroup$ wow reading this article it seems that bounding these covering codes is really no joke old.sztaki.hu/~keri/codes/index.htm $\endgroup$
    – user10001
    May 27, 2021 at 3:02
  • $\begingroup$ Can't you simply combine, for example, $K_3(11,3)$ and $K_3(4,2)$ to get an upper bound of 243x3? $\endgroup$
    – loopy walt
    May 27, 2021 at 3:03
  • $\begingroup$ I guess, wait, $K_3(4,2)$ is really $3$? $\endgroup$
    – user10001
    May 27, 2021 at 3:07
  • 1
    $\begingroup$ Onir the answer is in your link: sztaki.hu/~keri/codes/3_tables.pdf We are looking for $K_3(15,5)$ - we can have up to 5 errors in 15 questions. The tables only go up to 14. But we know that $K_3(15,5)<K_3(14,4)$. So it is at most 729. $\endgroup$
    – Dmitry Kamenetsky
    May 27, 2021 at 12:00
2
$\begingroup$

We can slightly improve on 65.

Get the first two guaranteed hits out of three questions using the 6 answer sets proposed in OP. Split the remaining 12 questions into two groups of 6. For each group provide all 27 answer sets of the form xyzzzz (x,y,z not necessarily distinct). This guarantees 4 correct per group.

Total combinations used: 6x27x27 = 4374.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.