Teaser 3075: Prime cuts for dinner
From The Sunday Times, 29th August 2021 [link] [link]
Tickets to the club dinner were sequentially numbered 1, 2, …, etc. and every ticket was sold. The number of guests for dinner was the highest common factor of three different two-figure numbers and the lowest common multiple of three different two-figure numbers. There were several dinner tables, each with the same number of seats, couples being seated with friends. The guests on each table added their ticket numbers together and obtained one of two prime numbers, both less than 150, but if I told you the larger prime number you would not be able to determine the other.
What was the larger of the two prime numbers?
[teaser3075]
GeoffR and 
Frits and 
Hugh Casement, 
Alex.T.Sutherland, and 1 other are discussing. 
Robert Brown are discussing. 
S2T2 
Jim Randell 7:03 pm on 27 August 2021 Permalink |
This Python program looks for candidate solutions, but doesn’t show that the tickets can be assigned to tables in the required fashion. However there is only one possible answer, so this is not necessary. (However, it is possible to assign tickets in both cases – see [link]).
It runs in 234ms.
Run: [ @replit ]
from enigma import mgcd, mlcm, subsets, irange, intersect, divisors_pairs, tri, Primes, express, filter_unique, unpack, printf # generate candidate solutions def generate(): # primes less than 150 primes = Primes(150) # look for gcds and lcms of 3 2-digit numbers (gcds, lcms) = (set(), set()) for ns in subsets(irange(10, 99), size=3): gcds.add(mgcd(*ns)) lcms.add(mlcm(*ns)) # consider number of tickets, n for n in intersect([gcds, lcms]): # total sum of tickets t = tri(n) # consider k tables, with q people per table for (k, q) in divisors_pairs(n, every=1): if k < 3 or q < 3: continue # consider 2 primes, for the ticket sums for (p1, p2) in subsets(primes, size=2): # express the total using 2 of the primes for (q1, q2) in express(t, (p1, p2), min_q=1): if q1 + q2 == k: yield (n, t, k, q, p1, p2, q1, q2) # look for candidate solutions, where p1 is ambiguous by p2 ss = filter_unique( generate(), unpack(lambda n, t, k, q, p1, p2, q1, q2: p2), unpack(lambda n, t, k, q, p1, p2, q1, q2: p1), ) for (n, t, k, q, p1, p2, q1, q2) in ss.non_unique: printf("n={n}: t={t}; {k} tables of {q} people; ({p1}, {p2}) -> ({q1}, {q2})")Solution: The larger of the two primes was 109.
There are 30 tickets:
And 30 is the only number that satisfies the conditions.
So the sum of the ticket numbers is T(30) = 465.
And the tickets can be arranged into 5 tables of 6 people, to give one of two prime sums for each table as follows:
In each case the larger prime is 109.
And there are many ways to achieve the same sums.
LikeLike
GeoffR 9:30 am on 31 August 2021 Permalink |
I programmed this teaser in two stages, first re-using the few lines of Jim’s code to find the intersection of GCD/LCM values to give the number of guests.
The next stage was to examine possible table arrangements and arrangements of two prime numbers to make up the sum of tickets.
I also tested different prime number multipliers e.g 4/1 and 3/2 for the 5 table arrangement and 5/1 and 4/2 for the 6 table arrangement.
from itertools import permutations from enigma import mgcd, mlcm, subsets, irange, Primes # primes less than 150 primes = Primes(150) # look for 3 No. 2-digit numbers for gcd and lcm values gcds, lcms = set(), set() for ns in subsets(irange(10, 99), size=3): gcds.add(mgcd(*ns)) lcms.add(mlcm(*ns)) # Numbers of Guests (N) N = list(gcds.intersection(lcms))[0] print('No. of guests = ', N) # N = 30 # Ticket sum of numbers for N guests T = N * (N + 1)//2 print('Sum of all ticket numbers = ', T) # 30 people - possible table arrangements: # - 5 tables of 6 people or 6 tables of 5 people - two possibilities # - 2 tables of 15 people or 15 tables of 2 people - not viable # - 3 tables of 10 people or 10 tables of 3 people - not viable # try 5 tables of 6 people, using 2 primes to make sum of tickets # results were found for prime multipliers of 4 and 1 # no results from 2 and 3 prime multipliers were found print('Two possible prime values:') for p1, p2 in permutations(primes, 2): if 4 * p1 + p2 == T: print( (max(p1, p2), min(p1, p2)), end = " ") # (149, 79) (109, 89) (101, 61) (103, 53) (107, 37) (109, 29) (113, 13) # There is only maximum prime i.e. 109, where the other prime could not be known. # For maximum primes of 149, 101, 103, 107 and 113, the second prime is known. # try 6 tables of 5 people, using 2 primes make sum of tickets for p3, p4 in permutations(primes,2): if 5 * p3 + p4 == T: print(max(p3, p4), min(p3, p4)) # No solution # No. of guests = 30 # Sum of all ticket numbers = 465 # Two possible prime values: # (149, 79) (109, 89) (101, 61) (103, 53) (107, 37) (109, 29) (113, 13)This section of code find the two sets of three two digit numbers used by the setter for the HCF/LCM values in this teaser.
There were 33 numbers in the GCD set of numbers and 25,608 numbers in the LCM set of numbers, with a minimum value of 30 and a maximum value of 941,094. The setter used the minimum LCM value.
# The number of guests for dinner was the highest common # factor of three different two-figure numbers and the # lowest common multiple of three different two-figure numbers. # Q. What were these two sets of three digit numbers? from itertools import combinations from math import gcd, lcm for x in combinations(range(10, 100), 3): a, b, c = x if gcd(a, b, c) == 30: print(f"Three 2-digit values for HCF = {a}, {b}, {c}") for x in combinations(range(10, 100), 3): d, e, f = x if lcm(d, e, f) == 30: print(f"Three 2-digit values for LCM = {d}, {e}, {f}") # Three 2-digit values for HCF = 30, 60, 90 # Three 2-digit values for LCM = 10, 15, 30 # Therefore, a value of 30 was used for number of guests.LikeLike