Arithmetic hide-and-seek: solution
Here is my solution for the problem of arithmetic hide and seek. Please read it if you prefer to solve the problem by yourself.
Many users on G+ (comments thread) and in the comments has correctly solved it and additional questions. The first ones were Suhail Sherif, Brent Werness and Heffalump Horton. Hope that the problem entertained you.
Solution
First note, that if Angel knows the formula, then he can win instantly, whatever the current turn number \(k\) is. To do this, just substitute \(k\) to the formula and obtain exactly, where Demon hides. Indeed, Angel does not know the formula. However, it is not a problem, since the set of possible formulas is countably infinite. This means that it is possible to build an infinite sequence of formulas that contain every possible formulas (moreover, this can be done explicitly, see below). Angel can use this sequence to check formulas one-by-one, on each turn substituting current turn number to \(k\) and checking for Demon. Sooner or later, Angel will try the formula, Demon has conceived and win the game (though he can win earlier, by pure luck). This gives the winning strategy.
Explicit solution
The above solution could be enough for a mathematician, but as a programmer, I wanted to write down the explicit algorithm. To do this, first the sequence of all formulas should be built. It can be done in a multitude of ways, some of them are more computationally effective (faster and contain less duplicates) than others. For the proof-of-concept code, I used the simplest approach.
Using the usual linear notation, every allowed formula can be written as a string, composed of characters “0123456789+-*/^()k” (where ^ stands for powering). It is easy to enumerate all possible strings. A simple way is shortlex order: first all strings of 1 character, then of 2 characters in alphabetic order and so on. By excluding non-valid expressions, one gets a sequence of all possible formulas, from the shortest ones to the longest.
I implemented this enumeration algorithm in Python. To check whether the string is a valid formula it uses a simple parser, written with pyparsing library. To reduce numbers of duplicates (equivalent formulas), it disallows numbers starting with 0, except for the 0 itself.
The implementation is not breathtakingly fast, but fast enough to enumerate expressions up to 5 characters in a reasonable time.
Source code is on Github: dmishin/arithmetic-hide-and-seek.
Here are few first formulas and corresponding search attempts done by Angel.
Turn k Formula f Value f(k)
1 0 0 2 1 1 3 2 2 … … … 10 9 9 11 k 11 12 10 10 … … … 101 99 99 102 -0 0 … … … 476 29 512 477 2k 3'902'185'687'894'990'289'226'996'537'241'457'882'185'747 … … … 1729 kk 1.40457…×105598
The sequence of attempts behaves erratically, but its amplitude grows very fast. At the step \(k=320282\), the formula \(k^{k^k}\) is reached, which evaluates to tremendous \(320282^{320282^{320282}} \approx 10^{10^{1763323.7111}} \), a number that is so big that to write down even the number of digits in it one needs 1'763'324 digits.
This sequence is shown on the graph below. The graph uses logarithmic vertical scale because of the fast growth rate. Positive values are show in red, and negative in blue. Note that not all actual data points are shown, some values are so large, that even in the logarithmic coordinates the rest of the graph will be too small.
Growth rate
How fast the amplitude of Angel's search grows? Quite fast, actually. Even the logarithmic plots above do not properly reflect it, since the highest data points are not shown on them.
For the proposed implementation, growth rate is easy to estimate. Quite obviously, when \(k\) is large enough, the biggest possible values have form k^k^…^k. Since the percent of valid formulas remains roughly constant at about 20% (a rather curious fact, actually. Is it true, and what is the limit value? I don't know UPD: Actually, it is not true, but number of formulas nevertheless grows exponentially), the length of the string grows approximately as logarithm of the turn number: \(L ~ \log k\). Therefore, maximum value grows as k^k^k^… (log k times). This can be written as: \(^{\log k}k\) (see tetration) or, with Knuth's up-arrow notation, as \(k\uparrow\uparrow\log k\).
Growth rate, however, depends on the enumeration method chosen. By rearranging formulas, it is always possible to make growth faster.
It is also possible to decrease growth rate. For example, it can be done by “diluting” sequence with growing sequences of zeros. However, there is a lower limit: the growth rate should be strictly faster than of any fixed height power tower: \(k^{k^{k^\ldots}} = k\uparrow\uparrow n\).
Extensions
Here are few thoughts on possible extensions of the problem, with a result that I was not aware of.
Extension first: more operators
It can be easily seen that the set of allowed operators is rather arbitrary. It can be expanded with arbitrary number of additional operators, functions or constants like \(\pi\).
Extension second: Turing machine
But what if instead of a formula, Demon uses a Turing machine: an ideal computer, capable to implement any algorithm. This change the game.
At first, it may seem that nothing has changed significantly. The set of all programs is countable and enumerable, but there is one obstacle … It can be formulated as a theorem:
Theorem 1: weaker Demon
If a winning strategy for the Angel exists, and Demon's computation method is expressive enough (see below), then Angel's search sequence is not expressible by Demon.Here expressive enough means that for every expressible formula \(f(k)\), there is another expressible formula \(f_1(k)\), such that \(f_1(k) \ne f(k) \forall k\). For example, \(f_1(k)=f(k)+1\). The rules from the original problem are, indeed, expressible enough in this sense.
The proof is by contradiction:suppose that Angel's sequence (winning strategy) \(A(k)\) can be implemented by Demon. Then he can implement sequence \(A(k)+1\), which is always 1 step before Angel. Then Angel can't win. Contradiction.
Theorem 2: slower Demon
The above theorem is a corollary of another theorem:
Growth rate of Angel's search sequence is strictly faster than growth rate of any sequence that Demon can compute.This theorem can also be proven by contradiction.
So, back to the Turing machines. Now it is clear that if Demon uses an algorithm instead of formula, then Angel's sequence can't be calculated by an algorithm: it is uncomputable. This does not means that the winning strategy does not exist: we just can't write an algorithm that produces it.
However, if Angel (with some divine help maybe) can obtain a Turing oracle - an entity that can determine, whether any given Turing machine hangs or terminates, then the situation changes. Using the oracle, Angel can win with the following algorithm:
k := 1
for each algorithm A:
if oracle says that A(k) terminates, then:
search Demon at point A(k)
k := k + 1
Since oracle can not be implemented algorithmically, Demon can't go a step before angel and can't escape.
Go deeper
So what if we go further, and give oracle to Demon?
Now Angel can't catch him for sure even with the help of an oracle. Since the set of all oracle-enabled algorithms is also enumerable, it essentially proves that Turing oracle is not enough to solve termination problem of an algorithm with oracle!
Thus, winning strategy, while existing in some sense, can not be computer neither by an algorithm nor by an algorithm with oracle. To catch Demon, Angel needs something more powerful: a second order oracle.
This race or arms can be extended indefinitely, defining an infinite hierarchy of oracles.
Comments