Teaser 2541: Lotto luck
From The Sunday Times, 5th June 2011 [link]
Chris was lucky in the lotto, winning a whole number of pounds (under £ 5,000), which he shared with his five children. John got £ 1 more than a fifth of the total; Ciaran got £ 1 more than a fifth of the remainder. After Ciaran got his share, Fergal got £ 1 more than a fifth of the remainder, and after Fergal got his share, Brendan got £ 1 more than a fifth of what was left. After Brendan got his share, Chris gave Grainne £ 1 more than a fifth of what was left and kept the remainder (a whole number of pounds).
How much did Chris keep?
[teaser2541]
Hugo, 
John Crabtree are discussing. 
Frits, 
Ruud, and 
Pete Good are discussing. 
S2T2 
Jim Randell 8:36 am on 3 June 2025 Permalink |
For a starting amount X, the next child’s share is X/5 + 1, and the remainder is 4X/5 − 1.
Each of the shares and remainders must be an integer, because if we ever get a share that has a fractional part, then the fractional part of the remainder will be further subdivided into a smaller fraction. And as both the starting amount and the final remainder are whole numbers, then all the intermediate numbers are too.
The following Python program runs in 71ms. (Internal runtime is 3.7ms).
from enigma import (irange, ediv, printf) # calculate share and remainder from total X def calc(X): share = ediv(X, 5) + 1 return (share, X - share) # consider possible winnings for W in irange(1, 4999): # calculate share and remainder for each child try: (J, R) = calc(W) # John (C, R) = calc(R) # Ciaran (F, R) = calc(R) # Fergal (B, R) = calc(R) # Brendan (G, R) = calc(R) # Grainne except ValueError: continue # output solution printf("W={W} -> J={J} C={C} F={F} B={B} G={G} -> R={R}")Solution: Chris kept £ 1019.
The initial winnings were £ 3120, and they are distributed as:
It is easy to see that the initial amount won must be a multiple of 5, which allows us to skip 80% of the cases checked. (And brings the internal runtime down to 1.0ms).
And with further analysis we can get an even faster solution:
We find the remainder after step k is:
So after the shares for the 5 sons have been distributed we have:
where: 0 < R < W < 5000.
This is a Linear Diophantine Equation in 2 variables, and can be solved using the Extended Euclidean Algorithm [@wikipedia], implemented as [[
egcd()]] in the enigma.py library.Here is a general solver for this kind of equation:
from enigma import (egcd, div, divc) # solve linear diophantine equations in 2 variables: def diop_linear(a, b, c, mX=0, fn=0): """ solve the linear Diophantine equation a.X + b.Y = c for integers X, Y (where a, b are non-zero, and gcd(a, b) divides c). return ((X0, Y0), (Xd, Yd)) to give solutions of the form: (X, Y) = (X0 + t.Xd, Y0 + t.Yd) for integer t the value of X0 returned is the smallest integer possible above (or equal to) mX, and Xd is positive. however, if <fn> is set, then a function f: t -> (X, Y) is returned instead. """ if a == 0 or b == 0: raise ValueError("diop_linear: invalid equation") (X, Y, g) = egcd(a, b) if g > 1: (a, b, c) = (a // g, b // g, div(c, g)) if c is None: raise ValueError("diop_linear: no solutions") # calculate particular solution (X0, Y0) and deltas (Xd, Yd) (X0, Y0) = (c * X, c * Y) (Xd, Yd) = ((-b, a) if b < 0 else (b, -a)) # adjust X0 to be the smallest possible value t = divc(mX - X0, Xd) X0 += t * Xd Y0 += t * Yd if fn: return (lambda t: (X0 + t * Xd, Y0 + t * Yd)) return ((X0, Y0), (Xd, Yd))Which we can then use to solve the puzzle:
from enigma import (irange, inf, printf) # k = number of sons k = 5 # solve the Diophantine equation: 4^k W - 5^k R = 5(5^k - 4^k) (p4k, p5k) = (4**k, 5**k) fn = diop_linear(p4k, -p5k, 5 * (p5k - p4k), fn=1) # consider increasing solutions where 0 < W < 5000 for t in irange(0, inf): (W, R) = fn(t) if not (W < 5000): break if R < 0: continue # output solution printf("W={W} R={R}")This program has an internal runtime of just 35µs.
LikeLike
Hugo 10:54 am on 9 January 2026 Permalink |
A slightly different way of looking at it:
He borrows £5 from his wife, so the amount to be distributed is £3125 (= 5^5).
The eldest child gets a fifth of that, and each successive child four fifths as much as the previous child, being a fifth of what is left. He ends up with £1024 (= 4^5), from which he can repay his wife.
There are further solutions with an integer times as much, always including the borrowed £5.
If there were six children, the smallest solution would be £15625 (= 5^6),
if only four then £625 (= 5^4), in each case including the borrowed £5.
It’s not hard to come up with variants in which each child gets a quarter, or a sixth, or some other fraction of what is left.
LikeLike
John Crabtree 8:03 pm on 4 June 2025 Permalink |
This teaser is a variation of the Monkey and the Coconuts puzzle which Martin Gardner wrote about decades ago in his column in the Scientific American. The puzzle is older than that.
R[1] = 4W/5-1 = 4(W+5)/5 – 5
And so R[k] = 4^k (W + 5) / (5^k) – 5
R[5] = 1024(W+5) / 3125 – 5, and so (W+5) = 3125, and the answer follows.
LikeLike
Jim Randell 3:10 pm on 6 June 2025 Permalink |
A neat bit of analysis.
LikeLike