• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

2048 puzzle

Sa967St

Not A Moderator
Joined
Mar 11, 2008
Messages
3,795
Location
Waterloo, ON, Canada
WCA
2007STRO01
YouTube
Visit Channel
Can you think of a way to prove it without just observing arbitrarily many cases? Also, would it still be true if you start with three or four tiles instead of two?

I consider Ricardo's first sentence the proof. Is it not clear enough?

I was referring to proving the formula itself, not the ratio being <=1.

Also, as TDM mentioned, you can have multiple merges per turn, losing multiple tiles in one turn. I suspect that in order to lose multiple tiles (say, 2 tiles) in one turn, there must have been one previous turn where you didn't merge anything, but I can't think of why. Either that, or I'm not fully understanding Ricardo's post.


Question: Does anyone know the probability of a getting a 4 instead of a 2?

Looks like 10%:

Code:
// Adds a tile in a random position
GameManager.prototype.addRandomTile = function () {
  if (this.grid.cellsAvailable()) {
    var value = Math.random() < 0.9 ? 2 : 4;
    var tile = new Tile(this.grid.randomAvailableCell(), value);

    this.grid.insertTile(tile);
  }
};
From http://gabrielecirulli.github.io/2048/js/game_manager.js
Thanks!
 
Last edited:

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
I was referring to proving the formula itself

That's what I thought, and Ricardo's first sentence does prove it.

Also, as TDM mentioned, you have have multiple merges per turn, losing multiple tiles in one turn. I suspect that in order to lose multiple tiles (say, 2 tiles) in one turn, there must have been one previous turn where you didn't merge anything, but I can't think of why.

Really doesn't matter *when* the merges occurred, what matters is their overall number (that's what you have in the formula, after all).

Let's say you start with 4 tiles and during play, you gain 5 and lose 7. You end up with 4+5-7=2, no matter when when the gains and losses happened. In general:

Code:
End = Start + Gains - Losses
    = Start + Turns - Merges

The first equation is known from everyday life, and the second is what Ricardo pointed out. Just rearrange the result to get your version of the formula.
 
Last edited:

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
I suspect that in order to lose multiple tiles (say, 2 tiles) in one turn, there must have been one previous turn where you didn't merge anything, but I can't think of why.

Actually there must even have been two such merge-less previous turns. If you never have such a turn then you always have two tiles on the board (the merged and the new) and thus can only do one merge. Only merge-less turns increase the number of tiles, and each only increases it by 1. Since two merges in one turn need four tiles on the board and you start with only two tiles, this requires two previous merge-less moves.

Little riddle: How many times during one game can you have exactly two tiles on the board?

Harder riddle (and I don't know the exact answer): What's the smallest possible sum of all tiles on the board when you reach the 2048 tile?
 
Last edited:

RicardoRix

Member
Joined
Jul 29, 2013
Messages
130
WCA
2013LEIS01
Little riddle: How many times during one game can you have exactly two tiles on the board?

Assuming you always get the '2' tile on a move, it's the new 2 tile with every other number combination.
so 2+2, 2+4, 2+8, 2+16, 2+32, etc.

Actually scrub that, I can't see how you get anything other than 2+2, and then 2+4. You've got too many 2's cluttering up the place.

For the hard riddle I'm going with 5 tiles: 2,2,8,8,2048.
 
Last edited:

TDM

Member
Joined
Mar 7, 2013
Messages
7,006
Location
Oxfordshire, UK
WCA
2013MEND03
YouTube
Visit Channel
twFbJId.png

Can anyone beat that?
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
That's what I do, except I can't get lucky. When you can't move, do you start spamming left-right, or do one L/R move and then keep doing up-down?

One game only takes a few seconds that way, so just do it more often :). In my second 96, the game was already over right after the U/D spamming.

Got an 88 now, but after the U/D spamming I could still do L/R a bit and I did stop and think about how to do it that (that's also how I got my first 96).

2w7ihk1.png
 
Last edited:

TDM

Member
Joined
Mar 7, 2013
Messages
7,006
Location
Oxfordshire, UK
WCA
2013MEND03
YouTube
Visit Channel
One game only takes a few seconds that way, so just do it more often :). In my second 96, the game was already over right after the U/D spamming.

Got an 88 now, but after the U/D spamming I could still do L/R a bit and I did stop and think about how to do it that (that's also how I got my first 96).
After getting 1000+ several times in a row...
BKUowui.png

It's very unusual to get the game to stop without having to do L/R, but you were right: keep going and you'll get lucky eventually ;)
 

RicardoRix

Member
Joined
Jul 29, 2013
Messages
130
WCA
2013LEIS01
Actually there must even have been two such merge-less previous turns. If you never have such a turn then you always have two tiles on the board (the merged and the new) and thus can only do one merge. Only merge-less turns increase the number of tiles, and each only increases it by 1. Since two merges in one turn need four tiles on the board and you start with only two tiles, this requires two previous merge-less moves.

Little riddle: How many times during one game can you have exactly two tiles on the board?

Harder riddle (and I don't know the exact answer): What's the smallest possible sum of all tiles on the board when you reach the 2048 tile?

I think I can explain this smallest sum by working backwards. So where normally you always get a 2 tile added in, going backwards you must have a 2 tile to take away. So you need to divide down the 2048 tile as quick as possible so it starts to give you 2's to take away. So you need a few mid-range tiles to get you to this stage. The minimum for this would be: 2,2,8,8,2048,

The sequence going forward:

2,4,8,16,32,64,128,256,512,1024,
2,2,4,8,16,32,64,128,256,512,1024,
2,4,4,8,16,32,64,128,256,512,1024,
2,2,8,8,16,32,64,128,256,512,1024,
2,4,16,16,32,64,128,256,512,1024,
2,2,4,32,32,64,128,256,512,1024,
2,4,4,64,64,128,256,512,1024,
2,2,8,128,128,256,512,1024,
2,4,8,256,256,512,1024,
2,2,4,8,512,512,1024,
2,4,4,8,1024,1024,
2,2,8,8,2048,
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
2,4,8,16,32,64,128,256,512,1024

But is this state actually achievable? I'd instantly believe it if the board were long so you could really think about doing this simply in a straight line, but on the 4x4 board it's not that obvious.

And is 4,4,8,16,32,64,128,256,512,1024 maybe also achievable? It would lead to a smaller end result.

Also, what about finishes where you don't go straight up through the powers of two, one per turn? Where you don't just do one merge-towards-2048 per turn but several? For example, right before the last turn you do of course need two 1024-tiles, but you don't need to already have a 1024-tile before the next-to-last turn if that next-to-last turn builds both 1024-tiles at the same time. Maybe such other progressions could lead to a smaller end result?

(I btw really do have these questions and don't know the answers)

Your answer to my simpler riddle is not quite correct yet, btw, as you're still assuming only 2-tiles popping up. There's also a somewhat neat little insight behind that riddle, which explains why you can't get any boards with just two tiles except very few small ones.
 
Last edited:

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
Little riddle: How many times during one game can you have exactly two tiles on the board?

A quick lemma to show that (Number of turns taken) \( \geq \) (Number of Merges made) must hold true from the start of the game to your current board state:
2=B-T+M

where
B=number of tiles on the board
T=number of turns taken
M=number of merges

Assume T<M

then
M=T+k where k is a natural number
2=B-T+(T+k)
2=B+k
2-k=B

This would say that that board has fewer than 2 tiles. I am going by Sarah's statement earlier that this is impossible.

Therefore \( T \geq M \) must hold true.

Since \( T \geq M \) must hold true, then we can write:
T=M+j where j is a non-negative integer

2=B-(M+j)+M
2=B-j
2+j=B

And you have 2 tiles on your board only when j=0, which means when T=M.

That doesn't answer your question, but that is the extent of what I have noticed so far.

--edit--
Just trying different board states in my head I can't find any games where I have 2 tiles more than three times.
 
Last edited:

Jaycee

Member
Joined
Jul 17, 2011
Messages
1,843
Location
Crestwood, Illinois
YouTube
Visit Channel
Second time getting the 4096, and I felt like I could have gotten the 8192, but I messed up while paying half of my attention to this and half of my attention to my friend who was talking to me in study hall.

ot43lk.png
 

Attachments

  • ot43lk.png
    ot43lk.png
    53 KB · Views: 16
Top