I've come across the following little quiz game problem, which I've failed to solve.
Say we have $15$ people, each of them of different age, and you want to guess their actual birthday – not just their age.
You are allowed to guess as many times as you want, but the guessing goes as follows:
- Choose $5$ random people from the group.
- Each of them gives you four distinct possible dates, which they have chosen before the quiz started (so they will not change their options later in the game). One of these is correct.
- When you have guessed on the date for all five, they will tell you how many correct guesses, you had. They will not tell you which guesses were correct.
Now the questions are:
- What is the probability to guess one specific person's birthday in the first try?
- How many times would you expect, you have to guess to get one person's birthday right?
- How many times would you expect, you have to guess to get all $15$ people's birthday right?
- What is the probability to get one person's birthday right in less than $200$ guesses?
- What is the probability to get all the people's birthday right in less than $3000$ guesses?
The first question was rather easy to answer. When you pick randomly, you have to pick the person, whose birthday you would like to know, the probability of this is $\dfrac{1}{3}$, since we pick $\dfrac{1}{3}$ of the people in the group. To know one person's birthday for sure in the first try, you will have to answer his question correct. But as you will not know which question, you answered correct, when you ask, unless you answered all of them correct, you will have to answer correct, which has the probability $\left(\dfrac{1}{4}\right)^5 = \dfrac{1}{1024}$.
So the answer to the first question is $\dfrac{1}{3072}$.
To solve the next questions, I've tried to assume that we only have $5$ people, and that they are always chosen. This gives me a strategy to find one specific person's birthday, since I can just alter my answers to his question, and after maximum four guesses, I've guessed his birthday.
Unfortunately, I cannot be sure that he will come up every time, I ask. Actually, I cannot be sure that he will ever come up, but I "only" have to find the expected amount of guesses.
And this is where I got stuck. Any help in tackle this question will be so much appreciated! Hints or even solutions, anything.
Thank you very much in advance!
Best Answer
A definite answer is very hard to give because there is a lot of convoluted strategy involved. A rough information theoretical approximation is as follows. We have to guess 30 bits of information and the first round gives us about $1.94$ bits, so we might know all after about 16 rounds. However, on the one hand we can increase the expected information gain (though hardly ever to the maximum of $2.58$ bits), on the other hand the information to be gained about five selected people may be less due to knowledge gained in previous rounds.
You can work with a lower bound by assuming the trivial strategy that makes random guesses in each round and only making use of rounds where you guess all correct. As a slight improvement, you may choose to always repeat the known correct giuess for people already solved. However we ignore the fact that all-wrong-guesses can be used to strike away one bad for each of the five people and other advantages. Under this strategy, let $X_n$ be the number of solved people after $b$ rounds. So $X_0=0$ and otherwise $$\begin{align}P(X_{n+1}=k)=&\frac1{1024}\cdot \frac{20-k\choose 5}{15\choose 5}P(X_n=k-5) \\&+ \frac1{256}\cdot \frac{{19-k\choose 4}{k-4\choose 1}}{15\choose 5}P(X_n=k-4)\\&+ \frac1{64}\cdot \frac{{18-k\choose 3}{k-3\choose 2}}{15\choose 5}P(X_n=k-3)\\ &+\frac1{16}\cdot \frac{{17-k\choose 2}{k-2\choose 3}}{15\choose 5}P(X_n=k-2)\\ &+\frac1{4}\cdot \frac{{16-k\choose 1}{k-1\choose 4}}{15\choose 5}P(X_n=k-1)\\ &+\frac{{k\choose 5}}{15\choose 5}P(X_n=k)\\\end{align}$$ (especially, $P(X_n=1)=\ldots=P(X_n=4)=0$) You can use this recursion to estmiate the expected number of rounds until you know all birthdays: $$E(all)=\sum_{n=0}^\infty P(X_n<15) $$