Return to Question

  Expected halting time for "The 2^n Game" (aka 2048) -- with random moves

  Expected halting time for "The 2^n Game" (aka 2048) -- with random moves

It's been weeks (months?) since the 2048 game--by Gabriele Cirulli--took Internet by storm. I have an explicit integer $X$ which is greater or equal than any score of this game. Possibly my $X$ is the actual maximal score, I don't know, it may go either way. Thus my question: what is the maximal possible score for game 2048? (I'll provide $X$ in an answer below, as a SPOILER; it was quite straightforward to get $X$, and similar upper bounds for a way larger family of similar games). If $X$ is not sharp than sharper bounds are welcome too.

Consider $\ A=A_0=A_1=\ldots$ and $\ \forall_{n=0\ 1\ \ldots}\ |A_n|=b\ $ be finite (the playing board is finite so-to-speak). Consider an arbitrary non-negative integer $n$. For each $\ x\in A_n\ $ consider one of its oldest ancestors. By permuting sets $\ A_n\ $ we may assume that $\ x\ $ itself is always its ancestor whenever there is an ancestor for $\ x.\ $ Now let $\ \xi\ $ be the set of all $\ y\in A_n\,\ $ different from $\ x,\ $ for which there is an ancestor at least as old as the one for $\ x.\\\$. Then $\ x\ $ has all its ancestors in $\ A(x) := A\setminus\xi.\ $ Observe that functions (*moves*) preserve $\ A(x).\ $ hence we can consider the induced template for $\ A(x)\ $ and the respective bound:

REMARK Let me repeat what I said from the start, that the whole thing is straightforward.

t's been weeks (months?) since the 2048 game--by Gabriele Cirulli--took Internet by storm. I have an explicit integer $X$ which is greater or equal than any score of this game. Possibly my $X$ is the actual maximal score, I don't know, it may go either way. Thus my question: what is the maximal possible score for game 2048? (I'll provide $X$ in an answer below, as a SPOILER; it was quite straightforward to get $X$, and similar upper bounds for a way larger family of similar games). If $X$ is not sharp than sharper bounds are welcome too.

Consider $\ A=A_0=A_1=\ldots$ and $\ \forall_{n=0\ 1\ \ldots}\ |A_n|=b\ $ be finite (the playing board is finite so-to-speak). Consider an arbitrary non-negative integer $n$. For each $\ x\in A_n\ $ consider one of its oldest ancestors. By permuting sets $\ A_n\ $ we may assume that $\ x\ $ itself is always its ancestor whenever there is an ancestor for $\ x.\ $ Now let $\ \xi\ $ be the set of all $\ y\in A_n\,\ $ different from $\ x,\ $ for which there is an ancestor at least as old as the one for $\ x.\ $. Then $\ x\ $ has all its ancestors in $\ A(x) := A\setminus\xi.\ $ Observe that functions (moves) preserve $\ A(x).\ $ Thus we can consider the induced template for $\ A(x)\ $ and the respective bound:

REMARK Let me repeat what I said from the start, that the whole thing is straightforward. A simple proof when it appears in a result+proof combination can still have a value (when the theorem is significant). @Pietro's above comment is too sketchy. The @David's post math.stackexchange.com/a/902535/448 still doesn't mention some points, as simple as the whole thing is (see my comment over there at stackexchange). But anyway, a complete proof, with all essential moments was already provided by me below (and also above for the total sum), and in an extended generality. David's post simply repeats my obvious main idea--anyway, there is perhaps but one sensible way, but for details.