Teaser 1849: Losing a daughter
From The Sunday Times, 22nd February 1998 [link]
“I’ll be pleased to get rid of her!”, exclaimed George, as he and Martha worked out the seating plan for the wedding of their youngest daughter. The 50 guests were to be seated at seven tables (numbered 1 to 7), each table seating at least six but not more than eight. Alter long arguments as to who should be avoiding whom, they came up with a plan. “That’s strange”, commented Martha. “If you take the number at each table and multiply it by the table number and then add the seven products, you get a perfect square — highly inappropriate when all the tables are round!”. George rang the caterer, who was familiar with the details, and told him about this “square” property as well as the number of people to be seated on table 7. “Then the same number of people will be at table 1″, said the caterer”. “Yes”, confirmed George.
How many were to be seated on table 6?
[teaser1849]
GeoffR, 
Frits, 
Lise Andreasen, 
S2T2 
Jim Randell 10:02 pm on 24 April 2024 Permalink |
This Python program generates all possible arrangements with the “square” property.
And then looks for those which would allow the caterer to deduce the number of guests at table 1, having been told the number of guests at table 7. We then examine the cases where these numbers are equal.
The program runs in 53ms. (Internal runtime is 1.5ms).
from enigma import (decompose, is_square, filter_unique, item, map2str, printf) # generate possible configurations with the "square" property def generate(): # distribute the 50 guests among the 7 tables for ns in decompose(50, 7, increasing=0, sep=0, min_v=6, max_v=8): # map table numbers to the number of guests seated m = dict(enumerate(ns, start=1)) # check the "square" property if is_square(sum(i * n for (i, n) in m.items())): yield m # knowing the number at table 7 the caterer deduces the number at table 1 for m in filter_unique(generate(), item(7), item(1)).unique: # is it the same number? if m[1] == m[7]: # output solution printf("m[6]={m[6]} [m={s}]", s=map2str(m))Solution: 6 guests were to be seated at table 6.
There are three possible arrangements (table number = number of guests):
In each case the “square” property gives a value of 196 (= 14²).
LikeLike
ruudvanderham 11:25 am on 25 April 2024 Permalink |
Here’s my (brute force) solution:
import itertools import math import collections number_at_table1_per_number_at_table7 = collections.defaultdict(set) number_at_table6_per_number_at_table7 = collections.defaultdict(set) for number_at_table in itertools.product((6, 7, 8), repeat=7): if sum(number_at_table) == 50: total = sum(i * n for i, n in enumerate(number_at_table, 1)) if math.sqrt(total) % 1 == 0: number_at_table1_per_number_at_table7[number_at_table[6]].add(number_at_table[0]) number_at_table6_per_number_at_table7[number_at_table[6]].add(number_at_table[5]) for i in number_at_table1_per_number_at_table7: if len(number_at_table1_per_number_at_table7[i]) == 1: # unique! print(number_at_table6_per_number_at_table7[i])LikeLike
Frits 2:18 pm on 25 April 2024 Permalink |
Allowing for more than one solution.
sign = lambda x: -1 if x < 0 else x > 0 # return a list of items grouped by element <by> grpby = lambda s, by: [[x for x in s if x[by] == v] for v in set(x[by] for x in s)] # decompose number <t> into <k> numbers from <ns> times -1, 0 or 1 so that # sum(<k> numbers) equals <t> and with the count of positive numbers # one higher than the count of negative numbers def decompose2(t, k, ns, s=[], delta=0): if k == 1: if abs(t) in ns or t == 0: if delta + sign(t) == 1: yield s + [t] else: for m in [-1, 0, 1]: n_ = m * ns[0] # can we get to delta = 1 in k - 1 moves if abs(delta + m - 1) <= k - 1: yield from decompose2(t - n_, k - 1, ns[1:], s + [n_], delta + m) # 7 * tri(7) = 14^2 and 14^2 is the only feasible square. # if we substract 7 from the number of guests per table we have a list of # -1, 0 and 1. Making sure all these -1/0/1 items sum to zero we end up with # square 14^2 and having one more postive than negative number guarantees # 50 people at 7 tables. # group by table 7 for g in grpby(list(decompose2(0, 7, range(1, 8))), -1): # group by table 1 if len(g2 := grpby(g, 0)) != 1: continue print("answer:", ' or '.join(set(str(7 + sign(x[-2])) for x in g2[0])))LikeLike
GeoffR 6:15 pm on 25 April 2024 Permalink |
As shown, this program gave four potential solutions, which need some manual filtering, as this facilty does not seem available in MiniZinc.
Of the four solutions output, the 2nd and 4th solutions can be discounted, as they have different values for Table No. 6.
The 1st and 3rd solutions have equal numbers of guests on Tables 1 and 7, albeit different, but the same number of 6 guests on Table 6.
Therefore, number of guests on Table 6 = 6.
LikeLike