Two spies throwing stones into a river

Question

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 1

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<k} \left(T_i \cup \{(\infty, 0)\}\right) \right\} \setminus \{(0, \infty)\}$$ where the $(\infty, 0)$ option corresponds to pruning the branch where the current player would throw $i$ stones.

When $k>1$ we can make a small transformation for ease of computation: $$\begin{eqnarray}\prod_{i<k} \left(T_i \cup \{(\infty, 0)\}\right) &=& \left(T_{k-1} \cup \{(\infty, 0)\}\right) \times \prod_{i<k-1} \left(T_i \cup \{(\infty, 0)\}\right)\\ &=& \left(T_{k-1} \times \prod_{i<k-1} \left(T_i \cup \{(\infty, 0)\}\right)\right) \cup \\&& \left(\{(\infty, 0)\} \times \prod_{i<k-1} \left(T_i \cup \{(\infty, 0)\}\right)\right)\\ \end{eqnarray}$$ so $$\begin{eqnarray}T_k &=& \left\{ \left(\sum_{s \in S} \mathrm{snd}(s), \min_{s \in S} \mathrm{fst}(s) \right) \middle| S \in \left(T_{k-1} \times \prod_{i<k-1} \left(T_i \cup \{(\infty, 0)\}\right)\right) \right\} \cup \\&& \left\{ \left(\sum_{s \in S} \mathrm{snd}(s), \min_{s \in S} \mathrm{fst}(s) \right) \middle| S \in \prod_{i<k-1} \left(T_i \cup \{(\infty, 0)\}\right) \right\} \\ &=& \left\{ (x + y, \min(w, z)) \middle| (w, x) \in T_{k-1}, (y, z) \in T_{k-1} \cup \{(0, \infty)\} \right\} \cup T_{k-1} \\ &=& \left\{ (x, w) \middle| (w, x) \in T_{k-1} \right\} \cup \left\{ (x + y, \min(w, z)) \middle| (w, x) \in T_{k-1}, (y, z) \in T_{k-1} \right\} \cup T_{k-1} \\ \end{eqnarray}$$

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$$

Answer 2

This is another example of an information puzzle. You are trying to find the most numbers a pair of spies can send to each other given that there are 26 stones in the river.

Furthermore, the stones are all identical, and the only way the spies can communicate is by throwing a certain number of stones into the pond at the same time.

You are ultimately trying to devise an algorithm that can produce the most possible outcomes for this procedure of throwing 26 stones, which will them map to the greatest number of results.

---

The answer lies in the number of ways there are to divide 26 stones into groups.

Although the stones themselves are identical, the order that they're thrown in isn't. So the groups that the stones are thrown in form an ordered partition, like such:

o o o o|o o o|o o|o o o o o|o|o o|o o o|o o o o|o o

Each o represents a stone, and each | represents a divider between a group of stones that were thrown. In the example above, there were 4, 3, 2, 5, 1, 2, 3, 4, 2 stones thrown.

Now, notice that any two consecutive stones can have a divider between them or not. This is a total of 25 dividers that can either be present or not present, for a total of $2^{25} = 33~554~432$ outcomes. So our first upper bound on the numbers the spies could exchange is $\lfloor2^{12.5}\rfloor = 5792$.

Complicating this is the fact that each spy has to have some control over the stones they throw. If spy 1 throws all 26 stones (which is the case with no dividers), this leaves no choice in the matter for spy 2.

So, we decide instead to give each spy his own set of 13 stones, which again can either have dividers between them or not (which is a total of 12 positions where dividers can occur). In this case, the upper bound is $2^{12} = 4096$.

Complicating this yet again is that each spy has to throw either the same number of groups of stones, or the first spy throws one more group of stones than the second spy.

So, for each of the 13 stones, the spies need to decide on a way to divide them into groups of, say, 6 or 7. If each spy decides beforehand to divide the stones into exactly 7 groups to throw, this gives a total of $\binom{12}{6} = 924$ choices in where to put the dividers, which is our first solution that actually works.

---

From here, we have to work up. Note that this first naïve solution doesn't take advantage of the fact that the first spy can throw one more group of stones than the second, or that either spy can throw less than 13 stones. So there's some information that we've ended up discarding.

The hockey stick theorem states that any number $\displaystyle \binom{n}{k}$ is equal to $\displaystyle \sum_{m=0}^{k} \binom{n-1-m}{k-m}$ (the theorem gets its name from the way those numbers form a hockey stick on Pascal's Triangle). So supposing we instead arrange that spy 2 can throw anywhere from 7 to 13 stones in 7 groups depending on how many spy 1 throws, he can still get a total of $\binom{13}{6} = 1716$ combinations. The algorithm then becomes:

• Both spies determine which arrangement of stones to throw beforehand, with the restriction that they each throw exactly 7 groups of no more than 13 stones.

• They come to the river and alternate throwing groups of stones that correspond to their number.

• Spy 1 then throws all the remaining stones into the river, and they depart.

This allows them to exchange two numbers up to $1716$, which is the same number you got up to.

---

Now, we note that in some of the above cases, we have some stones left over that Spy 1 has to throw away. Could we put these to better use?

• In $\binom{11}{5} = 462$ cases, a spy will have 1 stone left.

• In $\binom{10}{4} = 210$ cases, a spy will have 2 stones left.

• In $\binom{9}{3} = 84$ cases, a spy will have 3 stones left, etc.

In each of these cases, the spy can throw any number from $1$ to $n$ stones, but Spy 2 cannot throw any stones if Spy 1 doesn't throw at least $1$ first, so we consider the worst-case scenario where Spy 1 has thrown all his stones but Spy 2 still has $n$ to throw.

Spy 1 throws a stone, leaving $n-1$ for Spy 2. Spy 2 then throws any number from $1$ to $n-1$ and Spy 1 throws the rest away. This algorithm will still work if there are any other number of stones left.

This doesn't really do anything in the case where there are only 1 or 2 stones left (in each of these cases, Spy 2 either has no stones to throw or must throw exactly 1 stone, which doesn't give any information). However, for 3 or more stones, we get the following improvements:

• For $s = 3$, we can express $2$ cases per arrangement, for an improvement of $\binom{9}{3} \times (2-1) = 84$ more cases.

• For $s = 4$, we can express $3$ cases per arrangement, for an improvement of $\binom{8}{2} \times (3-1) = 56$ more cases.

• For $s = 5$, we can express $4$ cases per arrangement, for an improvement of $\binom{7}{1} \times (4-1) = 21$ more cases.

• For $s = 6$, we can express $5$ cases per arrangement, for an improvement of $\binom{6}{0} \times (5-1) = 4$ more cases.

All together, we get $84 + 56 + 21 + 4 = 145$ extra cases from the extra stones, bringing the total up to $1861$.

---

I can't see any elegant improvements to make on this algorithm past that, though. If you were to make a computer program to traverse all the possibilities, I suppose you could get to $2286$, but it would probably require a whole different approach, potentially involving the same sequence of throws from one spy representing different numbers depending on how the other spy threw his stones.

Answer 3

This to add to Joe Z.'s answer, who achieved 1861. Hope this will help the other people to improve the answer.

Joe Z.'s idea with some tuning allows to achieve 1891. The idea, which makes it possible to proceed further is to choose between two algorithms basing on the first turn result. [Actually, this is a special case of more general idea, described in Peter Taylor's answer, what is good about below-described algorithm is that $M_{max}$ here can be found without help of computer.]

So, here is the algorithm for M = 2106:

1. Each spy gets 13 stones as his "property" stones (let's call them PS). That means a spy can count on these stones to use them how he likes without worries about what needs the other spy.

2. Each spy also gets some number ($T$) of mandatory turns (let's call them MT) to distribute his 13 stones between. $i$-th spy guarantees to throw 13 or less stones in $T_i$ turns.

3. Spy 1 decides how many mandatory throws each spy will get.

   • If spy 1 trows 1 stone at turn one then $T_1 = 7, T_2 = 6$.
   • If spy 1 trows 2 or more stones at turn one then $T_1 = 6, T_2 = 5$.

4. If some spy $i$ ($i$ = 1 or 2) has made $T_i$ turns but the other spy (spy $j$) needs more then one turn to finish, spy $j$ "leaves" one stone for the other spy to "burn": he (spy $j$) subtracts one stone from his PS.

5. If spy $i$ sees that the other spy must left for him one stone to "burn" spy $i$ must "burn" this stone no matter what: he throws one more stone than he planed.

6. Spies agree on enumeration of all posible combinations each of them can do by this algorithm in advance.

Let's calculate the combinations each spy can throw.

First lemma, what number of combinations a spy can do if he decides to throw $S$ stones in $T$ turns?

The possible map of throws looks like this:

`Ao|o|o|o|o|o|o o o o o o oB` 

The notation is o - a stone, and each | - a finish of a turn (can be at any plase between o's), A - start, spies just came to the river, B - finish, spies diverge, - a free position, where | can be put.

So we have $T-1$ | to put in $S-1$ position. The number of combinations will be $C = \binom{S-1}{T-1}$.

Second lemma, what number of combinations a spy can do if he decides to throw $S$ stones in $T$ or $T+1$ turns? It would be $C = \binom{S-1}{T-1} + \binom{S-1}{T} = \binom{S}{T}$.

Then the mini decision tree:

1. First spy:

   2. Decides that he needs $T_1 = 7, T_2 = 6$. Then his first turn has been finished, 12 PS and 6 MT of the other spy left. He can make 6 "free" turns.

      3. He can leave 0 stones for spy 2 to burn and throw 12 stones in 6 turns, which will give him $C = \binom{11}{5}$ combinations.
      4. He can leave 1 stone for spy 2 to burn and throw 11 stones in 6 or 7 turns, which will give him $C = \binom{11}{6}$ combinations.
      5. ... [full analogy].
      6. In total $C = \binom{11}{5} + \binom{11}{6} + \binom{10}{7} + \binom{9}{8} = 1053$.

   3. Decides that he needs $T_1 = 6, T_2 = 5$. Then his first turn is not finished, 12 PS and 5 MT of the other spy left. He can make 6 "free" turns.

      3. ... [exactly the same as the previous case]
      4. In total $C = 1053$.
   4. In total $C = 1053 + 1053 = 2106$.

2. Second spy:

   2. $T_1 = 7, T_2 = 6$. He has 13 PS and 6 MT of the other spy left.

      3. He can leave 0 stones for spy 1 to burn and throw 13 stones in 6 or 7 turns, which will give him $C = \binom{13}{7}$ combinations.
      4. He can leave 0 stones for spy 1 to burn and throw 12 stones in 7 or 8 turns, which will give him $C = \binom{12}{8}$ combinations.
      5. ... [full analogy].
      6. In total $C = \binom{13}{7} + \binom{12}{8} + \binom{11}{9} + \binom{10}{10} = 2267 $.

   3. $T_1 = 6, T_2 = 5$. He has 13 PS and 5 MT of the other spy left.

      3. ... [full analogy with the previous case].
      4. In total $C = \binom{13}{6} + \binom{12}{7} + \binom{11}{8} + \binom{10}{9} = 2683 $.

   4. In total $C = min(2267, 2683) = 2267$. (This spy can't choose the case).

3. In totals both spies can do $C = min(2106, 2267) = 2106$.

Answer 4

So lets see how much information can be exchanged, my highest is m = 715 or 1430 for both spies.

Lets look at the restraints.

1) The number of stones is the only information that may be collected.

2) The two spies must take turns , they must therefore take the same number of turns

3) The number of stones is limited , 26

4) The spies may not limit the throws of the other player (each has 13 stones)

5) They may not throw 0 stones

Implied Rules

6) Each player may not know anything about the other players numbers. Nor may they know anything about the numbers during their meetings.

7) One spies number may not interfere with the other spies number. Scenario where one spy finishes early or uses the other players left over stones cannot occur.

This means that there are at most six turns of throwing stones. On a given turn a player may throw a stone or more. The number of throws cannot be available since they must stop at the same time sop they must have their information in the same space of turns. They must know how many turns are being exchanged so they can terminate at the same time.

Simply using the dividers between the 13 stones from above as a binary word is a good idea. This will allow numbers up to 2^12 to be represented. By considering the division of a group as a binary signal, and the lack of a divider as the off positions you get a 12 bit word. This does not rely on extra information being passed, just translates the gaps into a binary word. to ensure the alternation of turns the binary word will be 6 bits long of binary data ( 1 stone = 0, 2 stone = 1). This gives us 2^6 options. I know above it seems great to have 2^12 from a grouping of 13 stones. However by stating that you have dived them into 6-7 groups ( 7 is impossible) you have created six bits, not 12. You are counting the number of ways to group the data, and yet you just said the there are only 6-7 groups. 64 for each spy, sadly a 7th digit cannot be included due to only having one stone and not being able to assume the number isn't 64. With only one stone that bit will never actually contain data since there is only one choice. Using the separators to binary encode is a good idea, but needs the numbers of throws to be variable, which does not work. This is due to having to terminate the word at agreed number of symbols. so . . m = 64

The information allowed is the number of stones. However the turn limitation forces us to allocate enough stones to allow for full transimition. So we are looking for unique signals sent by groups of numbers, limited to 13 stones. Each grouping is a symbol to be transmitted. Sending 6 groups using 12 stones make no logical sense. So instead of loosing that last stone it should be used for a trinary signal in that grouping.

However if the Alternation of throws is enforced very strictly . . . meaning they MUST take turns, the problem becomes very abbreviated. Even the tree above which i find as wonderful mechanic should be constructed so that the tree is balanced, for example that each player reaches the end of their tree with the same number of turns. Logically the forces them to used a set number of agreed groups and leave left over stones. If each player has 13 stones then they can do 6 binary, 4 trinary, or 3 quadrany choices.
If each leaf has N choices there can be N / K rounds of signals sent. if the signals are 1 stone /two stone there are six signals and a tree of 2^6 in size. if there are three signals (1 stone, 2 stone, 3 stone) you have a tree of 3^4 in size. This is due to the nodes not being able to contain a value, only the end of the path does. How can a spy terminate early? the signals must all be sent otherwise we need a new signal to indicate the end. so using a look up tree might not be as efficient here as we hoped due to the limited information.

tightly enforcing this constraint pushes out many possible scenarios. it seems that four trinary signals would carry the most information in this scenario. four blocks of trinary data sent by both spy would allow for 81 different signals without compromising the information sharing rules, the turn alternation rules, or the rock sharing rules. However we can use the last stone and add one more choice. This nets us 3 X 3 X 3 X 4 = 108 choices.

Now to use the leftover stones we can simply make the later choices in the tree to include the possibility of the leftover stones being left. There are many cases where the leftover stones could be used in the final 'word'. In fact we get a larger pool of results by limiting the later throws. 10 choices, 1 choice, 1 choice, 1 choice performs better than 3 , 3, 3, 4 in this case due tot he carry over stones. This yields many extra leaves on out decision tree. I will try to get a mathematical expression for this calculation, I wrote a program to test it and found 715 as the optimum choice.

Now the case where the number of turns are decided by the first players move does not work for two reasons. This simply makes the first choice a binary choice and uses extra stones. Furthermore, if the first player need to use the extra set and indicates this, what does the second player do if their answer is in a tree with a different number of moves? Trees in this case must be balanced ( have the same number of nodes to all leaves).

Both the binary tree above and the binary combinations above count far too many scenarios where the information exchange does not work. The look up table is irrelevant, the total numbers of signals is the relevant answer. Both players will have a look up tree that must be identical. But the tree must be balanced or else one player will end on tier two while the other pushes to the last leaf of the deepest branch. Test your scenario with the highest value/ lowest value pairs, and then with a highest /highest value to test the transmition.

Answer 5

Thinking of a simpler and more practical solution that is focusing on the first part of the question:

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

and not worrying about the algorithm portion of the question as this is puzzling and not math stack exchange after all. I can come up with a simple solution that allows for 9,999 numbers for each spy. Other posters seem to think a restraint is:

The number of stones is the only information that may be collected.

I did not see that as part of the question. So we can also use the location the stone lands as an indicator of its value. Also assume each spy will take two turns each. For example if it is on the right of the spy it's 1 in front of the spy 2, left of the spy 5, Far away on the right 10, far away in middle 30, far away on the right 50.

Turn one is for the tens and ones

Turn two for thousands and hundreds

I guess you could go limitless if you wanted to also include height of stone, way it was thrown, number of times it bounded on the water. I simply thought it would be nice to have a non mathematical solution to show an alternate easyer to understand way to solve the problem that allows for higher numbers.