Tim and Tom are fictional characters (cats, I believe) who like to play the LoL number game.

In this game, Tim chooses two distinct integers A and B, both ≥ 2, and shows them to Tom. Tom's goal is to find a succession of translolmations that can be applied to A in order to obtain B. There are only two types of translolmations, denoted by the letters $\bf L$ and $\bf o$, in the order as they are applied, from left to right: $\bf L$ replaces the current integer with its square, and $\bf o$ replaces the current integer with the number of digits in its binary representation.

For example, if Tim chooses A = 7 and B = 11, a valid solution for Tom would be $\bf LoLLo$:

$7\buildrel\bf L\over\longrightarrow 49\buildrel\bf o\over\longrightarrow 6\buildrel\bf L\over\longrightarrow 36\buildrel\bf L\over\longrightarrow 1296\buildrel\bf o\over\longrightarrow 11$

For A = 10 and B = 9, valid solutions are $\bf ooL$ and $\bf oLLo$:

$10\buildrel\bf o\over\longrightarrow 4\buildrel\bf o\over\longrightarrow 3\buildrel\bf L\over\longrightarrow 9$

$10\buildrel\bf o\over\longrightarrow 4\buildrel\bf L\over\longrightarrow 16\buildrel\bf L\over\longrightarrow 256\buildrel\bf o\over\longrightarrow 9$

Tom is confident he will always be able to win the game, given a sufficient number of translolmations, no matter what integers Tim chooses. Can you explain how?

  • 6
    They're LoL cats :) – Bob Apr 20 '15 at 16:31
  • 1
    I believe Tim will win (by attrition) if he chooses A=2 and B=G. – Rob Watts Apr 20 '15 at 16:41
  • 1
    Tom is confident, but is Tom correct?) – klm123 Apr 20 '15 at 18:26
  • 7
    League of Legends cats? Usually for LOL cats all three letters are capitalized. :) – Almo Apr 20 '15 at 20:00
  • 2
    Notice that the "o" transformation is equivalent to floor(log_2(x)+1). – Kevin Apr 20 '15 at 22:32
up vote 13 down vote accepted

First of all, notice that by repeatedly applying $\bf o$, we can always reduce a number to 2. This should be readily apparent, but here's a non-rigorous proof of the fact:

2 has a binary representation requiring 2 digits (10), as does 3 (11). The length of the binary representation of a number grows slower than $n$, so $n\ge 3$ implies that $n \buildrel\bf o\over \longrightarrow m$ with $n \gt m$. Therefore, if $n\ge 3$, applying $\bf o$ will always reduce it by at least 1, allowing us through repeated applications to reduce the number to 2.

Now let's consider $\bf o$ in reverse. In order to get to B, we need to apply $\bf o$ to a number whose binary representation has B digits: $2^{B-1} \le n \lt 2^B$. If we square a number, it can jump that range - for example if $B=5$ then $2^{5-1}=16$ and $2^{5}=32$, but $15^2=225$.

However, if we apply $\bf o$ twice, then the range becomes far wider - $2^{2^{B-1}}\le n\lt 2^{2^{B}}$. At this point, there's no way to jump the range:

$$(2^{2^{B-1}}-1)^2=(2^{2^{B-1}})^2-2*2^{2^{B-1}}+1=2^{2^B}-2^{2^{B-1}+1}+1$$

Because $B\ge 2$, $2^{2^{B-1}+1}\ge 2^{2^{1}+1}=2^3=8$, so $2^{2^B}-2^{2^{B-1}+1}+1<2^{2^B}-7<2^{2^B}$.

So to summarize, apply $\bf o$ until it is less than $2^{2^B}$, then apply $\bf L$ until $2^{2^{B-1}}\le n\lt 2^{2^{B}}$, and then apply $\bf o$ twice. Of course, this is horribly inefficient, but it proves that it is always possible. For example, with B=197, $2^{2^B}$ is somewhere around $10^{10^{58}}$.

  • 2
    Simpler: Every number can reach 2, and I claim that 2 can reach every number. From 2 apply L n times and then o twice and we arrive at n. – Ben Frankel Apr 20 '15 at 18:54
  • @BenFrankel that requires you to actually go all the way down to 2. I've shown that you can use any number below 2^(2^(B-1)). – Rob Watts Apr 20 '15 at 19:32
  • Well done on being the first one to give a solution :) – GOTO 0 Apr 21 '15 at 15:00

Whenever $x>2$, we have $o(x)<x$, so applying $o$ enough (for example, $A$ times) obtains $$2$$ Applying $L$ to this a total of $B-1$ times gets $$2^{2^{B-1}}$$ This is a one followed by $2^{B-1}$ zeros, so applying $o$ to this gets $$2^{B-1}+1$$ This number is a 1, followed by $B-2$ zeroes, followed by a $1$, so applying o this gets $$ B $$ Thus, a recipe to get from $A$ to $B$ is given by $$ o^2(L^{B-1}(o^A(A)))=B $$ where $o^n$ denote repeated function application.

  • @BenFrankel I realize this is exactly what your comment instructed, but I did think of this independently and really wanted to post it :P – Mike Earnest Apr 20 '15 at 19:00
  • Sure, no problem. :) – Ben Frankel Apr 20 '15 at 20:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.