50
$\begingroup$

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the real exam. After each mock exam the teacher tells the student how many right answers he got, and when the student feels ready, he can pass the real exam. Show that if the student is good at combinatorics he can guess all the answers after only $2^{k}$ mock exams.

For those who prefer a more formal presentation of the problem: if $E=\{1,-1\}^{N}$ we seek $n$ so that for some vectors $v_{1},v_{2}, \ldots, v_{n}\in E$ \begin{align*} \phi\colon E &\rightarrow \mathbb{N}^{n},\\ v &\mapsto (\langle v,v_{1}\rangle, \langle v,v_{2}\rangle, \ldots, \langle v,v_{n}\rangle) \end{align*} is injective. Show that it is possible to find such vectors when $N=k2^{k-1}$ and $n=2^{k}$.

It is possible to use duality to transform again the problem. We seek a $n\times N$ matrix $M$ such that $v\mapsto Mv$ is injective over $E$. If $X$ is the formal polynomial vector $X=(X_{1},X_{2}, \ldots,X_{n})$ then $v\mapsto Mv$ is injective iff $v\mapsto \langle X,Mv \rangle$ also is. But $\langle X,Mv \rangle = \langle M^{T}X, v \rangle$ and it is easily seen that $v\mapsto \langle M^{T}X,v \rangle$ is injective iff the $N$ column vectors $x_{i}$ of $M$ are such that $\sum_{i\in I} x_{i}\neq \sum_{j\in J} x_{j}$ for any two different subsets $I$, $J$ of $\{1,\dots,N\}$.

This problem comes from an olympiad-like contest. The original problem was formulated with 30 questions and the aim was to prove that the student could guess with 24 trials. One of my teachers came up with the result above (which would give 16 trials for 30 questions), but I can't remember his proof or find another one by myself.

I tagged this information theory because some probabilistic arguments show that it is impossible to do better than this asymptotically. More precisely, if we choose the coordinates of the $v$ defined above randomly, then \begin{equation*} N = H(\phi(v)) \leqslant \sum_{i} H(\langle v,v_{i} \rangle) = nH(B(N,1/2)) \sim (n/2)\log_{2}(N) \end{equation*} where $H$ designates entropy. With $N=k2^{k-1}$ we get $n\geqslant c\frac{k2^{k}}{k-1+\log_{2}(k)}\geqslant c2^{k}$ for all $c<1$ and $k$ large enough.

$\endgroup$
  • 2
    $\begingroup$ Can you explain the formal presentation? It seems to be that you think that the answer guesses must be fixed $v_i$, whereas I think that the original question allows the student to choose how to answer after each mock test. $\endgroup$ – Calvin Lin Dec 9 '14 at 5:14
  • 1
    $\begingroup$ Here is closely related (less-refined) question. $\endgroup$ – Andrew Kelley Dec 11 '14 at 1:40
  • 2
    $\begingroup$ There is an article in russian journal "Математическое просвещение" ( mccme.ru/free-books/matprosf.html ) with discussion about this problem . There you can find the proof. But it's in russian. $\endgroup$ – bigant146 Sep 27 '17 at 14:02
  • 3
    $\begingroup$ The full answer can be found in the link below, though I recommend thinking about this for a while before revealing the solution. users.renyi.hu/~p_erdos/1963-12.pdf $\endgroup$ – mm8511 Apr 28 '18 at 23:18
  • 1
    $\begingroup$ @Sergio Would you consider writing up the answer from the reference in a short self-contained way? $\endgroup$ – Phira Jun 24 '18 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.