Another user recently asked a question on the Puzzling stack: Two spies throwing stones into a river. Suitably generalised, it becomes:
Two spies (Alice and Bob) need to exchange a message. Each will encode their message as a number from $1$ to $M$ before they meet. They will then meet by the river and communicate secretly by throwing stones.
There will be a pile of $N$ indistinguishable stones at their meeting point. Starting with Alice, they take turns throwing some of the stones into the river: Alice throws some number of stones, then Bob, then Alice again...
Each spy must throw at least one stone on their turn, until all $N$ stones are gone.
They observe all throws and separate when there are no more stones. No information is exchanged except the number of stones thrown on each turn.
Given that $N$ is known in advance, what is the largest possible value of $M$?
There is a simple algorithm to compute the answer, and I'm working on a proof of correctness for a more subtle and efficient approach. However, I'm wondering about the history of this problem. The user who posted it on Puzzling.SE knows only that "the puzzle was proposed in Oct 2009 by user tatunya (currently inactive) on this russian puzzle site: http://braingames.ru/index.php?path=comments&puzzle=475". The version given there asks whether $M \ge 1700$ given $N=26$.
Does this puzzle have a name? Can anyone ante-date the posting on braingames.ru? Has any analysis of it been published?
