Stephen Mildenhall suggested the following puzzle. Create two sequences of strictly increasing positive integers, A(n) and B(n) with n = 1,2,…. These sequences must be such that any positive integer M is the sum M = A(i) + B(j) for at most one pair i,j. Note, however, not all M need to be such a sum. When A and B together have this property, they are called identifiable.
Here is a magic trick to illustrate how identifiable sequences might be used. You will give list A to Person A and list B to Person B and ask them each to randomly select one number. They confer and tell you only the sum. With identifiable sequences you can magically tell them which number each of them chose.
One pair of identifiable sequences is A(1) = 1, B(n) = 2 A(n), A(n + 1) = 2 B(n). Some example unique sums from these sequences are: 3 = 1 + 2. 6 = 4 + 2. 9 = 1 + 8, 12 = 4 + 8, … But A and B grow very rapidly with n.
In contrast, the slow growing sequences A(n) = 2n and B(n) = 2n + 1 are not identifiable. For example, 7 = 2 + 5 = 4+ 3.
In general, we expect only a small proportion of all the positive integers can be formed as A(i) + B(i) when A and B are identifiable.
The challenge is to construct the slowest growing pair of identifiable sequences. Assume A(1) = 1 and B(1) = 2. What do you propose for a pair A(n) and B(n)? How do you compute them as efficiently as possible? Can you say anything about their growth rates as functions of n? Polynomial? Exponential? What is A(100)? A(200)? Extra credit: A(1000)? You may need a computer.
Know the answer? Send your solution to ar@casact.org.
- Beyond some point S is a constant sequence of only 0s or only 1s. Horatio wins because he can, for example, alternate between picking 0 and 1 forever.
- There is no point after which S is periodic (an endless repetition of a fixed sequence of finite length). Hypatia wins because, for example, she can pick alternating ever longer finite sequences of 0s and 1s (0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, …) with each finite sequence long enough to break any prior periodicity.
- S does not contain all possible finite binary sequences in it. Equivalently, at least one binary sequence of finite length is nowhere in S. Hypatia wins because, for example, she can pick all 0s.
- For a given set C of countably infinite binary sequences C = {S1, S2, …}, S ∊ C. That is to say S must be some element of C. Horatio wins because, for example, as every time he picks the 2n + 1 digit for S, he can pick the opposite of whatever the 2n + 1 digit is for Sn,
Solutions were also submitted by John Berglund, Bob Conger, Clive Keatinge, Eamonn Long, Dan Paine and R.S Pulis.
