Maths Olympiad Prep

Library / /63 of 63

Combinatorics Difficulty 7.9 National olympiad, round 2 Prove it Japan

Alice and Bob are playing a game using a blackboard. Initially, each of 2,3,,502, 3, \dots, 50 is written on the blackboard once. Also, a non-empty subset SS of {2,3,,50}\{2, 3, \dots, 50\} is given. In the first turn, Alice erases all the elements of SS from the blackboard. After that, the two players, starting with Bob, take turns erasing one or more integers from the blackboard. However, they cannot erase integers that are relatively prime to all of the integers erased in the opponent's previous turn. The game ends when a player has no integers left to erase at the beginning of their turn, resulting in that player's loss and the other player's win.
How many sets SS are there such that Alice can always win, regardless of Bob's actions?

Solution

For kk primes p1,p2,,pkp_1, p_2, \dots, p_k, denote by X(p1,p2,,pk)X(p_1, p_2, \dots, p_k) the set of all integers in {2,3,,50}\{2, 3, \dots, 50\} that do not have any prime factor other than p1,p2,,pkp_1, p_2, \dots, p_k. The blackboard is said to be in (p1,p2,,pk)(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(p1,p2,,pk)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 (p1,p2,,pm)(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 T1T_1. All elements in T1T_1 have a prime factor other than p1,p2,,pmp_1, p_2, \dots, p_m. Let q1,q2,,qnq_1, q_2, \dots, q_n be prime numbers that are not in {p1,p2,,pm}\{p_1, p_2, \dots, p_m\} but appears as prime factors of some of elements in T1T_1. Then, X(p1,p2,,pm)T1X(p_1, p_2, \dots, p_m) \cup T_1 is a subset of X(p1,p2,,pm,q1,q2,,qn)X(p_1, p_2, \dots, p_m, q_1, q_2, \dots, q_n).
Denote by T2T_2 the set of all elements in X(p1,p2,,pm,q1,q2,,qn)X(p_1, p_2, \dots, p_m, q_1, q_2, \dots, q_n) not included in X(p1,p2,,pm)T1X(p_1, p_2, \dots, p_m) \cup T_1. Since q1,q2,,qnT2q_1, q_2, \dots, q_n \in T_2 but q1,q2,,qnX(p1,p2,,pm)T1q_1, q_2, \dots, q_n \notin X(p_1, p_2, \dots, p_m) \cup T_1, T2T_2 is not empty. Additionally, since any element in T2T_2 has a prime factor in {q1,q2,,qn}\{q_1, q_2, \dots, q_n\}, the player is able to erase all elements in T2T_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 r1,r2,,rr_1, r_2, \dots, r_\ell be prime numbers which divide at least one element of SS. If S=X(r1,r2,,r)S = X(r_1, r_2, \dots, r_\ell), then Alice can always win. If SX(r1,r2,,r)S \neq X(r_1, r_2, \dots, r_\ell), T:=X(r1,r2,,r)ST := X(r_1, r_2, \dots, r_\ell) \setminus S is not empty. Additionally, since any element in TT has a prime factor in {r1,r2,,r}\{r_1, r_2, \dots, r_\ell\}, by the definition of r1,r2,,rr_1, r_2, \dots, r_\ell, Bob can erase all elements in TT and make the blackboard in (r1,r2,,r)(r_1, r_2, \dots, r_\ell)-good situation. By the lemma, Bob can win regardless of actions of Alice.
Therefore, the sets SS that satisfy the problem condition are those in the form of X(p1,p2,,pk)X(p_1, p_2, \dots, p_k) with some prime numbers p1,p2,,pkp_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}\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47\} (15 prime numbers). Therefore, the answer is 21512^{15}-1 sets.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.