22
$\begingroup$

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?

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

2 Answers 2

13
$\begingroup$

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}}$.

$\endgroup$
3
  • 4
    $\begingroup$ 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. $\endgroup$ Apr 20, 2015 at 18:54
  • 1
    $\begingroup$ @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)). $\endgroup$
    – Rob Watts
    Apr 20, 2015 at 19:32
  • 1
    $\begingroup$ Well done on being the first one to give a solution :) $\endgroup$
    – GOTO 0
    Apr 21, 2015 at 15:00
12
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ @BenFrankel I realize this is exactly what your comment instructed, but I did think of this independently and really wanted to post it :P $\endgroup$ Apr 20, 2015 at 19:00
  • $\begingroup$ Sure, no problem. :) $\endgroup$ Apr 20, 2015 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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