Japan Mathematical Olympiad

For $k$ primes $p_1,p_2,\dots ,p_k$, denote by $X(p_1,p_2,\dots ,p_k)$ the set of all integers in $\{2,3,\dots ,50\}$ that do not have any prime factor other than $p_1,p_2,\dots ,p_k$. The blackboard is said to be in $(p_1,p_2,\dots ,p_k)$-good situation or simply good, if the set of all integers that are already erased is identical to $X(p_1,p_2,\dots ,p_k)$. Lemma. If the blackboard becomes good after a turn, the player who plays the turn is able to win regardless of the opponent's actions. Proof. Suppose that after the turn, the blackboard becomes in $(p_1,p_2,\dots ,p_m)$-good situation. We only have to consider the case the opponent can erase at least one integer in the next turn. Denote the set of integers erased by the opponent in the next turn by $T_1$. All elements in $T_1$ have a prime factor other than $p_1,p_2,\dots ,p_m$. Let $q_1,q_2,\dots ,q_n$ be prime numbers that are not in $\{p_1,p_2,\dots ,p_m\}$ but appears as prime factors of some of elements in $T_1$. Then, $X(p_1,p_2,\dots ,p_m)\cup T_1$ is a subset of $X(p_1,p_2,\dots ,p_m,q_1,q_2,\dots ,q_n)$. Denote by $T_2$ the set of all elements in $X(p_1,p_2,\dots ,p_m,q_1,q_2,\dots ,q_n)$ not included in $X(p_1,p_2,\dots ,p_m)\cup T_1$. Since $q_1,q_2,\dots ,q_n\in T_2$ but $q_1,q_2,\dots ,q_n\notin X(p_1,p_2,\dots ,p_m)\cup T_1$, $T_2$ is not empty. Additionally, since any element in $T_2$ has a prime factor in $\{q_1,q_2,\dots ,q_n\}$, the player is able to erase all elements in $T_2$. From the discussion above, it is shown inductively that if the blackboard becomes good after a turn, the player who plays the turn can erase one or more integers and make the blackboard good at every turn afterwards. Especially, the player is able to erase at least one integer at every turn, which imply the player is able to win. ■ Let $r_1,r_2,\dots ,r_{\ell }$ be prime numbers which divide at least one element of $S$. If $S=X(r_1,r_2,\dots ,r_{\ell })$, then Alice can always win. If $S\ne X(r_1,r_2,\dots ,r_{\ell })$, $T:=X(r_1,r_2,\dots ,r_{\ell })\setminus S$ is not empty. Additionally, since any element in $T$ has a prime factor in $\{r_1,r_2,\dots ,r_{\ell }\}$, by the definition of $r_1,r_2,\dots ,r_{\ell }$, Bob can erase all elements in $T$ and make the blackboard in $(r_1,r_2,\dots ,r_{\ell })$-good situation. By the lemma, Bob can win regardless of actions of Alice. Therefore, the sets $S$ that satisfy the problem condition are those in the form of $X(p_1,p_2,\dots ,p_k)$ with some prime numbers $p_1,p_2,\dots ,p_k$. The number of such sets corresponds to the number of ways to choose one or more elements from the set of prime numbers less than or equal to 50, which is $\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\}$ (15 prime numbers). Therefore, the answer is $2^{15}-1$ sets.