Just for fun problem, hoping it builds motivation for educational math or creative techniques if lucky to turn out that way.

Imagine you use a normal set of 6 high dominoes (28 pieces 0 to 6). You randomize them and expose one. Then select another randomly and try to place it to the one you already have wherever it fits and proper strategy suggests. You can use only 2 ends, so doubles are not placed vertically (for more branching as in many versions) so that the game remains simple enough with just 2 ends at all times.

1) Find the proper strategy how to play it.

2) Estimate or exactly calculate the probability the entire 28 pieces are placed in one run.

3) What is the average length of a run (how far does the average run go before it halts)


Feel free to solve any smaller system like the 0 to 2 dominoes (22,21,11,20,10,00) if it helps build results and intuition.




Alternative game now; (my patent lol if it turns interesting)

We have 2 players. The game starts as before with the first guy uncovering a domino and the second taking turn to uncover another one and try to place it (if successful then the other player plays again etc they alternate until one cant continue). If a player cannot play the domino they have drawn the game ends and that player loses.

Estimate the win probability when you draw first (ie that the opponent gets blocked unable to play drawn domino).

Also consider that the opponents can play the game with bets (then called or reraised or folded) when its their turn to play. So they start with some antes pot and then they bet as much as they like (like nl poker) (or maybe pot limit structure).

In the original game, you do not say what the objective of one's strategy should be. I can think of three objectives that may be conflicting to some degree:

(1) Maximize the chance of playing all 28 tiles

(2) Maximize the expected longest starting string

(3) Maximize the expected average starting string

I would imagine that the optimal strategy could be (would be?) different for these three different objectives.

Obviously the original has to do with maximizing the probability to finish it. Based on that then you get the others (like what is the avg length if you played with the objective to finish with highest probability). If you play to maximize length i am not sure if it is conflicting or not but lets say its always aimed at the probability maximization. The project initially is to finish it. The other versions of games though of course start getting different objectives each time. The original problem can be properly priced i suppose and offered as game. Of course the strategy is probably not hard it would seem, even if hard to do without computer assistance i mean live, if there were time limits in how fast you play.

Although yes i can see if you wanted to maximize steps and not probability at some point you might select a path that secures an impossibility to finish in exchange for a significant probability opening to see multiple additional steps happen vs the correct move to keep game alive but at the substantial reduction of surviving one more domino say type thing because it has to pass from a narrow path.

You know when you start a post answering a legitimate (and essential) question with "Obviously ..." you come off as a total jackass. Not a great way to start a discussion.

Whats the matter, are we having attitude adjustment issues here or what? Whats your problem? Way to go trying to insult the OP. Did i call you names? Dont i have a bloody title saying Dominoes completion in one run success probability? The only way this makes sense without a further description is if the success probability is the objective, the main focus. Otherwise it would be for example idiotic to ask a question and not have in mind the only unambiguous interpretation since clearly i could otherwise want to maximize the avg number of runs or the avg whatever function of runs or the sum of dominoes scoring multiples of 5s sum of ends score and all kinds of wild imagination objectives that were never specified.

For something not to be introduced it means its not necessary to introduce it because the objective is to maximize the run success probability. Otherwise that probability can be anything you want to make it, making the statement ridiculously ambiguous, undefined. It is profound that i could never mean anything else here otherwise i would have been explicit about it since it clearly requires a definition what on earth i am after. Only way such definition is not required is if its not needed. Only way its not needed is if probability maximization to finish is the only thing that matters. Who is the jackass now? There was nothing wrong with what i said. The fact you took insult in it and called me names is the only jackassious thing about it all. It is shocking in fact. Where did that come from?

And let me also say that no hard feelings exist ever. I respect you as a poster and lets get back into constructive exchanges. We both deserve better. I imagine i am your friend and value your contributions a lot.

So lets see what happens in the trivial 00,01,11 case.

If you draw 00 you then lose only if you draw 11. So that is 1/3*1/2 loss.
If you draw 01 you then never lose as 00,11 can both be played safely.
If you draw 11 you then lose only if you draw 00 next. So that is 1/3*1/2 loss also.

Overall win probability on trivial play for the n=1 set of dominoes (3 pieces) is 1-2/6=2/3

For the n=2 set you have 6 pieces (22,21,20,11,10,00) (in general you have 1/2*((n+1)^2-n-1)+n+1 pieces)

If you draw 22 you then lose if you draw 11,00,10 right away. That is 1/6*3/5 loss probability.

That then leaves these branches; 22-21 and 22-20.

In the first 22-21 the remaining pieces are 20,11,10,00 so the next loss comes from drawing 00. That is an additional 1/6*1/5*1/4 loss.
If you draw 20 you then have 02-22-21 and 11,10,00 left so you can play any of the 3 left you draw. Of them however if you get 11 the choice is convenient and then nothing bad happens the process finishes with the other 2 left. If you get 00 the same thing happens. If you get 10 however there is no way to play it that doesnt lead to problems. So thats another source of failure. Its worth 1/6*1/5*1/4*1/3.

And so on to be continued, you get the idea how detailed it all gets.

This is where maybe some creative possibly group theory or symbolic calculation smart trick manipulation (eg Mathematica) can yield the probability as a standard sum of terms that their order matters etc...

With 6 items you have 6! ways to draw them that are instantly killed in many cases by not having a strategy that orders them properly. With 28 pieces it will get ugly fast but the probability may converge real fast and some main terms to estimate it may prevail. Some branches die fast eg some 00-66 start with doubles is instantly inhibiting the process it would seem. Even a standard XY domino eg 64 is only now depending on a small fraction each time like from the remaining 27 pieces only 12 eg 66,65,63,62,61,60,40,41,42,43,44,45 can continue so it must drop fast.

Looking forward to some creating thinking maybe even from seemingly unrelated fields of mathematics.

One could also ask how many different domino lines of length 28 exist? Or how they relate to each other?

Also these proper length 28 lines mentioned are not necessarily all legitimate, (when connected i mean), because (although i need to think it more) many of them might not correspond to optimal strategy necessarily. kind of like having 11-16-66-62-22-21-14-42-22-20 and then getting 01 you would not put it it would seem (not sure though) in the right side to produce two 1s with only 2 ones ie 13,12 left in the still big deck while there are much more 0s. Although notice issues like maximizing length vs completion probability are introduced now also and i am not entirely certain that they agree for example on decision here. In fact i am not entirely certain in general in complex cases that even maximizing length wants to put it in way that results in 2 0s either (probably yes here but maybe not in other cases, not clear on this yet to me, it seems a complex enough problem).

Interesting problem. My initial thought was to construct a graph having 28 dominoes as the vertices then you need to find the number of hamiltonian paths. Most likely this is a dead end but it turns out there is a better graph representation (dominoes are represented by edges) where the problem is reduced to finding eulerian cycles/paths: http://mathafou.free.fr/pbm_en/sol233.html

Nice thanks. Lets look more into it. For anyone interested to follow these closer;

http://en.wikipedia.org/wiki/Eulerian_path

http://en.wikipedia.org/wiki/Hamiltonian_path

While watching the NFL playoffs, I coded up the 0-2 set (6 tiles). Here are some results for this simplest case.

Of course, there are 6! = 720 possible tile sequences. 96 of the sequences permit a complete path.

I coded up four different levels of strategy.

(1) Flip a coin if you can play a tile on either end (this is a Level 0 strategy):

Expected tally of 1 move = 288.00
Expected tally of 2 moves = 108.00
Expected tally of 3 moves = 95.85
Expected tally of 4 moves = 84.25
Expected tally of 5 moves = 71.58
Expected tally of 6 moves = 72.32

(2) If you can play a tile at either end, choose the end that maximizes the chance of playing the next tile (Level 1 strategy):

Tally of 1 move = 288
Tally of 2 moves = 108
Tally of 3 moves = 96
Tally of 4 moves = 72
Tally of 5 moves = 60
Tally of 6 moves = 96

(3) If you can play a tile at either end, choose the end that maximizes the chance of playing the next two tiles (Level 2 strategy):

Same results as Level 1 strategy

Tally of 1 move = 288
Tally of 2 moves = 108
Tally of 3 moves = 96
Tally of 4 moves = 72
Tally of 5 moves = 60
Tally of 6 moves = 96

(4) You have perfect knowledge of the sequence of the tiles:

Tally of 1 move = 288
Tally of 2 moves = 108
Tally of 3 moves = 84
Tally of 4 moves = 72
Tally of 5 moves = 72
Tally of 6 moves = 96

The 0-3 set (10 tiles) seems like it could be amenable to a similar approach, but the number of permutations increases dramatically.