最后丢弃

Last to Discard

专题: Brainteaser / 脑筋急转弯
难度: L5
来源: OpenQuant

题目详情

Alice 和 Bob 用一堆 $n$ 卡开始游戏。通过滚动公平的 $1000$ 双面骰子来选择 $n$ 。轮到每个玩家时，将当前的牌堆分成两堆，并丢弃较小的一堆。如果两堆大小相同，则仍丢弃其中一堆。如果玩家无法在自己的回合中分割牌堆，他们就输了。如果爱丽丝先走，并且两个玩家都发挥最佳，她获胜的概率是多少？

Alice and Bob start a game with a stack of $n$ cards. Let $n$ be chosen by rolling a fair $1000$ sided die. On their turn, each player will split the current stack of cards into two piles and discard the smaller pile. If both piles are the same size, one pile is still discarded. If a player is unable to split the stack of cards on their turn, they lose. If Alice goes first and both players play optimally, what is the probability that she wins?

解析

让我们从基本情况开始，逐步了解哪些套牌尺寸给我们带来了胜利，哪些牌组失败了。

如果我们有一副大小为 $1$ 的牌，这显然是一个失败的数字，因为我们无法分割这副牌。另一方面， $2$ 的牌组大小获胜，因为通过分割它，我们可以给对手 $1$ 的牌组大小。请注意，能够给出失败的号码意味着你拥有获胜的号码。反之亦然。如果我们的牌组大小为 $3$ ，则我们只能给出 $2$ 的牌组大小，这是中奖号码。因此 $3$ 是一个失败的号码。

当你的牌组大小为 n 时，你可以给对手的牌组大小范围将在 $\left\lceil \frac{n}{2} \right\rceil$ 和 $n-1$ 之间。因此， $4$ 、 $5$ 和 $6$ 都是获胜号码，因为我们能够从这些位置的每一个位置给对手一个 $3$ 。

继续这一趋势，我们看到所有可以表示为 $2^k-1$ 的数字都在丢失。原因是你从该位置给出的所有号码都是中奖号码。

$1000$ 下有 $9$ 号码（尝试 $log_2(1000)$ ）比 $2$ 的 $2$ 的幂小，因此有 $9$ 丢失号码。因此 Alice 获胜的概率为 $\boxed{\frac{991}{1000}}$

Original Explanation

Let's start from the base case and work our way up to see which deck sizes given to us are winning and which ones are losing.

If we are given a deck of size $1$ , this is clearly a losing number as we can not split this deck. On the other hand, a deck size of $2$ is winning since by splitting this we can give our opponent a deck size of $1$ . Note that being able to give a losing number means you have a winning number. The opposite is also true. If we have a deck size of $3$ , we see that we can only give a deck size of $2$ which is a winning number. Hence $3$ is a losing number.

The range of deck sizes you can give your opponent with a deck size of n will be between $\left\lceil \frac{n}{2} \right\rceil$ and $n-1$ . Therefore, $4$ , $5$ , and $6$ are all winning numbers because we are able to give our opponent a $3$ from each of these positions.

Continuing this trend we see all numbers that can be represented as $2^k-1$ are losing numbers. The reason for this is all numbers you can give from that position are winning numbers.

There are $9$ numbers (try $log_2(1000)$ ) that are $1$ less than a power of $2$ under $1000$ , therefore there are $9$ losing numbers. Alice's probability of winning is therefore $\boxed{\frac{991}{1000}}$