Brain teaser 1000: One thousand down
From The Sunday Times, 20th September 1981 [link]
This auspiciously-numbered Brain-teaser has given my wife a chance to take stock of the teasers which she has tried over the years. When the Brain-teasers started to be numbered she did one of the early ones and took most of that Sunday over it. So she decided not to spend every Sunday on them, but only to do those teasers whose numbers were multiples of that first one she had tried.
This worked very well for a long time until one Sunday there was an exceptional teaser which she couldn’t resist doing, even though she had done the previous week’s. She so enjoyed doing that extra puzzle that she decided she would in future try precisely those teasers whose numbers were the sum of two numbers (possibly the same) of teasers which she had tried previously. She didn’t try last week’s, but she’ll be busy today trying this one. But the rest of us have suddenly realised with horror that we’re never going to get a decent Sunday lunch again, because my wife is going to have to do every Brain-teaser from now on.
(1) What was the first teaser which she tried?
(2) What was the number of that “exceptional teaser which she couldn’t resist”?
(3) How many of the first 1,000 Brain-teasers will she have tried?
[teaser1000]
John Crabtree are discussing. 
S2T2 
Jim Randell 2:37 pm on 30 May 2021 Permalink |
(See also: Enigma 1154, Enigma 1194, Enigma 228, Enigma 122).
If the first Teaser is number x, then she will try 2x, 3x, 4x, …. Until one day, having done kx she can’t resist also doing (kx + 1).
So we can consider this to be a “money changing” problem, using denominations of x and y = (kx + 1).
And the largest amount that cannot be expressed using these denominations is 999.
This is the Frobenius Number of the denominations:
And the number of amounts that are not expressible using the denominations is:
The following Python program runs in 53ms.
Run: [ @replit ]
from enigma import irange, div, printf F = lambda x, y: x * y - x - y N = lambda x, y: div((x - 1) * (y - 1), 2) # consider the first teaser x (< 100) for x in irange(2, 99): # and consider multiples of x < 1000 for kx in irange(2 * x, 997, step=x): y = kx + 1 if F(x, y) == 999: # output solutions n = 1000 - N(x, y) printf("(1) {x}; (2) {y}; (3) {n}")Solution: (1) The first Teaser she tried was number 5; (2) The Teaser she couldn’t resist was number 251; (3) She will have tried 500 of the first 1000 Teasers.
LikeLike
Jim Randell 4:59 pm on 30 May 2021 Permalink |
And the following program shows the numbers of the Teasers that were attempted:
from enigma import irange, printf (x, y) = (5, 251) # collect attempted teasers ns = set() # attempt teaser n def attempt(n): ns.add(n) printf("{n}" + ("" if len(ns) % 15 == 0 else " \\")) # consider increasing teaser numbers for n in irange(1, 1000): # start by doing multiples of x if n < y: if n % x == 0: attempt(n) elif n == y: # and then do y attempt(n) else: # and then any number that is the sum of two previous numbers if any(n - a in ns for a in ns): attempt(n) printf("\nattempted = {n}", n=len(ns))Output:
LikeLike
John Crabtree 9:54 pm on 31 May 2021 Permalink |
If y = n * x + 1, this leads to (x – 1) * n * x = 1000 = 2^3 * 5^3
And so x = 5, n = 50, y = 251, etc
LikeLike
Jim Randell 8:39 am on 1 June 2021 Permalink |
@John: A neat bit of analysis. It also provides the answer to (3) directly:
LikeLike