2
$\begingroup$

Given is a domino parts set with typical 28 parts from [ | ] to [6|6].

[ | ] [ |1] [ |2] [ |3] [ |4] [ |5] [ |6]

[1|1] [1|2] [1|3] [1|4] [1|5] [1|6] [2|2]

[2|3] [2|4] [2|5] [2|6] [3|3] [3|4] [3|5]

[3|6] [4|4] [4|5] [4|6] [5|5] [5|6] [6|6]

As every domino player knows, one can only place a part after one of the 2 ends of the dominoes chain; and the end placed part free half must match the half of the part to be placed that will be snapped to it!

The rules for scoring are: every time a part is placed, if the sum of both ends of the dominoes chain is a multiple of 5, you add it to you current score.

example: [4|2] [2|1] makes 5 points

A double (every part where the two halfes are equal) is always placed rotated by 90º; so for accounting purposes, unlike other pieces, both sides ot the part are taken into account.

Example:

___       ___
|6|       |4|
——— [6|4] ———  
|6|       |4|
———       ———

makes for 20 points.

One single part placed accounts as the two tips.

Example [2|3] accounts as 5 points

And

___ 
|5| 
——— 
|5| 
——— 

accounts as 10 points.

So what is the chain that achieves the maximal number of points and what is that score?

$\endgroup$
  • $\begingroup$ In your example with the two doubles, if the double-6 wasn't there when the double-4 was placed, would that only give $10$ points? And is it correct that your example giving $20$ points is the maximum possible? I.e. the possible scores when placing a part are $0,5,10,15,20$? $\endgroup$ – Jens Jan 23 '17 at 16:39
  • $\begingroup$ Wait, $15$ isn't possible, right? Also, I assume there is only $1$ player? $\endgroup$ – Jens Jan 23 '17 at 16:54
  • $\begingroup$ @Jens: No. For having 10 points, the sum needs to be 10 at the moment. And the re is no moment it could happen by putting parts [6|6], [6|4], [4|4]. 20 points is the maximum possible on a placing and it is only achievable by having [6|6] in one end and [4|4] on the other. And, yes: "the possible scores when placing a part are 0,5,10,15,20". $\endgroup$ – sergiol Jan 23 '17 at 17:48
  • $\begingroup$ 15 can happen, For example, placing [5|5][5|0][0|1][1|5] by that order will make the points: 10, 10, 0, 15, in each place action. And, yes, the question is for only one player. $\endgroup$ – sergiol Jan 23 '17 at 17:51
  • 1
    $\begingroup$ @sergiol What is the rule about doubles? In standard dominoes, when a double is placed, pieces can then be placed at all 3 sides. From your description I have a sense that you are keeping everything to a straight line? $\endgroup$ – Jan Jan 24 '17 at 8:44
1
$\begingroup$

I made a program to simulate the game and got the following result:

enter image description here

The middle row shows the placement of the dominoes, the bottom row shows the order of placement of each domino and the upper row shows the total score as each domino is placed. The total score after the placement of the last domino can be seen to be $175$.

The result comes with several caveats. A full blown simulation with all $28$ dominoes is simply too large to be finished in reasonable time (except perhaps on a super-computer). So I made some shortcuts:

  1. To reduce the number of computations needed, I decided to only start a chain with one of the five dominoes which, when placed first, gives points, i.e.: $[0,5], [1,4], [2,3], [4,6]$ or $[5,5]$

  2. To further reduce computations (and this is the big one) I decided to do the simulation incrementally in the following way:

    a. Run the simulation with all $28$ dominoes, but cap the number of links (dominoes) in the chain at $N \lt 28$. Keep increasing $N$ until it really hurts (effectively a full day of computation, which was at $N=11$).

    b. Check if domino placements for chains of length $n<N$ seem to stabilize in the chain length interval between $n$ and $N$. I.e. check if the same $n$ dominoes are placed in the same order repeatedly, for chains of length $n$ to $N$. If so, assume these $n$ dominoes will always be placed in this order, no matter how large the chains get.

    c. Fixate the first $n$ dominoes to be these dominoes in that order. I.e. assume that no matter how long the chain gets, the first $n$ domino placements will be these $n$ dominoes. Continue the search for the best chain given that the first $n$ dominoes must be the ones found above and thus excluding these dominoes from participating in the further search.

    d. Go to b.

With these caveats, I submit that the answer is $175$.

$\endgroup$
  • $\begingroup$ On a maths site, I was hoping for a more mathematical theoretical approach! Nevertheless nice answer! Thanks! $\endgroup$ – sergiol Feb 6 '17 at 23:18
  • $\begingroup$ I believe this is incorrect because it does not take into account the special case of doubles. As stated by the OP : "A double (every part where the two halfes are equal) is always placed rotated by 90º; so for accounting purposes, unlike other pieces, both sides ot the part are taken into account." $\endgroup$ – samfr May 14 at 4:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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