, 2023

The answer is $N = 10$, where 「」 denotes the ceiling function. In general, if the given IDs must not exceed $M$, then the smallest $N = \lceil \log_2 M \rceil - 1$.

Construction: Label the two squids $1$ and $2$, with their given IDs being $D_1$ and $D_2$ respectively. When $M \le 2^{N+1}$, the IDs can be represented as
$$D_i = p_{i,1} 2^N + p_{i,2} 2^{N-1} + \dots + p_{i,N} 2^1 + 1 = 1 + \sum_{j=1}^{N} p_{i,j} 2^{N+1-j},$$
where $p_{i,j} \in \{0,1\}$. For convenience, let $p_{i,j}$ denote the value of $p_{i,j}$ for the squid whose turn it is on turn $i$, that is,
$$p_{i,j} = \begin{cases} p_{1,j} & i \equiv 1 \pmod{2} \\ p_{2,j} & i \equiv 0 \pmod{2} \end{cases}$$
Similarly define $D_i$ as the ID of the squid whose turn it is on turn $i$.

Let $k_0 = 0$, and consider the following strategy: if on turn $i$ the squid cannot yet determine which ID is larger, have it compute
$$k_i = \min\{k : p_{i,k} = 1, k > k_{i-1}\}.$$
and have it announce $k_i - k_{i-1}$. It is easy to see that the sum of the numbers announced up through turn $i$ is $k_i \le N$. Furthermore, since $k_i$ is strictly increasing, it must be that after finitely many turns $\{k : p_{i,k} = 1, k > k_{i-1}\} = \emptyset$; we need only show that the squids will correctly determine which ID is larger before this situation occurs. To this end, let us define the sets
$$S(k) := \begin{cases} \{(D_1, D_2) : 1 \le D_1, D_2 \le M\} & k = 0 \\ \{(D_1, D_2) : p_{1,1} = p_{2,1}, \dots, p_{1,k} = p_{2,k}\} & k \ge 1 \end{cases}$$

First, we prove by mathematical induction that: at the end of turn $i$, either "the squids know $(D_1, D_2) \in S(k_{i-1})$" or "one of the squids can determine which ID is larger." The case $i=1$ is obvious. Suppose the claim holds for $i$; then on turn $i+1$:
(a) since no determination was made on the previous turn, by the induction hypothesis the squids know $(D_1, D_2) \in S(k_{i-1})$;
(b) since $k_i - k_{i-1}$ was announced on the previous turn, by the definition of $k_i$, the squids know $p_{i,k_{i-1}+1} = \cdots = p_{i,k_{i}-1} = 0$ and $p_{i,k_i} = 1$.

At this point there are several cases:
- There exists $k_{i-1} < \ell < k_i$ such that $p_{i+1,\ell} = 1$; then using (a) and (b) we may derive the following relation and determine which is larger:
$$D_{i+1} \ge 1 + \sum_{j=1}^{k_{i-1}} p_{i+1,j} 2^{N+1-j} + 2^{N+1-\ell} > 1 + \sum_{j=1}^{k_{i-1}} p_{i,j} 2^{N+1-j} + \sum_{j=\ell+1}^{N} 2^{N+1-j} \ge D_i$$
- If not, and $p_{i+1,k_i} = 0$, then the squids can use (a) and (b) to derive the following relation and determine which is larger:
$$D_{i+1} \le 1 + \sum_{j=1}^{k_{i-1}} p_{i+1,j} 2^{N+1-j} + \sum_{j=\ell+1}^{N} 2^{N+1-j} < 1 + \sum_{j=1}^{k_{i-1}} p_{i+1,j} 2^{N+1-j} + 2^{N+1-\ell} \le D_i$$
- If neither of the above holds, then $p_{1,j} = p_{2,j}$ for all $k_{i-1} < j \le k_i$, so we know $(D_1, D_2) \in S(k_i)$.

* If $p_{i+1,j} = 0$ for all $j > k_i$, then based on $(D_1, D_2) \in S(k_i)$ and the uniqueness of the IDs, the squids can deduce the following relation and thereby determine which is larger:
$$D_{i+1} = 1 + \sum_{j=1}^{k_i} p_{i+1,j} 2^{N+1-j} \le 1 + \sum_{j=1}^{k_i} p_{i,j} 2^{N+1-j} + 2 \le D_i$$
* If not, then $\{k : p_{i,k} = 1, k > k_{i-1}\}$ is nonempty, so the squids can successfully compute $k_{i+1}$.

Lower bound: We need only show that when $M = 2^k + 1$, it is impossible to guarantee a win while announcing numbers summing to less than $k$.

Let us proceed by mathematical induction on $k$. The case $k=1$ is obvious. Suppose the claim holds for all $k < K$. Note that the first squid can only declare which is larger directly on the first turn when $D_1 = 1$ or $D_1 = M$. Aside from these two cases, for $i=1,2,\dots,K-1$, suppose the first squid announces $i$ when $D_1 \in A_i$; then there must exist some $i$ such that $|A_i| \ge 2^{K-i} + 1$, otherwise
$$2^K - 1 = |\{2,3,\dots,M-1\}| = \left| \bigcup_{i=1}^{K-1} A_i \right| \le 2^{K-1} + 2^{K-2} + \dots + 2^1 < 2^K - 1$$
which is a contradiction. This means that after the first turn ends, there are at least $2^{K-i} + 1$ possible values of $D_1$, and all $2^{K-i} + 1$ of these could also be possible values of $D_2$. Thus, starting from the second turn onward, the game can be viewed as one with at least $2^{K-i} + 1$ possible ID values, but where the sum of the numbers announced must be less than $K-i$ (since $i$ has already been announced on the first turn); by the induction hypothesis, a win cannot be guaranteed in this case. This completes the proof.