先手还是后手：选到有公因子就输

Prime First

专题: Strategy / 策略
难度: L6
来源: QuantQuestion

题目详情

集合 $S=\{2,3,\dots,30\}$ 。Alice 与 Bob 轮流从 $S$ 中选一个未选过的整数。

规则：若某人选到的整数与先前已被选过的任意整数有公因子（>1），则该人立刻输。

Alice 可以选择先手或后手。令 $p=1$ 表示应先手， $p=2$ 表示应后手。

已知 Alice 在她第一步有 6 个最优首选 $v_1,\dots,v_6$ 。求

100p+\frac{v_1+\cdots+v_6}{6}.

Consider the set of integers $S = \{2, 3, \dots, 30\}$ . Alice and Bob play a game where they take turns selecting integers from $S$ . The first player to select an integer that shares a common factor with a previously picked integer loses. Alice has the ability to determine if she wants to select first or second. Assume both players play optimally. Let $p = 1$ if Alice should choose to go first and $p = 2$ if she should go second. There are $6$ optimal selections $v_1,\dots,v_5$ for Alice's first turn. Find $100p + \frac{v_1 + v_2 + v_3 + v_4 + v_5 + v_6}{6}$ .

解析

Alice 应该先手（ $p=1$ ）。她可以先选 6（或 12/18/24），一次性“消掉”质因子 2 与 3，从而把局面引导到对自己有利的必胜结构；另外 5 与 25 也能作为必胜开局。

6 个最优首选可取 $\{6,12,18,24,5,25\}$ ，因此

100\cdot 1+\frac{6+12+18+24+5+25}{6}=115.

Original Explanation

Consider all the primes in $S: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29$ . There are $10$ such integers. The key idea to notice here is that for whoever selects the integer $6$ , that eliminates $2$ and $3$ . Therefore, no other pairwise products of primes among the remaining prime integers are at most $30$ . Therefore, there would be $8$ primes left, and whoever is selecting first in this new game loses, as they can only eliminate one prime factor a turn. However, this "new game" is really just the second turn our game after we eliminate $2$ and $3$ . Therefore, Alice should go first, select the value $6$ (alternatively, $12, 18,$ or $24$ also work, as they have the same primes in the factorization) so that she can eliminate both $2$ and $3$ , and then Bob and Alice alternate selecting among the remaining prime integers. Then, Bob would be forced to pick some non-prime integer, which will have a prime factor among those already eliminated, so Bob will lose. Therefore, Alice should go first, and the answer is $1$ .

However, there is also another sneaky starting integer, which is $5$ . This is because regardless of what Bob selects on his first turn after Alice selects $5$ , Alice can force Bob to eliminate one prime factor at a time after her next turn, so this also works. Since $5$ works, $5^2 = 25$ also works. Therefore,

100(1) + \frac{6 + 12 + 18 + 24 + 5 + 25}{6} = 115