Brain-Teaser 33: Postal purchases
From The Sunday Times, 5th November 1961 [link]
A rectangular sheet of postage stamps (i.e., one with each row containing the same number of stamps) was sold in such a way that each successive customer bought either a complete row or a complete column, thereby leaving the sheet rectangular after each purchase.
The 2nd customer bought 6 stamps more than the 4th and half as many again as the 6th customer. The 5th customer bought twice as many stamps as the 12th. After the 7th customer had made his purchase exactly one-third of the original sheet had been sold.
What was the size of the original sheet of stamps? And what was the total number of stamps bought by the first 12 customers?
[teaser33]
Frits and 
John Crabtree, 
Hugh Casement, and 1 other are discussing. 
S2T2 
Jim Randell 9:21 am on 9 May 2021 Permalink |
(See also: Enigma 460).
This Python program runs in 51ms.
Run: [ @replit ]
from enigma import (irange, inf, printf) # make k purchases from an (x, y) rectangle def solve(k, x, y, t, ss=[]): # perform checks: n = len(ss) # the 2nd purchase is divisible by 3 and is greater than 6 if n == 2 and not (ss[1] > 6 and ss[1] % 3 == 0): return # the 4th purchase is the 2nd less 6 if n == 4 and not (ss[3] == ss[1] - 6): return # the 5th purchase is divisible by 2 if n == 5 and not (ss[4] % 2 == 0): return # the 6th purchase is (2/3) the 2nd if n == 6 and not (ss[5] * 3 == ss[1] * 2): return # after the 7th purchase 1/3 of the original sheet is sold if n == 7 and not (sum(ss) * 3 == t): return # the 12th purchase is half the 5th if n == 12 and not (ss[11] * 2 == ss[4]): return # are we done? if k == 0: yield ss else: if y > 1: # buy a row of x stamps yield from solve(k - 1, x, y - 1, t, ss + [x]) if x > 1: # buy a column of y stamps yield from solve(k - 1, x - 1, y, t, ss + [y]) # diagonal enumeration of (x, y) pairs, x > y def pairs(a, b): # consider the sum of the dimensions for t in irange(a, b): # values for y for y in irange(1, t // 2): yield (t - y, y) def run(): # consider (x, y) rectangles for (x, y) in pairs(12, inf): # attempt 12 purchases for ss in solve(12, x, y, x * y): yield (x, y, ss) for (x, y, ss) in run(): printf("x={x} y={y}: {ss} -> {t}", t=sum(ss)) breakSolution: The original sheet consisted of 21 × 18 stamps (= 378 stamps in total). Between them, the 12 customers purchased 208 stamps.
The individual purchases were (1st – 12th): 21, 21, 21, 15, 20, 14, 14, 18, 18, 18, 18, 10.
The following diagram shows one way the original sheet could have been sold. Each purchase is numbered, and the number of stamps bought is given in brackets.
Initially there are 378 stamps in the sheet.
After the first 7 purchases (shown in red) the yellow and green squares remain. A total of 252 stamps, which is 2/3 of the original 378 stamps, so 1/3 have been sold.
After all 12 purchases (red and yellow) only the green squares remain. A total of 170 stamps, so 208 stamps have been sold in all.
LikeLike
Frits 10:41 am on 1 June 2021 Permalink |
You can already skip (x, y) combinations in run() if x * y is not a multiple of 3.
LikeLike
Frits 11:20 am on 2 June 2021 Permalink |
Only one (x, y) rectangle is possible (without even considering purchases as the 6th).
Second question is not dealt with.
from enigma import irange # the 2nd purchase is divisible by 3 and is greater than 6 # the 4th purchase is the 2nd less 6 # the 5th purchase is divisible by 2 # the 6th purchase is (2/3) the 2nd # after the 7th purchase 1/3 of the original sheet is sold # the 12th purchase is half the 5th # diagonal enumeration of (x, y) pairs, x > y def pairs(a, b): # consider the sum of the dimensions for t in irange(a, b): # values for y for y in irange(1, t // 2): yield (t - y, y) for (x, y) in pairs(12, 196): # assume x < 100 # consider x, y with y + 3 <= x <= y + 7 (purchase 2 and 4 rules) # and x % 3 != 2 (purchase 2 rule) # purchase 7 rule makes x * y a multiple of 3 if (x * y) % 3 or x < y + 3 or x > y + 7 or x % 3 == 2: continue # 2nd purchase comes from initial long side # 4th purchase comes from initial short side for a in range(1, 7): b = 7 - a # after the 7th purchase 1/3 of the original sheet is sold if (x - a) * (y - b) * 3 != 2 * (x * y): continue # if only 2nd purchase made from initial long side (b = 1) if b == 1: # 1st purchase is made from the initial short side if (x - 1) % 3: continue # if y is odd then the 5th purchase is odd, impossible if y % 2: continue # purchases 3 - 7 must be equal to 2nd purchase - 6 (and even) # so 2nd purchase must be even as well if x % 2: continue # if only 4th purchase made from initial short side (a = 1) if a == 1: # x must be three higher than y (the 4th purchase is the 2nd less 6) if x != y + 3: continue # if initial long side is a multiple of 3 if x % 3 == 0: # the 1st purchase must be made from the long side # after the first 2 purchases the short side has decremented with 2 if x > y + 4: continue # 4th purchase rule if x == y + 4: # the 3rd purchase must be made from the initial short side # (difference between sides may not become higher than 6) # so both sides after 4 purchases have decremented with 2 if x % 2 and y % 2: continue # 5th purchase must be even print(f"{(x, y) = } {(a, b) = } remaining {(x - a), (y - b) = }") # (x, y) = (21, 18) (a, b) = (3, 4) remaining (x - a), (y - b) = (18, 14)LikeLike