Taxman 游戏：最大得分

Taxman

专题: Brainteaser / 脑筋急转弯
难度: L4
来源: QuantQuestion

题目详情

黑板上写着 1..10。你每次选一个数，税官会拿走所有能整除该数的数。

你只能选择那些“仍至少有一个因子尚未被税官拿走”的数。直到没有可选数为止。若最后还有未被拿走的数，则税官把它们全部拿走。

你的得分是你选到的数之和。问：最优策略下你的最大得分是多少？

We start with the numbers $1 - 10$ on a board. You pick a number. The taxman then takes all the numbers that divide it evenly. We do this until there are no numbers left. However, you can only pick numbers that have at least one factor that hasn't been taken yet. If there are any unclaimed numbers at the end, the taxman takes them. Your score is the total of the numbers that you take. Following optimal strategy, what is your max possible score?

解析

最优选择序列可以达到拿到 $6,7,8,9,10$ ，总和为 40。

因此最大得分为 40。

Original Explanation

Notice that we can only take one prime off the board since all the primes are divisible only by $1$ and themselves. Thus for our first pick, let's choose $7$ (the largest prime on the board). The taxman then takes $1$ and the board becomes $2$ , $3$ , $4$ , $5$ , $6$ , $8$ , $9$ , and $10$ . We can't choose $2$ , $3$ , or $5$ since they are prime and don't have any more factors. We should never choose $4$ because we then can't take $8$ later. In this case, the best choice to take is $9$ since it is one of the larger numbers and only has one factor left ( $3$ ). Now the board becomes $2$ , $4$ , $5$ , $6$ , $8$ , and $10$ . Out of this set, $6$ is the only number with only one factor so let's take it. Now the taxman takes $2$ . The board is now $4$ , $5$ , $8$ , and $10$ . Now it doesn't matter what order we take $8$ and $10$ , the taxman will get $4$ and $5$ . Thus the numbers we have are $6$ , $7$ , $8$ , $9$ , and $10$ which gives you a score of $40$ and the taxman has $1$ , $2$ , $3$ , $4$ , $5$ which gives them a score of $15$ . You win with a score of $40$ !