Skip to main content
MathOverflow

Return to Answer

actually answer the question
Source Link
Ilmari Karonen
Ilmari Karonen
  • 1.3k
  • 9
  • 13

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.

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.

Source Link
Ilmari Karonen
Ilmari Karonen
  • 1.3k
  • 9
  • 13

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.