10
$\begingroup$

I was scrolling on TikTok the other day when I came across a video similar to this one. They're playing a game with bottles. Initially, $6$ bottles, each of a different color, are hidden behind a box and the goal is to guess the correct order of the bottles. The player takes turns guessing the order of the bottles and after each guess it is revealed how many bottles the player got right, i.e. exactly how many bottles are in their correct position.

A question naturally arises - Given $n$ bottles, each of a different color out of $n$ colors, what is the optimal strategy for this game?

I've tried to answer the question with no success. An alternative question is what is the optimal strategy if we allow for repetition (instead of guessing permutations of $\{1, 2, ..., n\}$, we guess $n$-tuples from $\{1, 2, ..., k\}^n$) - Given $n$ bottles, each being one of $k$ colors, what is the optimal strategy for this game?

Note: when I say optimal strategy, I mean what is the smallest $m$ such that there exists a strategy that guarantees a win in $m$ guesses or less.

$\endgroup$
5
  • $\begingroup$ I have edited the title to something more descriptive of the game and its mathematical content. Some additional tags may also be helpful but these seem fine for now $\endgroup$
    – whpowell96
    Commented Aug 4 at 23:44
  • 5
    $\begingroup$ You may want to describe "optimal" in more detail. Are you trying to minimise the expected number of guesses or minimise the worst-case number of guesses? (For the similar Mastermind game they give different results.) $\endgroup$
    – Henry
    Commented Aug 4 at 23:47
  • $\begingroup$ The "information-theoretic lower bound" is that you need at least $\frac{\log n!}{\log (n+1)} \approx n - \frac{n}{\log n}$ guesses, which for $n = 6$ is $4$. So it would be natural to try to shoot for a strategy that wins using $n$ or so guesses. $\endgroup$
    – Qiaochu Yuan
    Commented Aug 4 at 23:55
  • $\begingroup$ This question seems to be the similar to this one or this one . Maybe some of it is also useful here. $\endgroup$
    – Immanuel
    Commented Aug 5 at 0:34
  • 1
    $\begingroup$ Actually, $\ln n!/\ln n$ is an information theoretic lower bound as there are only $n$ different outcomes of each round: the number of matching bottles cannot be $n-1$. $\endgroup$
    – Einar Rødland
    Commented Aug 5 at 4:17

1 Answer 1

Reset to default
3
$\begingroup$

Here is an improved lower bound for the permutation case.

Assuming there are $n$ bottles of $n$ different colours, and in each round the guess has to be a permutation of the colours, there is a lower bound on the number of rounds as has been pointed out in the comments. Since in each round there are at most $n$ different outcomes (since $n-1$ correct colours is not possible), the minimum number of rounds is $\ln n!/\ln n$. However, this is a weak bound since, at least in the first rounds, the number of correct colours is likely to be small.

Let $A_k$ be the number of different $n$-permutations with exactly $k$ fixed points. This can be expressed as $A_k=\binom{n}{k}\,!(n-k)$ where $!m$ is the number of fixed point free $m$-permutations, also known as derangements.

At the start, there are $M_0=n!$ possible permutations. In round $r$, we make a guess, and worst case is a result $k$ leaving at least $M_r$ possible permutations where $M_r$ is the smallest number so that $\sum_{k=0}^n\min(A_k,M_r)\ge M_{r-1}$.

This gives stronger lower bound, $R_n$, on the number of guesses required to get the right answer: ie after $R_n-1$ guesses, you know the right answer, and in round $R_n$ you provide it.

I found the lower bound on $R_n$ by this method to be $R_n\ge n$ for $n=1,\ldots,164$, and after that it was $R_n\ge n-1$ for as far as I tested.

The actual values of $R_n$ for low $n$ are $R_1=1$, $R_2=2$, $R_3=4(?)$, beyond which I would not solve by hand.

My guess is that $R_n\approx n$, perhaps even $R_n\le n+C$ for some constant $C$.

$\endgroup$
2
  • $\begingroup$ How did you get $\sum_{k=0}^n\min(A_k,M_r)\ge M_{r-1}$? $\endgroup$
    – Natrium
    Commented Aug 12 at 14:06
  • $\begingroup$ @Natrium: After $r-1$ rounds there are $M_{r-1}$ possible permutations. You then make a guess that splits these into groups depending on the number of fixed points $k$ (ie matching bottles) in you guess. If the biggest of these groups has size $M_r$, that is the worst case: all other groups have at most $M_r$ permutations. However, as there are only $A_k$ permutations with $k$ fixed points, so the maximal size of group $k$ is $\min(A_k,M_r)$. Combined, these groups must contain all $M_{r-1}$ permutations, hence the inequality. $\endgroup$
    – Einar Rødland
    Commented Aug 12 at 16:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .