Unsolvable


mar-de-plata1

Why go swimming, if you can do math instead inside a room with no windows?

Back in 1997, during my visit to beautiful Mar del Plata in Argentina, I was asked to solve a math problem that I soon realized was close to being unsolvable. The setting was the Banquet for the 38th International Math Olympiad. I was 17 and there was delicious, free food in front of me, so it was pretty impossible to get my attention. Still, the coach of the Romanian team decided to drop by the Greek table to challenge us with the following problem:

Infinite Power: If x^{x^{x^{x^{\dots }}}} = 2, find x.

I was pretty hungry and a bit annoyed at the interruption (it is rude to eat and do math at the same time!), so I looked at the problem for a moment and then challenged him back with this one:

Infiniter Power: If x^{x^{x^{x^{\dots }}}} = 4, find x.

After a few moments, he looked at me with a puzzled look. He knew I had solved his problem within a few seconds, he was annoyed that I had somehow done it in my head and he was even more annoyed that I had challenged him back with a problem that confounded him.

Your mission, if you choose to accept it, is to figure out why the coach of the Romanian IMO team left our table alone for the rest of the competition.

Good luck!

PS: The rest of the Romanian team (the kids) were really cool. In fact, a few years later, I would hang out with a bunch of them at MIT’s Department of Mathematics, or as my older brother put it, The Asylum.

26 thoughts on “Unsolvable

  1. Interesting. It seems that, given {{x^x}^x}^x… = 2, we obtain x^2 = 2, from which we deduce that x = \pm\sqrt{2}. However, by the same reasoning, we could arrive at the conclusion that the soluton for {{x^x}^x}^x… = 4 is x = \qm\sqrt{2}, and therefore we end up with a contradiction.

      • *****************SPOILER*****************

        Sqrt[2]^Sqrt[2] = {2^(1/2)}^Sqrt[2] = 2^(Sqrt[2]/2) = 2^(1/Sqrt[2])

        So Sqrt[2]^Sqrt[2]^Sqrt[2] = {2^(1/Sqrt[2])}^Sqrt[2] = 2^1 = 2.

        Notice x^Sqrt[2] > x for x>1. In particular, 2^Sqrt[2] > 2. So x such that x^x^x^… = 2 doesn’t actually exist, because if it did, it would have to be Sqrt[2] and it isn’t.

        That Romanian was a jerk and your response was awesome :-)

  2. First of all, I think that by general conventions, x^{x^x} \equiv x^{(x^x)}, not (x^x)^x which (the latter) could be written as x^{x\cdot x} = x^{x^2}. So let me follow the general conventions about the meaning of the composite powers.

    If the sequence of convoluted powers y=x^{x^{x\dots}} converges to 2 or 4 respectively, it must be that x^y=2 or 4 respectively. We may substitute 2 or 4 for y here to get x^2=2 or x^4=4, respectively. Both conditions are solved by x=\sqrt{2}, at least when we stay within real non-negative numbers that have a unique enough result for x^x.

    So x=\sqrt{2} is a necessary condition for x to be a solution to both problems. We must now verify whether it is a sufficient condition for either problem. One may numerically calculate a dozen of steps to be sure that the composite power converges to 2 but not 4. One may easily prove the inequality that if y\lt 2, then still (\sqrt{2})^y\lt 2, so one can’t get above two. It can’t ever get above two, i.e. towards four.

    That’s why the problem with 2 has the solution of $\sqrt{2}$ while the problem with 4 has no solutions.

    The final answer? I think that the Romanian coach decided to avoid the Greek table because the Greek contestants already ate the free food (as your description of your eating habits also suggests) and meat and he had to choose other tables where there was some free food left to take, something they don’t have in Romania. ;-) Another, less important problem is that he or she didn’t quite understand the logic, the difference between sufficient and necessary conditions, and the possibility that some problems have no solutions.

    • The LaTeX here doesn’t recognize backslash-lt and gt for “less than and greater than”. The missing sentence says

      … if y\leq 2, then (\sqrt{2})^y \leq  2, too.

      Fortunately, the claim works with sharp as well as non-sharp inequalities. The proof of the implication above is simple: (\sqrt{2})^y is an increasing function of y and for y=2, the power just happens to give exactly 2, so for lower bases, it gives less than 2.

        • the largest number is exp(1)
          this can be shown as follows: let us consider the increasing sequence y_{k+1}=x^(y_k) , and with x the solution of x=y_{inf}^(1/y_{inf}). Obviously, y_k/y_inf is converging quikly to 1, so z_k=1-y_k/y_inf is getting very small for large k. We can then take the log of both sides of the recursion, and expand in first order in z_k (as those quantities are very small) and get
          z_{k+1}/z_{k} = log y_{inf}. A necessary condition for convergence is therefore log(y_inf)<=1. It can easily be checked that the boundary case exp(1) still converges.

          • Cool, just to be sure, I manually numerically verified Frank’s result. The maximum x for which the infinite-composite-power converges is 1.44466786 or so, and indeed, the power is then 2.718\dots or so. The number 1.44466786 may be seen to be nothing else than \exp(1/e).

            • It would be interesting to see how fast x=1.44467 would surpass 1000 (ie after how many powers?) I wonder if there is a simple way to figure this out without calculators.

            • Dear Spiros, for your “overshot” constant, it’s about 2,212 steps. One exceeds 1,000 only about 20 iterations after the composite power exceeds 3. Almost exactly in one-half of the interations, after 1,100 steps or so, the composite power surpasses e=2.71828.

              If you only want orders of magnitude estimates, this behavior is probably describable theoretically, following methods by Frank etc. One may study the increase of composite power by adding one more step “x to something” to the chain. It slowly decreases roughly to 0.000011 for your starting number – the minimum increment is achieved after approximately 1,100 steps (in the middle of the near-divergent series). One could probably interpolate the increment as a quadratic function of (i-1100), with the coefficients calculable without a calculator.

              At the end, it’s still a difficult problem although the dependence on “i”, the iteration level, is pretty much gradual, as if “i” were another continuous variable, so I will give up attempts to solve it fully.

  3. If you differentiate x^{y}=y
    Then you get \frac{dy}{dx}=\frac{x^{2y}}{x(1-\ln{y})}
    This derivative is positive if y \epsilon (0,e)
    Based on what Frank and Lubos said previously, I don’t think the equation x^{y}=y makes any sense if y is outside this interval.

  4. Pingback: 2 ίσον 4 at physics4me

  5. If Exp[1] is the interval of convergence, what’s the radius of convergence … i.e. z^z^z^z^z…= h where both z and h are complex?

    • Let us first define what we mean by the equation x=y^(1/y) or equivalently y.log(x)=log(y); using the convention log(a)=log(|a|exp(i\theta_a))=log|a|+i\theta_a with -pi<theta_a<pi, we get the linear set of equations (written as a 2×2 matrix)

      [|x| ] = [cos(\theta_\inf) , sin(\theta_inf) ] [log|y_inf| /|y_inf| ]
      [\theta_x] [-sin(\theta_inf) , cos(\theta_inf)] [ \theta_inf / |y_inf|]

      Just like in the real case, we now set up a recursion y_{k+1}=x^{y_k} using the same rules; defining |y_k|/|y_inf|=1+z_k,
      theta_k=\theta_\inf+\xi_k, we get, up to first order in z_k and xi_k,

      [z_{k+1} ] = [log(|y_inf|) -\theta_inf] [z_k]
      [xi_{k+1}] [\theta_inf log(|y_inf|)] [xi_k]

      given that x obeys the above set of equations (this is how this consistency condition was derived).
      These real recursion equations converge iff the eigenvalues of the corresponding 2×2 matrix are smaller than 1, which is equivalent to the condition (with y_inf = y )

      |log(y_inf)|<1

      or equivalently

      sqrt(log|y|^2+\theta_y^2) <1

      which indeed reduces to y<exp(1) for the real case. Note that we use the convention that -pi<=\theta<=pi, which is also the convention that e.g. matlab is using. So if |log(y)|<=1, calculate x using the above set of equations, and do the recursion y_{k+1}=x^{y_k} for an arbitrary starting point y_0, then the recursion y_k should converge to y_inf.

      • Just for the record, |x| has to be replaced by log(|x|) in the above formula.
        The “boundary” points of the set for which the function y=x^x^x^… is well defined can now easily be seen to be parameterized by one angle -pi<chi<pi :

        y=exp(exp(i*chi))

        and corresponding

        x=exp(exp(i*chi-exp(i*chi)))

        This expression for x hence determines "the radius of convergence" for the function f(x)= x^x^x…

  6. Spiros, could you provide me with an email to be able to send an innovative non-binary/Boolean quantum algorithm to be considered at the Expert’s Corner of Quantum Frontiers?
    Regards,
    Jaime
    PS. Off-topic contact comment not for posting.

Your thoughts here.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s