Problem 2570

The answer is $n = 83 + 89 - 1 = 171$.
In general, if Ana has to decide between periods from the set $\mathcal{P} := \{p_1 > p_2 > \dots > p_r\}$ of pairwise distinct relatively prime positive integers for $r \ge 3$, the answer is $p_2 + p_3 - 1$.

### Bound
Suppose for the sake of contradiction that Ana has a winning sequence of integers $x_1, \dots, x_n$ with $n \le p_2 + p_3 - 2$. We will generate contradictions by providing two primes $p, q \in \mathcal{P}$ and associated nonconstant functions $f_p, f_q: \mathbb{Z} \to \mathbb{Z}$ with periods $p$ and $q$ respectively such that $f_p(x_i) = f_q(x_i)$ for all $i$.

Claim — There exists a prime $r \in \mathcal{P}$ such that for all primes $p \in \mathcal{P} \setminus \{r\}$, the set of integers $\{x_1, \dots, x_n\}$ forms a complete residue class modulo $p$ (i.e. for all $t$, there exists $i$ such that $x_i \equiv t \pmod{p}$).

Claim — Suppose for the sake of contradiction that such $r$ didn't exist, and there were in fact two primes $p, q \in \mathcal{P}$ such that $\{x_1, \dots, x_n\}$ did not form a complete residue class modulo either $p$ or $q$. Concretely, consider $t, s$ such that there is no $i$ with $x_i \equiv t \pmod{p}$ and no $j$ with $x_j \equiv s \pmod{q}$.
Construct the functions $f_p, f_q: \mathbb{Z} \to \mathbb{Z}$ as

$$f_p(x) = \begin{cases} 0 & \text{if } x \not\equiv t \pmod{p} \\ 1 & \text{if } x \equiv t \pmod{p} \end{cases}$$
and
$$f_q(x) = \begin{cases} 0 & \text{if } x \not\equiv s \pmod{q} \\ 1 & \text{if } x \equiv s \pmod{q} \end{cases}.$$
We have $f_p(x_i) = f_q(x_i) = 0$ for all $i$, which is the desired contradiction.

Let $r$ be the prime from the above claim. Let $p, q$ be the largest two primes in $\mathcal{P} \setminus \{r\}$, so $n \le p+q-2$. Construct the graph $G_{pq}$ with vertex set $\{x_1, \dots, x_n\}$ and edge $x_i \sim x_j$ if $p \mid x_i - x_j$ or $q \mid x_i - x_j$. The following claim allows us to construct a pair of bad functions $f_p, f_q$.

Claim — The graph $G_{pq}$ is disconnected.

Proof. Let $G_p$ be the graph on vertex set $\{x_1, \dots, x_n\}$ with edge $x_i \sim x_j$ if $p \mid x_i - x_j$. Note that $G_p$ is a collection of $p$ disjoint cliques, one for each residue class modulo $p$.

Prune the graph into $G'_p$, where each clique $K_r$ is replaced by a path of edge-length $r-1$. Define $G'_q$ similarly, and let $G'_{pq}$ be the union of $G'_p$ and $G'_q$.
Note that $G_{pq}$ and $G'_{pq}$ have the exact same connectivity properties. We have
$$|E(G'_{pq})| \le |E(G'_p)| + |E(G'_q)| = (n-p) + (n-q) \le n-2,$$
so $G'_{pq}$ is disconnected, as desired. $\Box$

Suppose $A \sqcup B = \{x_1, \dots, x_n\}$ are sets of disjoint vertices in $G_{pq}$. Construct the functions $f_p, f_q : \mathbb{Z} \to \mathbb{Z}$ as
$$f_p(x) = \begin{cases} 0 & \text{if } x \equiv a \pmod{p} \text{ for some } a \in A \\ 1 & \text{if } x \equiv b \pmod{p} \text{ for some } b \in B \end{cases}$$
and
$$f_q(x) = \begin{cases} 0 & \text{if } x \equiv a \pmod{q} \text{ for some } a \in A \\ 1 & \text{if } x \equiv b \pmod{q} \text{ for some } b \in B. \end{cases}$$
These are well defined due to the fact that $p, q \nmid a-b$ for $a \in A$ and $b \in B$, and the fact that $A \sqcup B$ forms a complete residue class modulo $p$. Again, we have $f_p(x_i) = f_q(x_i)$ for all $i$, which is the desired contradiction.

## Construction
Let $n = p_2 + p_3 - 1$. We claim that Ana has a winning strategy with the selection $x_i = p_1(i-1)$. Indeed, suppose that Banana writes down the values $y_1, \dots, y_n$ in order. We will show that Ana can always reconstruct $p$.

Claim — If $y_1 = \dots = y_n$, then Ana can correctly guess $p = p_1$.

Proof. Suppose for the sake of contradiction that $p < p_1$. Then, since $x_1, \dots, x_n$ forms a complete residue class modulo $p$, $f$ must be a constant function, which is the desired contradiction. $\Box$

We can now assume that $y_1, \dots, y_n$ are not all equal, which means $p \ne p_1$. Suppose for the sake of contradiction that there are two primes $q, r < p_1$ with associated nonconstant functions $f_p, f_q : \mathbb{Z} \to \mathbb{Z}$ with periods $q$ and $r$ respectively, such that $f_q(x_i) = f_r(x_i) = y_i$ for all $i$.
The following claim shows that $y_1, \dots, y_n$ must all be equal, which is the desired contradiction.

Claim — Let $G$ be the graph on vertex set $\{0, \dots, q+r-2\}$ with edge $i \sim j$ if $|i-j| \in \{q, r\}$. The graph $G$ is connected.

Proof. Note that $G$ has $q+r-2$ edges, so it suffices to show that it has no cycles. Suppose for the sake of contradiction it had a cycle $c_1, \dots, c_k$ with $k \ge 3$ and indices taken mod $k$.
Suppose first that $c_{i+1} - c_i = q$. Then, $c_{i+2} - c_{i+1}$ cannot be $-q$ (else $c_i = c_{i+2}$), it cannot be $r$ (else $c_{i+2} > q+r-2$), so $c_{i+2} - c_{i+1} \in \{q, -r\}$.

$$c_{i+1} - c_i = q \implies c_{i+2} - c_{i+1} \in \{q, -r\}$$

$$\begin{align*} c_{i+1} - c_i &= -q \implies c_{i+2} - c_{i+1} \in \{-q, r\} \\ c_{i+1} - c_i &= r \implies c_{i+2} - c_{i+1} \in \{-q, r\} \\ c_{i+1} - c_i &= -r \implies c_{i+2} - c_{i+1} \in \{q, -r\}. \end{align*}$$
Thus, either all consecutive differences of vertices in the cycle are in $\{q, -r\}$, or all in $\{-q, r\}$. Assume the first case, proof is similar for second case.
Let $a$ be the number of consecutive differences that are $q$, and $b$ be the number that are $-r$. We see that $a + b = k$ and $qa - rb = 0$. The second condition implies that $a \ge r$ and $b \ge q$, so we have $k \ge q + r$, which is the desired contradiction since $G$ has only $q + r - 1$ vertices. $\square$