The answer is $83 + 89 - 1 = \boxed{171}$. Upper bound We select $x_1,x_2,\dots,x_{171}$ such that \begin{align*} x_i &\equiv i\pmod{89!} \\ x_i &\equiv 0 \pmod{97}. \end{align*}for all $i=1,2,\dots,171$. Then, first, Ana can determine if $p = 97$ or not by checking if $f(x_1),\dots,f(x_{171})$ are all equal. Henceforth assume that $p\neq 97$. Assume that Ana cannot distinguish between $p$-periodic and $q$-periodic for some primes $p<q<97$. Construct a graph $G$ with vertices $1,2,3,\dots,p+q-1$, and edges joining $(x,x+p)$ and $(x,x+q)$ for all $x$. The graph has $p+q-1$ vertices, $p+q-2$ edges, and no cycles (because any cycles must have at least $q$ edges of type $(x,x+p)$ and at least $p$ edges of type $(x,x+q)$). Hence, $G$ connected. Now, if $f$ and $g$ are two functions indistinguishible by Ana, we must have that $f(u)=f(v)$ for any edge $(u,v)$ of $G$. This means that $f$ is constant at all vertices in $G$, so $f$ is constant modulo $p$ and $q$, a contradiction. Lower bound Assume there are values of $x_1,\dots,x_n$ that works. Call a prime $p$ good if $x_1,\dots,x_n$ hits every residue modulo $p$ and bad otherwise. Claim. There is at most one bad prime. Proof. Suppose that $p$ and $q$ are bad primes, and suppose that $r\pmod p$ and $s\pmod q$ are residues not hit by $x_1,\dots,x_n$. Then, the functions $$f_1(x) = \begin{cases} 1 & x\equiv r\pmod p \\ 0 & \text{otherwise} \end{cases},\quad f_2(x) = \begin{cases} 1 & x\equiv s\pmod q \\ 0 & \text{otherwise} \end{cases}$$are indistinguishable by Ana. This is a contradiction. $\blacksquare$ Claim. If $p$ and $q$ are two good primes, then $n\geq p+q-1$. Proof. Construct a graph $G_p$ and $G_q$, both with vertices on $x_1,\dots,x_n$. Two vertices $x_i$ and $x_j$ are joined by an edge in $G_p$ if $x_i\equiv x_j\pmod p$, and similarly for $G_q$ (but congruent modulo $q$) instead. Since $p$ and $q$ are both good, $G_p$ has $p$ components, while $G_q$ has $q$ components. Thus, $G_p\cup G_q$ has at least $p+q-|V(G_p)| = p+q-n$ components. Thus, if $n\leq p+q-2$, then $G_p\cup G_q$ is disconnected, so the set $\{x_1,\dots,x_n\}$ can be partitioned into two groups $A\cup B$ such that no $a\in A$ and $b\in B$ that are congruent modulo $p$ or modulo $q$. Now, we can define two functions \begin{align*} f_1(x) &= \begin{cases} 1 & x\equiv a\pmod p\text{ for some } a\in A \\ 0 & x\equiv b\pmod p\text{ for some } b\in B \end{cases} \\[4pt] f_2(x) &= \begin{cases} 1 & x\equiv a\pmod q\text{ for some } a\in A \\ 0 & x\equiv b\pmod q\text{ for some } b\in B \end{cases} \end{align*}which will be indistinguishable to Ana, but $f_1$ has period $p$ and $f_2$ has period $q$. This is a contradiction. $\blacksquare$ The two claims combined proves the problem: at least two primes in $83$, $89$, $97$ are good, so $n\geq 83+89-1=171$.

this is a devious p1 This post will only provide an alternative way to see the bound, which I believe is isomorphic but this is how I saw it in contest. We claim that the $x_i$ must cover all residues mod $p$ for all primes $p < 100$ except for at most one. Otherwise, if we have $p$ and $q$ as possible periods, one can just construct $f_1$ to be $1$ on all the $x_i$, but $2$ on a residue not covered mod $p$, and $f_2$ to be $1$ on all the $x_i$, but $2$ on a residue not covered mod $q$. These are indistinguishable. Draw a table, with rows indexed by residues mod $q$ and columns indexed by residues mod $p$. For each $x_i$, write $i$ in the corresponding table entry. Note every row must have an $x$ and every column must have an $x$. Now suppose we have $p$ and $q$ as two possible periods for $f$. If $i$ and $j$ are in the same row or in the same column, then it follows that $f(x_i) = f(x_j)$. This naturally establishes a set of connected components on the table; if we have more than one connected component, we can construct a nonconstant $f$. Hence it follows that the table has exactly one connected component, where $i$ is connected to $j$ if there exists a sequence of rook moves in the table, landing on labeled cells only, going from $i$ to $j$. Erase every label above the bottommost label in each column, and remove any labels so that each cell has at most one label. This gives us $p$ labeled cells. Now let $r$ be the number of rows with no labels; in order to make sure every residue mod $q$ is covered, we immediately need $r$ more labels. We can WLOG place these first, one per unlabeled row. Note then that the number of connected components is still $q-r$, since we placed exactly one per unlabeled row. From here, each additional label decreases the number of connected components by at most $1$. Since the number of connected components is $q-r$, we need at least $q-r-1$ labels. Thus in total we need at least $p+r+q-r-1 = p+q-1$ labels, as desired. Picking $p$ and $q$ to be the 2nd and 3rd largest primes beneath 100 gets the lower bound.

In general, to distinguish between periods $\mathcal P = \{p_1 > p_2 > \dots p_k\}$ for $k \ge 3$ requires $p_2 + p_3 - 1$. I'm not going to try to post a full solution to this problem. Instead, I want to give another (equivalent) way to phrase the main idea in the posts above using a grid instead of a bipartite graph which makes the illustrations easier. It is a testament to the difficulty for this problem that, despite the length of the commentary here, this post is not going to actually be a complete solution. Instead, it was (for me) the minimum number of examples I needed to draw before I could even start to understand the solution. Let $S = \{ x_1, \dots, x_n \}$. Translating the condition, Ana loses if and only if for some $p \neq q \in \mathcal P$ one can write a function $f \colon S \to {\mathbb Z}$ which could extend both to a nonconstant function ${\mathbb Z} \to {\mathbb Z}$ with period $p$, and to a nonconstant function ${\mathbb Z} \to {\mathbb Z}$ with period $q$. So if you zoom in on some pair primes $(p,q)$, you can imagine looking at a table ${\mathbb Z}/p \times {\mathbb Z}/q$ where for each $x_i$ you draw a star in cell $(x_i \bmod p, x_i \bmod q)$. Then it makes sense to speak about whether a particular table is winning or losing for Ana. A $p$-periodic function is one whose rows are all the same value; a $q$-periodic function is one whose columns are all the same value. For the pictures below, we use $p = 3$ and $q = 5$. Example 1 --- generic losing table. For example, the table shown on the left with six stars is losing for Ana. It's losing because if one fills in $1$'s and $2$'s for some of the stars as shown to the right in red and blue, the table could be completed in both ways to nonconstant functions. \begin{align*} \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & \ast & \ast & & & \ast \\ 1 \bmod 3 & & & & \ast & \\ 2 \bmod 3 & & & \ast & & \ast \\ \end{array} &\implies \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} & & & {\color{red}1} \\ 1 \bmod 3 & & & & {\color{blue}2} & \\ 2 \bmod 3 & & & {\color{red}1} & & {\color{red}1} \\ \end{array} \\ &\implies \begin{cases} \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} \\ 1 \bmod 3 & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} \\ 2 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} \\ \end{array} & 3\text{-periodic} \\[8ex] \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{blue}2} & {\color{red}1} \\ 1 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{blue}2} & {\color{red}1} \\ 2 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{blue}2} & {\color{red}1} \\ \end{array} & 5\text{-periodic} \end{cases} \end{align*} Example 2 --- losing table with missing rows and columns. Here's another example of a losing table with six stars. \begin{align*} \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & \ast & \ast & \ast \\ 1 \bmod 3 & \ast & \ast & \ast \\ 2 \bmod 3 \\ \end{array} &\implies \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & & \\ 1 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & & \\ 2 \bmod 3 \\ \end{array} \\ &\implies \begin{cases} \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} \\ 1 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} \\ 2 \bmod 3 & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} \\ \end{array} & 3\text{-periodic} \\[8ex] \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{blue}2} & {\color{blue}2} \\ 1 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{blue}2} & {\color{blue}2} \\ 2 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{blue}2} & {\color{blue}2} \\ \end{array} & 5\text{-periodic} \end{cases} \end{align*}This example shows that in general, if your stars miss both some rows and miss some columns, then Ana certainly loses. Example 3 --- winning table with missing rows. However, here's another example of a winning table where some rows are neglected entirely. The idea is that if one tries to copy the counterexample from above, one of the two functions ends up being constant, so it doesn't work as a counterexample. \begin{align*} \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & \ast & \ast & \ast & \ast & \ast \\ 1 \bmod 3 \\ 2 \bmod 3 \\ \end{array} &\implies \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1}\\ 1 \bmod 3 \\ 2 \bmod 3 \\ \end{array} \\ &\implies \begin{cases} \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1}\\ 1 \bmod 3 & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} \\ 2 \bmod 3 & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} & {\color{blue}2} \\ \end{array} & 3\text{-periodic} \\[8ex] \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1}\\ 1 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1}\\ 2 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1}\\ \end{array} & 5\text{-periodic} \end{cases} \end{align*}And indeed, if the function could be extended to be row-constant, then all the stars must be filled with the same number. So then a column-constant one would be constant everywhere. Example 4 --- generic winning table. Finally, here's an example of a generic winning table that covers all rows and columns. \begin{align*} \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & \ast & \ast \\ 1 \bmod 3 & & \ast & \ast & \ast \\ 2 \bmod 3 & & & & \ast & \ast \\ \end{array} &\implies \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} \\ 1 \bmod 3 & & {\color{red}1} & {\color{red}1} & {\color{red}1} \\ 2 \bmod 3 & & & & {\color{red}1} & {\color{red}1} \end{array} \\ &\implies \begin{cases} \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1}\\ 1 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1}\\ 2 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1}\\ \end{array} & 3\text{-periodic} \\[8ex] \begin{array}{c|ccccc} \mod 5 \rightarrow & 0 & 1 & 2 & 3 & 4 \\ \hline 0 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1}\\ 1 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1}\\ 2 \bmod 3 & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1} & {\color{red}1}\\ \end{array} & 5\text{-periodic} \end{cases} \end{align*}The point is that this example is winning because it has a connectedness and spanning property. To say exactly what this means, suppose we filled in the numbers such that the table could be extended to both a row-constant and column-constant one. Then in any row, the starred numbers are equal; the same is true in any column. However, because of the layout of the stars, all the stars in fact have the same number, and because there's at least one star in each row (say), that makes the whole grid constant in that extension. More precisely: we can consider a simple graph $G$ on the starred numbers, where we connect two numbers in either the same row or column. The desired condition is the graph has vertices either in all rows or in all columns and is also connected. Summary. In short, the grids that can appear for a fixed pair $(p,q)$ fall into these categories: If the stars both misses some rows and misses some columns, it's always losing for Ana (Example 3). Now suppose the stars either cover all rows or cover all columns (or both). Define the graph on the stars we just mentioned with stars as vertices and edges in the same row or column. Then: Disconnected graphs are losing for Ana (Example 1). Connected graphs are losing for Ana (Example 4). In particular, if there's a full row of stars, the grid is actually still winning for Ana, even if there are other empty rows (Example 2). In order to solve the problem, one should then prove the following lemma (I think the easiest proof by induction). Lemma: Consider an $m \times n$ grid and define a graph on all $mn$ cells with the adjacency relation above (same row or same column). A spanning tree of this graph has at least $m + n - 1$ edges. Finally, to apply the lemma to the problem, we finally look at all primes again, with $\mathcal P = \{ p_1 > p_2 > \dots > p_k \}$. There is at most one exceptional prime in $\mathcal P$ where the $(x_k)$ do not span all residues modulo $p_i$. For any other two non-exceptional primes $p_i$ and $p_j$, we get $n \ge p_i + p_j - 1$. And so we in particular must have $n \ge p_2 + p_3 - 1$ (and this could only have equality if $p_1$ is the exceptional prime).

In case it makes anyone feel better, I think this problem is quite difficult. To be more precise, I was shown the problem for the first time today, and told the answer right away. After half an hour at a blackboard, I still could not convince myself why the claimed answer was correct or prove either direction. (By that time, I had drawn Example 4 above, but had yet to realize how Examples 1-3 above played in.)

Would anyone be kind enough to predict how much the following will get Claim. $n_\text{min}\le89+83$. Proof. Let $\{x_i\}=\{0,97,\dots,(89+83-1)\cdot97\}$. Observe that $p=97$ only if $f(x_i)$ is constant, which conversely precludes $p=2,\dots,89$ as $\{x_i\}$ covers $\mathbb{Z}/p\mathbb{Z}$ for each such $p$. Hence ignore $p=97$ and divide everything by $97$. Suppose FTSOC that $\{f(x_i)\}$ is compatible with distinct periods $p\neq q$, i.e., $f(x_i)=f(x_j)$ if $i\equiv j\pmod{p}$ or $i\equiv j~(q)$. Consider the graph on $0,\dots,p+q-1$ where values are connected if they differ by $p$ or $q$, and examine the cycle

$\square$ In fact, we can strengthen the bound to $89+83-1$, since we can remove one of the indices (say, the penultimate $q$) leaving a path that is still connected and still covers both $\mathbb{Z}/p\mathbb{Z}$ and $\mathbb{Z}/q\mathbb{Z}$. Claim. $n_\text{min}\ge89+83-1$.

$\square$ Hence, the answer is $\boxed{89+83-1=171}$.

@above I think you will get points for construction but not for the bound. The construction proof, while messy, does seem to contain the correct line of reasoning. However the bound proof's line of reasoning seems incorrect for two reasons. Let's call your $171$ vertex graph that does work $G$, and call the $<171$ vertex graph that you assume exists (in order to cause a contradiction) H. It appears that you assume you can remove/combine vertices in G to create H, but this is not always true. How do you know that there isn't some $<171$ vertex graph that isn't a subgraph of G that still works? Also, graph G is not a tree, it actually has a much more complicated structure to it. Therefore you need to do more digging to actually prove removing any vertex from it breaks the graph.

peace09 wrote: Would anyone be kind enough to predict how much the following will get