Teaser 2932: Triangulation
From The Sunday Times, 2nd December 2018 [link] [link]
Liam plans to make a set of dominoes. They will be triangular, and one face of each domino will have a number at each corner. The numbers run from 0 up to a maximum digit (9 or less), and the set is to include all possible distinguishable dominoes.
With the maximum digit he has chosen the set would contain a triangular number of dominoes. [A triangular number is one where that number of balls can fit snugly in an equilateral triangle, for example the 15 red balls on a snooker table].
How many dominoes will he need to make?
[teaser2932]
S2T2 
Jim Randell 11:32 am on 20 March 2019 Permalink |
For each maximum digit, this Python program constructs all possible dominoes that are unique by rotation. It runs in 75ms.
Run: [ @repl.it ]
from itertools import product from enigma import (irange, is_triangular, printf) for d in irange(0, 9): s = set() # choose three numbers for the corners for (a, b, c) in product(irange(0, d), repeat=3): # record the domino by it's minimal rotation s.add(min((a, b, c), (b, c, a), (c, a, b))) # count the number of different dominoes n = len(s) t = ('[triangular]' if is_triangular(n) else '') printf("d={d}: {n} dominoes {t}")Solution: He will need to make 45 dominoes.
There is a degenerate solution where only the digit 0 is used. There is only one domino (0, 0, 0), and 1 is a triangular number T(1) = 1.
Running the program we see the number dominoes is given by the following sequence:
which is OEIS A006527 [ link ] the general formula is:
so we don’t have to count the dominoes.
from enigma import (irange, is_triangular, printf) for d in irange(1, 10): n = (d**3 + 2 * d) // 3 t = ('[triangular]' if is_triangular(n) else '') printf("d={d}: {n} dominoes {t}", d=d - 1)If we consider d > 9 there are larger solutions at d = 12 (741 dominoes) and d = 35 (15576 dominoes).
LikeLike