Reducing search space by probability First question on this Stack, so I hope this is appropriate. This is not for homework, but a personal question related to a machine learning problem I am working on. However, I don't have enough knowledge of probability theory to answer it. So thanks in advance!
You are given a multiple choice test of p=100 questions and q=6 choices per question. You can take the test as often as you would like. The questions are always given in the same order. Each time you take the test you are given your score, such as 75% accurate, but do not know which 75% is correct. How many times do you have to take the test in order to be guaranteed a score > 90%?
Each time you take the test, there should be a reduction in entropy. For example, if you received 0%, you could eliminate all those choices from the next submission.
I'm not looking for the answer per se, but where would I start to find the solution.
 A: Here are some nonconstructive estimates on the number of tries needed to find the exact answer, not just to get $90\%$ or more correct. See this paper by Erdős and Rényi for similar analysis of a related problem. This is also connected to the game Mastermind. 
Consider guessing randomly $k$ times. What is the expected number of pairs of possibilities which are not distinguished from the answer? If we choose $k$ so that the expected number is less than $1$, this means there is some arrangement of guesses which distinguishes all pairs.
Let $B(r) = 5^r {100 \choose r}$ be the size of the sphere of radius $r$. There are $\frac{1}{2} 6^{100} B(r)$ pairs of distance $r$ from each other. 
The probability $p(r)$ that a uniformly random guess has the same results for possibilities of distance $r \gt 0$ is at most $\frac{2}{3}$, with equality when $r=1$. In general it is the coefficient of $x^r$ in $(\frac{1}{6} + \frac{2}{3} x + \frac{1}{6} x^2)^r$.
After $k$ random tries, the expected number of pairs which are not distinguished is $\sum_r \frac{1}{2}6^{100} B(r) p(r)^k.$ When $k=456$, the expected number of pairs is $0.82$ so there is some configuration of $456$ guesses so that the exact answer can be determined from the results.
We can do better. Most of the guesses were required because of the case $r=1$. The chance to get the same score for pairs which differ by $1$ is $\frac{2}{3}$, but for every other distance the chance to get the same score is at most $\frac{1}{2}$. While there are relatively few pairs of distance $1$, there are still a lot in absolute terms. These pairs are not necessarily essentially different. If AAAA... is not distinguished from BAAA..., this means that all of the guesses did not have an A or B in the first coordinate. Then we also can't distinguish ACCC... from BCCC..., or any of $6^{99}$ pairs. We can get better estimates by grouping these possibilities into one essential pair $(A???...?,B???...?)$. The number of essential pairs which disagree in $r$ locations is $\frac{1}{2}{100\choose r}(6\times 5)^r$. We need to choose $k$ large enough so that $\sum_r \frac{1}{2} {100 \choose r} 30^r p(r)^k   \lt 1$. This first happens at $k=130$, where the sum is $0.20$. So, some choice of $130$ tries will distinguish each pair of possibilities (and in fact, $80\%$ of random choices will work).
Figuring out which answer is consistent with a collection of guesses and scores might be hard. Some variants of this problem in Mastermind are known to be NP-complete.
