Teaser 2913: Return tickets
From The Sunday Times, 22nd July 2018 [link]
In our tombola the tickets were numbered consecutively from 1 upwards and were printed in books of 20. A local airline donated the prizes – a number of tickets to Paris and back. We decided to split the prizes into single-journey tickets and award them in an unusual way. If any ticket number had all different digits which were in increasing order then it won an outward flight to Paris: if it had all different digits which were in decreasing order then it won a flight back from Paris. So, for example, number 145 won an outward flight, number 30 won a flight back, and single-figure numbers were lucky enough to win tickets there and back. Luckily we had exactly the right number of tickets for all the prizes to be awarded.
How many tickets did we print?
[teaser2913]
Jim Randell 5:21 pm on 11 May 2019 Permalink |
I originally wrote a program that just considers increasing ticket numbers until it finds a solution, but the Python program below finds all possible answers for a specified number of tickets per book (which can be given as a command line argument).
It does this by collecting increasing and decreasing numbers, and then considering them in order. It runs in 87ms.
Run: [ @repl.it ]
from enigma import subsets, irange, nconcat, arg, printf # k tickets per book k = arg(20, 0, int) printf("[{k} tickets per book]") # collect increasing and decreasing numbers (actually, we only need max_size=4) incs = set(nconcat(s) for s in subsets(irange(0, 9), min_size=1, max_size=9) if s[0] != 0) decs = set(nconcat(s) for s in subsets(irange(9, 0, step=-1), min_size=1, max_size=9) if s != (0,)) # find when the increasing and decreasing totals are the same ninc = ndec = 0 s = None for t in sorted(incs.union(decs)): if t in incs: ninc += 1 if t in decs: ndec += 1 if s: (t0, n) = s t1 = t - 1 # look for answers in the range [t0..t1] ans = list(x for x in irange(t0, t1) if x % k == 0) printf("tickets = 1 - {t0}..{t1} [incs = decs = {n}] ans={ans}", t1=t - 1) s = None if ninc == ndec: s = (t, ninc)Solution: 1480 tickets were printed.
It turns out there are no solutions larger than 8519, so a basic search of ticket numbers can stop there (and give a program that finds all possible solutions), and so the code above need only consider numbers of up to 4-digits.
8519 is divisible by 7 and 1217. With 7 tickets per books have solutions with 7, 1484, 8512, 8519 tickets. With 1217 tickets per book the only solution is 8519 tickets.
LikeLike