logical deduction - Two spies throwing stones into a river

There is a puzzle about two spies:

Two spies must pass each other two secret numbers (one number per spy), unnoticed by their enemies. They have agreed on a method for doing this using only 26 indistinguishable stones in advance.

They meet at a river, where there is a pile of 26 stones. Starting with the first spy, they take turns throwing a group of stones into the river: the first spy throws some number of stones, then the second one, then the first one again...

Each spy must throw at least one stone on his turn, until all the stones are gone.

They observe all throws and diverge when there are no more stones. They keep silence all the time and no information is exchanged except number of stones thrown at each turn.

How can they exchange the numbers successfully if the numbers can be from $1$ to $M$?

To understand the idea you can read the following simple solution for $M = 42$:

0. Let's call the spies spy 1 and spy 2. Spy 1 has number $N_1$ to tell Spy 2, and Spy 2 has number $N_2$ to tell spy 1.

1. The spies agree that each number $N$ from $1$ to $42$ shall be represented by a combination of two numbers $(m_1, m_2)$, where $1 \le m_1 \le 7$ and $1 \le m_2 \le 6$. Since there are exactly 42 possible combinations of $(m_1, m_2)$, it is possible for them to make this mapping.

2. At the river each spy calculates his pair of numbers $(m_1, m_2)$ that corresponds to the number he wants to send.

3. Spy 1 throws stones in the river corresponding to his $m_1$, then spy 2 throws stones corresponding to his own $m_1$, then spy 1 throws $m_2$ stones, then spy 2 throws $m_2$ stones.

4. Finally, spy 1 throws all the rest of the stones into the river if any left.

This solution works because neither spy throws more than 13 stones, so they can never throw more than 26 in total.

I know the algorithm for $M = 1716$. I know that an algorithm for $M = 2286$ exists, but I do not know what it is. I wrote a program that seems to prove that it is impossible to do if $M > 2535$.

I would like to know, what is the algorithm for $M = 2286$? Is it possible to formulate an algorithm for $M > 2286$?

---

Please note that people who attempt to solve this puzzle keep making the same mistakes:

1. 
   

   People forget that due to the alternation rule, if spy 1 needs to make $K$ throws, then spy 2 can make only $K-1$ or $K$ throws.

   
   


2. 
   
   

   People do not take into account that spies must agree on everything in advance. Therefore it doesn't matter for the second spy how big the first spy's number is, and how many stones he actually needs to transmit this information; each spy's algorithm must work for any possible number (from $1$ to $M$), that the other spy can want to tell him.

   
   

Answer

I think that the answer lies in inductive construction of the decision tree. At each step there are $k$ stones remaining, and the current player has to throw somewhere from $1$ to $k$ stones. The full tree $D_k$ for a situation with an initial $k$ stones is thus built up with $D_k$ having $k$ children, one instance each of $D_i$ for $i$ from $0$ to $k-1$: e.g. $D_3$ is

where the label on each edge is the number of stones thrown and every path ends with no stones remaining.

However, the spies must have pre-agreed an assignment of values to the leaves of this tree in such a way that the result is decodable: i.e. that given their place on the tree, each spy knows what possible outputs there are, and can communicate his number regardless of his partner's number. For simplicity, we assume that they prune all branches which have no values assigned to their descendants.

I believe that we can construct all such decodable decision trees from a simple principle: the children of the current node must all be decodable in order for the current node to be decodable. Then we can build up the decodable trees starting with $D_0$. I'm going to use the notation $T_k$ to denote the set of decodable trees with $k$ stones, and I'm going to represent each such tree as the thing which we really care about: $(x, y) \in T_k$ means there is a decodable tree with $k$ stones which allows the player who goes next to say one of $x$ numbers, and the other player to say one of $y$ numbers.

The base case is obviously $$T_0 = \{ (1, 1) \}$$ because neither player can do anything to distinguish between numbers. The recursive construction is $$T_k = \left\{ \left(\sum_{s \in S} \mathrm{snd}(s), \min_{s \in S} \mathrm{fst}(s) \right) \middle| S \in \prod_{i

When $k>1$ we can make a small transformation for ease of computation: $$\begin{eqnarray}\prod_{i

We can also simplify the bookkeeping by removing dominated pairs: if one pair is strictly worse than another, we forget about it. Denote the simplified sets as $T'_k$.

So we get $$\begin{eqnarray}T'_0 &=& \{ (1, 1) \}\\ T'_1 &=& \{ (1, 1) \}\\ T'_2 &=& \{ (2, 1) \}\\ T'_3 &=& \{ (3, 1), (1, 2) \}\\ T'_4 &=& \{ (5, 1), (2, 2), (1, 3) \}\\ T'_5 &=& \{ (8, 1), (4, 2), (2, 3), (1, 5) \}\\ T'_6 &=& \{ (13, 1), (7, 2), (4, 3), (3, 4), (2, 5), (1, 8) \}\\ \vdots \\ &&(1782, 1782) \in T'_{25}\\ &&(2535, 2536) \in T'_{26} \end{eqnarray}$$

So the solution is $$M=2535$$