Generalization of a mind-boggling box-opening puzzle

Question

Motivation. Suppose we are given $6$ boxes, arranged in the following manner:

$$\left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array}\right]$$

Two of these boxes contain a present, and the remaining $4$ are empty. From the outside, no-one can tell which boxes contain a present. There are ${6 \choose 2} =15$ ways to put the presents in the two boxes. The goal is to find one box containing a present as quickly as possible.

Anna opens the boxes in row-wise, that is, in the order: $1,2,3,4,5,6$. Bert opens the boxes column-wise: $1,4,2,5,3,6$. In the $15$ ways to distribute the two presents into the $6$ boxes, Anna finds the first present quicker than Bert $5$ times and Bert beats Anna only in $4$ scenarios (and there are $6$ ties). I think it is crazy that one arbitrary method (Anna's) should be better than another (Bert's) to uncover the first presents even if the two gift locations are picked at random!

Formalization and generalization. For $n\in\mathbb{N}$ we write $[n] := \{1,\ldots,n\}$. If $X$ is a set, then let $[X]^2 = \big\{\{x,y\}:x\neq y \in X\big\}$. By slight abuse of notation, we write $[n]^2$ instead of $[[n]]^2$. The collection of bijections $f:[n]\to[n]$ is denoted by $S_n$.

For the remainder of this post, let $n\geq 3$ be an arbitrary, but fixed integer. Let $a, b\in S_n$. We can think of $a$ as being the method that Anna uses to open the boxes $\{1,\ldots,n\}$, and $b$ is Bert's way of trying to find one present. The locations of the $2$ presents is encoded by an element $P\in [n]^2$. The number of $P\in [n]^2$ such that Anna finds one present quicker than Bert, and therefore wins, is

$$W(a,b) = \Big|\{P\in [n]^2: \min \big(a^{-1}(P)\big) < \min \big(b^{-1}(P)\big)\}\Big|.$$

We say $a\in S_n$ is better than $b\in S_n$ if $W(a,b) > W(b,a)$.

To me, it is not clear, whether "betterness" as defined above is a transitive relation, but this is not my main focus for this post. (EDIT. user14111 showed in the comment section that this relation is not transitive; the situation reminds me a little of the intransitive dice.)

Questions.

1. Are there infinitely many integers $n\geq 3$ such that for every $f\in S_n$ there is $f' \in S_n$ such that $f'$ is better than $f$? And related to this:

2. Are there infinitely many integers $n\geq 3$ such that there is $f_0\in S_n$ such that no element of $S_n$ is better than $f_0$?

Answer 1

Anna opens the boxes in row-wise, that is, in the order: $1,2,3,4,5,6$. Bert opens the boxes column-wise: $1,4,2,5,3,6$. In the $15$ ways to distribute the two presents into the $6$ boxes, Anna finds the first present quicker than Bert $5$ times and Bert beats Anna only in $4$ scenarios (and there are $6$ ties). I think it is crazy that one arbitrary method (Anna's) should be better than another (Bert's) to uncover the first presents even if the two gift locations are picked at random!

It's not really all that mind-boggling, at least not once you realize what's going on.

To see it more clearly, consider a slight variation of the setup where Anna still opens the boxes in the order $1,2,3,4,5,6$, but Bert instead chooses the order $2,3,4,5,6,1$. In other words, Bert decides to use the same strategy as Anna, but starting with box $2$ and leaving box $1$ for last.

This is basically the best strategy Bert could choose against Anna: the only way Anna wins or ties the race is if box $1$ contains one of the presents, which happens in 5 cases out of 15. In one of these 5 cases box $2$ contains the other present and the result is a tie; in the remaining 4 cases Anna is lucky and wins on the first try.

However, if box $1$ does not have a present, Anna's strategy is guaranteed to lose to Bert's, since on every subsequent step Anna opens a box that was just checked by Bert on the previous step. So Anna wins in 4 of the 15 possible cases, ties in 1 case and loses to Bert in all the remaining 10 cases.

Of course, knowing Bert's new strategy, Anna could turn the tables by instead choosing to open the boxes in the order $3,4,5,6,1,2$, beating Bert to the first present in 10 cases out of 15. But then Bert could change his order to $4,5,6,1,2,3$, again beating Anna's new order 10 times out of 15. But then Anna could beat Bert by choosing the order $5,6,1,2,3,4$, and then Bert could beat Anna with the order $6,1,2,3,4,5$, which Anna could beat with her original order $1,2,3,4,5,6$… which of course loses to Bert's strategy of opening the boxes in the order $2,3,4,5,6,1$, and so on.

So, yes, this game is indeed very strongly intransitive, and that's exactly why one "arbitrary" strategy can beat another equally arbitrary strategy.

On its own, no strategy (that doesn't check the same box more than once) is any "better" at finding the presents than any other strategy, since of course the numbering of the boxes (or their arrangement on a grid) is completely arbitrary and independent of which boxes contain the presents. But for every strategy there's an optimal counter-strategy that beats it to the first present in 10 cases out of 15, easily obtained by modifying the original strategy to skip the first box and open it last instead.

---

Questions.

1. Are there infinitely many integers $n\geq 3$ such that for every $f\in S_n$ there is $f' \in S_n$ such that $f'$ is better than $f$? And related to this:

2. Are there infinitely many integers $n\geq 3$ such that there is $f_0\in S_n$ such that no element of $S_n$ is better than $f_0$?

The answer to question 1 is yes. In fact, we can generalize the answer even further:

Theorem: Let there be $m ≥ 1$ presents in $n ≥ m + 2$ boxes. Then for any order $a$ of opening the boxes, there is another order $b$ such that $b$ is more likely to find the first present than $a$.

Proof: Let $b(k) = a(k+1)$ for $1 ≤ k < n$ and let $b(n) = a(1)$. Then $a$ wins only if there is a present in box $a(1) = b(n)$ and no present in box $a(2) = b(1)$, ties if both of these boxes contain a present and loses otherwise (i.e. if there is no present in box $a(1) = b(n)$). Thus order $a$ wins with probability $p_a = \frac{m}{n} \cdot \frac{n-m}{n-1}$ while order $b$ wins with probability $p_b = \frac{n-m}{n} = \frac{n-1}{m} p_a$. Since $n - 1 > m$, it follows that $p_b > p_a$.

(Note: If $n = m + 1$, any two orders that open the same box first always tie, while any two orders that don't open the same box first each have a $\frac{1}{n}$ chance of winning on the first box and will otherwise tie.)

This also shows that the answer to your question 2 is no.

Answer 2

This is not exactly an answer, but rather a pointer to some other references.

For the original version of the puzzle that I published in the American Mathematical Monthly, search for "fair permutations" on my webpage.

A version of the problem was discussed on the Puzzling Stack Exchange a few years ago; see in particular the graph at the end of Albert Lang's answer, which shows that if you consider arbitrary rectangles, it is not always the case that the player who searches fewer but longer lines will have the advantage.

Most recently, at my request, Gil Kalai featured the puzzle on his blog (see also the followup post).

Answer 3

This is not an answer, but only an attempt to remove the "mind-boggling" aspect of the problem.

As in the OP, let $S_n$ denote the set of all permutations of the set $[n]:=\{1,\dots,n\}$. Let $P_n$ denote the set of subsets of $[n]$ of cardinality $2$.

For any permutation $\pi\in S_n$ and any "unordered pair" $p\in P_n$, let $$\tau_\pi(p):=\min\{i\in[n]\colon\pi(i)\in p\}. $$ Also, any permutation $\pi\in S_n$, which we can think of as a re-labeling of the elements of the set $[n]$, induces the permutation/re-labeling (which we will denote also by $\pi$) of the set $P_n$ by the formula $\pi(p):=\{\pi(i)\colon i\in p\}$ for $p\in P_n$.

Take any permutations $\pi$ and $\rho$ in $S_n$. We are comparing the families $\tau_\pi=(\tau_\pi(p))_{p\in P_n}$ and $\tau_\rho=(\tau_\rho(p))_{p\in P_n}$ (that is, the functions $\tau_\pi$ and $\tau_\rho$ from $P_n$ to $[n]$), by considering (say) the difference $$d(\pi,\rho):=\sum_{p\in P_n}1(\tau_\pi(p)<\tau_\rho(p))-\sum_{p\in P_n}1(\tau_\pi(p)>\tau_\rho(p)).$$ Note that $\tau_\pi(\pi(p))=\tau_\rho(\rho(p))$ for all $p\in P_n$ or, equivalently, $\tau_\rho(p)=\tau_\pi(\pi(\rho^{-1}(p)))$ for all $p\in P_n$; that is, $\tau_\rho=\tau_\pi\circ\pi\circ\rho^{-1}$. So, the family $\tau_\rho$ is obtained from the family $\tau_\pi$ by applying the permutation/re-labeling $\pi\circ\rho^{-1}$ to the index set $P_n$ of the "unordered pairs".

So, there is no reason to expect that $\tau_\rho=\tau_\pi$ in general, and hence there is actually no reason to expect that $d(\pi,\rho)=0$ for arbitrary permutations/re-labelings $\pi$ and $\rho$ in $S_n$.

---

---

Below is an illustration, in Mathematica, of what has been said above:

---

Answer 4

This topic is fascinating, but the two specific questions asked are trivial, as indicated in the comment of Peter Taylor. Here is a paraphrase of that comment. The function $W$ has the form $W(a, b) = w(a^{-1} b)$, where $w(g) = W(1, g)$. Let $f(g) = w(g) - w(g^{-1})$. Then $a$ is better than $b$ if and only if $f(a^{-1}b) > 0$. Let $k$ be the number of $g \in S_n$ such that $f(g) > 0$. Then for every $a$ there are exactly $k$ elements $b$ such that $f(a^{-1}b) > 0$, i.e., $a$ is better than $b$, and there are exactly $k$ elements $b$ such that $f(b^{-1} a) > 0$, i.e., $b$ is better than $a$. Moreover $k \ne 0$ because otherwise no element is better than any other, which we have seen is not the case.