Teaser 2566: A fulfilling strategy
From The Sunday Times, 27th November 2011 [link]
I drove down a road with a number of petrol stations whose locations I saw on my map. I decided to check the price at the first station then fill up when I found one offering a lower price (or, failing that, the last one).
When I got home I noticed that I could arrange the prices (in pence per per litre) into an ascending sequence of consecutive whole numbers of pence, plus 0.9p (i.e. 130.9p, 131.9p, 132.2p, etc). I also worked out the average price that I would expect to pay using this strategy, if I were to encounter this set of prices in an unknown order, and I was surprised to find that this value turned out to be a whole number of pence per litre.
How many petrol stations were there?
When the puzzle was originally published in The Sunday Times it had been edited into a form that meant there were no solutions. Here I have rephrased the middle paragraph so that it works as the setter originally intended.
[teaser2566]
Robert Brown are discussing. 
GeoffR and 
John Crabtree and 
Jim Randell 8:12 am on 2 June 2020 Permalink |
(See also: Teaser 2988).
Here is a program that calculates the result directly. It runs in 50ms.
Run: [ @repl.it ]
from enigma import subsets, irange, inf, factorial, div, printf # strategy, take the first amount lower than the first n items def strategy(s, n): t = min(s[:n]) for x in s[n:]: if x < t: break return x # play the game with k items def play(k): # collect total amount t = 0 # consider possible orderings of the items ps = list(1299 + 10 * p for p in irange(1, k)) for s in subsets(ps, size=k, select="P"): t += strategy(s, 1) return t # consider numbers of items for k in irange(2, inf): t = play(k) # calculate the average expected price (in 10th pence) d = factorial(k) p = div(t, d) if p is not None and p % 10 == 0: printf("k={k} -> p={p}") breakSolution: There were 5 petrol stations.
And the expected average fuel price was 132.0 pence.
It doesn’t actually matter what the prices actually are, all the petrol stations could adjust their prices by the same whole number of pence, and the expected average price would be adjusted by the same amount.
Analytically:
As determined in Teaser 2988 we can use the formula:
To determine the mean expected value of choosing from k boxes with values from 1..k, using the strategy of picking the next box that is better than any of the first n boxes (or the last box if there are no boxes better than the first).
In this case n = 1:
If we award ourselves a prize of value k for selecting the cheapest fuel, and a prize of value 1 for selecting the most expensive fuel, then we have the same situation as in Teaser 2988, and if p is expected average prize value, then the corresponding expected average fuel price is (130.9 + k – p).
And k is an integer, so in order to make the expected average fuel price a whole number of pence we are looking for expected average prize value that is an integer plus 0.9.
i.e. when the value of 10 S(1, k) is an integer with a residue of 9 modulo 10.
When k is odd, the first part gives us a whole number, so we would also need the (5 / k) part to give a whole number. i.e. k = 1, 5.
When k is even, the first part gives us an odd number of halves, so we also need (5 / k) to give an odd number of halves. i.e. k = 2, 10.
And we are only interested in values of k > 1, so there are just 3 values to check:
The only value for k that gives a residue of 9 modulo 10 is k = 5.
And in this case our expected average prize is p = 3.9 so our expected average fuel price is 132.0 pence.
LikeLike