4
$\begingroup$

enter image description here

Taken from UK Bebras Computational Thinking Challenge

I am particularly interested to see how you can go through this systematically as opposed to using trial and error.

Clarification edits:

  • The dominoes must be placed end-to-end in order to form a circle.
  • No domino can be used twice unless they appear twice on the list.
  • There is more than one arrangement for the maximum amount of dominoes used
$\endgroup$
0

2 Answers 2

9
$\begingroup$

In a ring,

every number occurs in pairs, so they are all used an even number of times.

The given dominoes have three 1s, three 2s, four 3s, three 4s, five 5s. So 1, 2, 4 and 5 occur an odd number of times.

At best we can therefore leave out one of each of those, for example by leaving out a [1|4] and a [2|5] domino. The remaining 7 dominoes are easy to then put into a ring, for example:
[5|1] [1|3] [3|2] [2|5] [5|4] [4|3] [3|5].

$\endgroup$
3
  • $\begingroup$ I edited them to make dominoes, hope you don't mind $\endgroup$ Oct 28, 2016 at 14:33
  • $\begingroup$ Beat me to the punch with the answer! $\endgroup$ Oct 28, 2016 at 14:35
  • 1
    $\begingroup$ @BeastlyGerbil That stops them from being hidden by the spoilertag. $\endgroup$ Oct 28, 2016 at 14:36
2
$\begingroup$

I think that

5 is the longest you can make after a first analysis.
to make a ring, the first must match the last. And to do that you need a pair amount of a single digit. And all those who are not at the extremities will also need to only come in pair. But 1,2,4,5 are all impair, so no matter what there is 4 dominoes that you will have to put aside. One solution with 5 can then easily be deduced.
for example : [3,2][2,5][5,1][1,4][4,3]

EDIT
Failed to think about removing 2 odds at once with just 1 domino >.<
Second attempt :

removing [2,5]and[1,4] seems like the most efficient.
so 7 dominoes remaining. Then chaining them all together shouldn't take too much effort since it ends up being a circle and all the remaining numbers are even.
For example [2,5][5,4][4,3][3,5][5,1][1,3][3,2]

$\endgroup$
5
  • $\begingroup$ I edited them to make dominoes, hope you don't mind $\endgroup$ Oct 28, 2016 at 14:33
  • $\begingroup$ @BeastlyGerbil That stops them from being hidden by the spoilertag. $\endgroup$ Oct 28, 2016 at 14:36
  • $\begingroup$ @randal'thor oh didn't realise. Should I rollback? $\endgroup$ Oct 28, 2016 at 14:37
  • $\begingroup$ @BeastlyGerbil Looks like the OP has done it. $\endgroup$ Oct 28, 2016 at 14:41
  • $\begingroup$ Oh wow sorry about that, I was in edit mode for so long I didn't know what was happening over here, I think I edited over your edit by mistake.... and I got totally beaten to the punch by other puzzlers XD $\endgroup$ Oct 28, 2016 at 14:43

Your Answer

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

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