Problem 2152

Solution:

We will use the following notation. If $S \subseteq \mathbb{Z}^{+}$ is a subset of the positive integers and $D$ is defined as in the problem statement, define $d(S) = D \backslash S$. In addition, the $d$-sequence of $S$, written $\{d^{S}\}_{n \in \mathbb{Z}^{+}}$, is defined recursively as $d_{0}^{S} = S$, and $d_{n+1}^{S} = d(d_{n}^{S})$ for each $n \in \mathbb{Z}^{+}$.

Let $p_{1}, p_{2}, \ldots$ be an enumeration of all the prime numbers. Alice chooses the sets
$$A = \{p_{m}^{n} \mid n \equiv m \bmod 3,\ 0 < n \leq m\}, \quad B = \{p_{m}^{n} \mid n \equiv m-1 \bmod 3,\ 0 < n \leq m-1\}$$
and
$$C = \mathbb{Z}^{+} \backslash (A \cup B)$$
It is clear that each positive integer belongs to exactly one of the sets $A$, $B$ or $C$. By induction we readily get that
$$d^{k}(A) = \begin{array}{ll} \{p_{m}^{n} \mid n \equiv m \bmod 3,\ n \leq m-3k/2\} \\ \{p_{m}^{n} \mid n \not\equiv m \bmod 3,\ n \leq m-1-3(k-1)/2\} \end{array} \quad \text{ if } k \text{ is even and } k \neq 0$$
and
$$d^{k}(B) = \begin{array}{lll} \{p_{m}^{n} \mid n \equiv m-1 \bmod 3,\ n \leq m-1-3k/2\} & \text{ if } k \text{ is even and } k \neq 0 \\ \{p_{m}^{n} \mid n \not\equiv m-1 \bmod 3,\ n \leq m-2-3(k-1)/2\} & \text{ if } k \text{ is odd. } \end{array}$$
If $m \in \mathbb{Z}^{+}$ then $6m$ is definitely in $C$ as $6m$ is not a power of a prime. This means that all positive integers divide at least one number in $C$. It follows that
$$d(C) = \mathbb{Z}^{+} \backslash C = \mathbb{Z}^{+} \backslash (\mathbb{Z}^{+} \backslash (A \cup B)) = A \cup B = \{p_{m}^{n} \mid n \not\equiv m-2 \bmod 3,\ 0 < n \leq m\}$$
By induction it follows that all of the sets $d^{k}(M)$ are all distinct. Hence Bob can never create the same set in two different ways.

Remark. In fact Alice has to partition the positive integers in at least three parts if she wishes to beat Bob. It is clear that selecting a single set, namely $\mathbb{Z}^{+}$, will not do as $d(\mathbb{Z}^{+}) = \emptyset$ and $d(\emptyset) = \emptyset$. Next assume Alice has partitioned the positive integers in two sets $A$ and $B$. It can be assumed that $d(A) \neq B$ and $d(B) \neq A$ as Bob would win in either case. As $d(A)$ is disjoint from $A$ and $B$ is the complement of $A$ this means that $d(A)$ is a strict subset of $B$. Hence there is some $b$ in $B$ that does not belong to $d(A)$. The implication is that $b$ does not divide any number in $A$. Similarly there exists a number $a$ in $A$ that does not divide any number in $B$. Their product $ab$ belongs to either of the sets $A$ or $B$ and is divisible by both $a$ and $b$. This contradicts the existence of said numbers, $a$ and $b$. In fact we have proven for any subset $A$ of $\mathbb{Z}^{+}$ that $d(A) = \mathbb{Z}^{+} \backslash A$ or $d(\mathbb{Z}^{+} \backslash A) = A$.

Solution:

Use the same notation as in solution 1. We wish to construct a partition $\bigcup_{i \in \mathbb{Z}^{+}} A_{i}$ of the positive integers, such that no two sets among all sets in $\{d^{A_{1}}\}_{n \in \mathbb{Z}^{+}}, \{d^{A_{2}}\}_{n \in \mathbb{Z}^{+}}, \ldots$ are equal.

To begin with, consider a partition $\bigcup_{i \in \mathbb{Z}^{+}} P_{i}$ of the primes, such that each $P_{i} = \{p_{i1}, p_{i2}, \ldots\}$ is infinite. We may assume each set is infinite since the set of primes and $\mathbb{Z}^{+} \times \mathbb{Z}^{+}$ both are countable, so there exists a bijection between them. Define the sets
$$Q_{i} = \{p_{i1}, p_{i2}^{2}, p_{i3}, p_{i3}^{3}, p_{i4}^{2}, p_{i4}^{4}, p_{i5}, p_{i5}^{3}, p_{i5}^{5}, \ldots\}$$
consisting of $p_{ij}^{j}, p_{ij}^{j-2}, \ldots, p_{ij}^{(1,2)}$ for each $p_{ij} \in P_{i}$. By the exponent $(1,2)$ we indicate that the last power is 1 when $j$ is odd and 2 when it is even.

We will include the remaining integers $\{r_{1}, r_{2}, \ldots\} = \mathbb{Z}^{+} \backslash (\bigcup_{i \in \mathbb{Z}^{+}} Q_{i})$ to the partition as follows. First, add $r_{1}$ to some set $Q_{i_{1}}$, such that $\gcd(r_{1}, q) = 1$ for each $q \in Q_{i_{1}}$. Then, for each $k \in \mathbb{Z}^{+}$, add $r_{k+1}$ to a set $Q_{i_{k+1}}$ where $i_{k+1} > i_{k}$, such that $\gcd(r_{k+1}, q) = 1$ for each $q \in Q_{i_{k+1}}$. Note that such an $i_{k+1}$ always exists, since there always is an infinite amount of prime divisors among $Q_{i_{k}+1}, Q_{i_{k}+2}, \ldots$, and $r_{k+1}$ only has a finite amount of prime divisors.

The collection of $Q_{i}$ now forms a partition of $\mathbb{Z}^{+}$. What remains is to show that it satisfies Alice's winning condition.

We first see that we may ignore all the $r_{k}$. By definition, no divisor of $r_{k}$ coincides with any divisor of $Q_{i_{k}}$, and their contributions in the $d$-sequence will therefore be completely disjoint. As $d(d(\{r_{k}\})) = \emptyset$, the $d$-sequence will show no trace of the $r_{k}$ after the second element. Hence, we will work with the original $Q_{i}$.

We observe that $d(Q_{i}) = \{1, p_{i2}, p_{i3}^{2}, p_{i4}, p_{i4}^{3}, p_{i5}^{2}, p_{i5}^{4}, p_{i6}, p_{i6}^{3}, p_{i6}^{5}, \ldots\}$. This is simply $Q_{i}$ with the indices shifted by 1 and with an added 1. As this set essentially is on the same form as $Q_{i}$, we see that $\{d^{Q_{i}}\}_{n}$ consists of every possible shift in indices of the first set $Q_{i}$ (except the element 1 appearing in every other set). It is therefore obvious that the sets in the sequence are pairwise distinct. Additionally, the set of primes dividing some element in some set of $\{d^{Q_{i}}\}_{n}$ is $P_{i}$. Since the $P_{i}$ partition the primes, it is clear that all the sets in all the $d$-sequences of the $Q_{i}$ are distinct, which is what we wanted.

Remark. The main idea of the problem is to construct a single set $S$, such that the sets in the $d$-sequence of $S$ are pairwise distinct. Any set with similar properties to the $Q_{i}$ should give a valid initial collection $\mathcal{C}$ such that Alice wins.