In the single-player game of PlaceIt, a player must sort a random sequence of numbers in an online fashion. The game begins by sampling a sequence \(S = (s_1, \ldots , s_{20})\) of numbers uniformly at random from \(\{1, \ldots , 999\}\) without replacement. The elements of S are presented one by one to the player. Upon seeing an element \(s_i\) , a player must try to guess its rank, that is, the number n such that \(s_i\) is the \(n^{\text {th}}\) smallest number in S. For example, if \(s_1 = 496\) , the player might reasonably guess that \(s_1\) will be the \(10^{\text {th}}\) smallest number in S. The player must guess the rank of all 20 numbers of S correctly to win the game. Additionally, the game requires each guess to be consistent with previous guesses, so if the player guessed the rank of \(s_1 = 240\) to be 6, and then \(s_2 = 316\) is presented, the player is forced to guess a rank larger than 6 for \(s_2\) . If at any point the player cannot make a consistent guess, they lose immediately. Once a rank has been assigned, it cannot be changed. This article presents a mathematical analysis of PlaceIt, in which we prove that the optimal strategy wins with probability close to 0.0001335. We then extend our analysis to a continuous variant of the game.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Mathematical Analysis of PlaceIt: A Game of Perfect Online Sorting

  • Pablo Ruiz Cuevas,
  • Casey Chock,
  • Bernardo Subercaseaux

摘要

In the single-player game of PlaceIt, a player must sort a random sequence of numbers in an online fashion. The game begins by sampling a sequence \(S = (s_1, \ldots , s_{20})\) of numbers uniformly at random from \(\{1, \ldots , 999\}\) without replacement. The elements of S are presented one by one to the player. Upon seeing an element \(s_i\) , a player must try to guess its rank, that is, the number n such that \(s_i\) is the \(n^{\text {th}}\) smallest number in S. For example, if \(s_1 = 496\) , the player might reasonably guess that \(s_1\) will be the \(10^{\text {th}}\) smallest number in S. The player must guess the rank of all 20 numbers of S correctly to win the game. Additionally, the game requires each guess to be consistent with previous guesses, so if the player guessed the rank of \(s_1 = 240\) to be 6, and then \(s_2 = 316\) is presented, the player is forced to guess a rank larger than 6 for \(s_2\) . If at any point the player cannot make a consistent guess, they lose immediately. Once a rank has been assigned, it cannot be changed. This article presents a mathematical analysis of PlaceIt, in which we prove that the optimal strategy wins with probability close to 0.0001335. We then extend our analysis to a continuous variant of the game.