A sequence $x_1, x_2, ..., x_n, ...$ consists of an initial block of $p$ positive distinct integers that then repeat periodically. This means that $\{x_1, x_2, \dots, x_p\}$ are $p$ distinct positive integers and $x_{n+p}=x_n$ for every positive integer $n$. The terms of the sequence are not known and the goal is to find the period $p$. To do this, at each move it possible to reveal the value of a term of the sequence at your choice. (a) Knowing that $1 \le p \le 10$, find the least $n$ such that there is a strategy which allows to find $p$ revealing at most $n$ terms of the sequence. (b) Knowing that $p$ is one of the first $k$ prime numbers, find for which values of $k$ there exist a strategy that allows to find $p$ revealing at most $5$ terms of the sequence.
Problem
Source: ITAMO 2021 Problem 6
Tags: number theory, prime numbers
10.03.2022 14:06
(a) If $n \le 3$, then there are at most $B_3 = 5$ ways to partition a set of $n$ elements (where $B_n$ is the $n$-th Bell number), so one can only get at most $5 < 10$ distinct possible scenarios in any strategy. This is because each partition of a set with $n$ elements corresponds with a possible scenario when $n$ terms $x_{a_1}, x_{a_2}, \dots, x_{a_n}$ of the sequence are revealed; for example, $\{1, 2, 3, 4, 5\}$ can be partitioned into $\{\{1, 2, 3\}, \{4\}, \{5\}\}$, which corresponds to $x_{a_1} = x_{a_2} = x_{a_3}$ and $x_{a_1} \ne x_{a_4} \ne x_{a_5} \ne x_{a_1}$. Thus, $n \ge 4$. For $n = 4$, then one can ask for the values of $x_1, x_5, x_{11}, x_{46}$. Note that $x_i = x_j$ for positive integers $i < j$ if and only if $p | j - i$ since the $p$ repeated terms in the sequence are distinct. The following strategy works: If $x_1 = x_5 = x_{11} = x_{46}$, then $p = 1$. If $x_1 = x_5 = x_{11}$ and $x_{46} \ne x_1$, then $p = 2$. If $x_1 = x_{46}$, $x_{5} = x_{11}$, and $x_1 \ne x_5$ then $p = 3$. If $x_1 = x_5$ and $x_1 \ne x_{11} \ne x_{46} \ne x_1$, then $p = 4$. If $x_1 = x_{11} = x_{46}$ and $x_1 \ne x_5$, then $p = 5$. If $x_5 = x_{11}$ and $x_1 \ne x_5 \ne x_{46} \ne x_1$, then $p = 6$. If $x_{11} = x_{46}$ and $x_1 \ne x_5 \ne x_11 \ne x_1$, then $p = 7$. If $x_1, x_5, x_{11}, x_{46}$ are distinct, then $p = 8$. If $x_1 = x_{46}$ and $x_1 \ne x_5 \ne x_{11} \ne x_1$, then $p = 9$. If $x_1 = x_{11}$ and $x_1 \ne x_5 \ne x_{46} \ne x_1$, then $p = 10$. Thus, the least $n$ for which there exists a strategy is $\boxed{4}$. (b) We claim that there exists a strategy if and only if $\boxed{k \le B_5 = 52}$. If $k \ge 53$, then by only asking at most $5$ questions, one can only get at most $B_5 = 52$ distinct possible scenarios, which is not enough to distinguish all $k$ possible periods. If $k \le 52$, we will show there exists a strategy. Similar to (a), we will attempt to create a one-to-one correspondence between the $52$ partitions of $S = \{1, 2, 3, 4, 5\}$ and the distinct possible scenarios when revealing $5$ terms $x_{a_1}, x_{a_2}, x_{a_3}, x_{a_4}, x_{a_5}$ of the sequence, where $x_{a_m} = x_{a_n}$ if and only if $m$ and $n$ are in the same subset for a unique partition of $S$. Let $p_1 < p_2 <\dots< p_{52}$ be the first $52$ prime numbers, and let $P = p_1p_2\dots p_{52}$. So the period of the sequence is $p_t$ for some $1 \le t \le 52$. We number the partitions of $S$ from $1$ to $52$, with Partition $1$ being $\{\{1,2,3,4,5\}\}$ and Partition $2$ being $\{\{1\}, \{2,3,4,5\}\}$. The rest of the partitions can be numbered from $3$ to $53$ in any way. Define the function $f_i: S \to S$ such that for each $x \in S$, $f_i(x)$ is the smallest element of $S$ in the same subset as $x$ in Partition $i$ ($f_i(x)$ can be equal to $x$). Note that $f_1(x) = 1$ for all $x \in S$, $f_2(1) = 1$, and $f_2(x) = 2$ for all $x \in \{2,3,4,5\}$. Since $p_3 = 5$, we have $1 \le f_i(x) \le p_i$ for all $x \in S$ and $1 \le i \le 52$. Let $a_n = \sum_{i = 1}^{52} f_i(n) \frac{P}{p_i}$ for $n = 1,2,3,4,5$. Once again, $x_{a_m} = x_{a_n}$ if and only if $p_t | a_n - a_m$. Since $p_t | \frac{P}{p_i}$ for all $i \ne t$ and $p_t \nmid \frac{P}{p_t}$, then $a_n \equiv f_t(n)\frac{P}{p_t} \pmod{p_t}$. Hence, $p_t | a_n - a_m$ if and only if $p_t | \frac{P}{p_t}(f_t(n) - f_t(m)) \iff p_t | f_t(n) - f_t(m)$. Since $1 \le f_t(m), f_t(n) \le p_t$, $p_t | f_t(n) - f_t(m)$ if and only if $f_t(n) = f_t(m)$, i.e. $m$ and $n$ are in the same subset in Partition $t$. Therefore, if $p_t$ is the period of the sequence for some $1 \le t \le 52$, then $x_{a_m} = x_{a_n}$ if and only if $m$ and $n$ are in the same subset in Partition $t$. This makes it possible for one to reveal $x_{a_1}, x_{a_2}, x_{a_3}, x_{a_4}, x_{a_5}$ determine which of them are equal and unequal, match the scenario to a partition of $S$, and find the value of $t$ uniquely. For $k < 52$, a similar strategy can be made. Thus, for all $k \le 52$, there exists a strategy to find the period $p$ of the sequence.