Teaser 3171: What’s happened to our chocolate bar?
From The Sunday Times, 2nd July 2023 [link] [link]
Father Christmas was rewarding his helpers (sprites, elves and fairies). He had 333 helpers, of whom 111 were elves.
He had 28 chocolate bars to give away in proportion to the size of the groups. If the groups’ shares were 9.5, 9.3 and 9.2 then they would actually receive 10, 9 and 9, because the bars can’t be split and the extra bar goes to the group with the highest remainder (for two extra bars, one each would go to the two groups with the highest remainders). In fact the sprites, elves and fairies received 7, 9 and 12 bars respectively.
“I’ve found another chocolate bar”, said Father Christmas, “so now the sprites, elves and fairies will receive 6, 10 and 13 bars respectively.”
“What’s happened to our chocolate bar?” asked the sprites.
How many sprites are there?
[teaser3171]
Tony Brooke-Taylor, and 
Frits are discussing. 
Pete Good, and 
GeoffR are discussing. 
Mark Valentine are discussing. 
S2T2 
Jim Randell 3:58 pm on 30 June 2023 Permalink |
What better time to run a Christmas themed puzzle?
See also: this Matt Parker video [@youtube]
This Python program runs in 61ms. (Internal runtime is 414µs).
from enigma import (decompose, item, first, printf) # distribute <k> bars among <ns> def distribute(k, ns): t = sum(ns) ds = list() # allocation rs = list() # (index, remainder) # initial allocation for (i, n) in enumerate(ns): (d, r) = divmod(n * k, t) ds.append(d) rs.append((i, r)) # distribute remaining bars k -= sum(ds) for (i, r) in first(sorted(rs, key=item(1), reverse=1), k): ds[i] += 1 return ds # total number of helpers T = 333 # number of elves E = 111 # choose the number of sprites and fairies for (S, F) in decompose(T - E, 2, increasing=1, sep=2, min_v=1): # calculate the distributions of 28 and 29 bars if distribute(28, [S, E, F]) != [7, 9, 12]: continue if distribute(29, [S, E, F]) != [6, 10, 13]: continue # output solution printf("S={S} E={E} F={F}")Solution: There are 76 sprites.
There are 76 sprites, 111 elves, 146 fairies (= 333 helpers in total).
With 28 chocolate bars the distribution is:
After allocating the 6, 9, 12 bars there is 1 bar left over, which goes to the sprites, as they have the largest remainder, giving a final allocation of 7, 9, 12 bars (28 in total).
With 29 the distribution is:
After allocating the 6, 9, 12 bars there are 2 bars left over, which go to the fairies and the elves, as they have the largest remainders, giving a final allocation of 6, 10, 13.
We can look at the “fairness” of the allocations by considering the amount of chocolate per helper.
If each bar weighs 100g, then in the first case there is 2800g of chocolate, and 333 helpers, so a completely fair allocation would be 8.41g per helper.
The actual allocations are:
So the sprites get an above average share this allocation, and the elves and fairies get below average.
In the second allocation there is 2900g of chocolate, giving a fair allocation of 8.71g per helper.
And the actual allocations are:
In this allocation the sprites get a below average share, and the elves and fairies get above average.
Manually:
Adding 1 bar to the total causes S’s proportion of the chocolate to go down and E’s and F’s proportions to go up. So in the first case there was 1 remaining bar which went to S, and in the second case there were 2 remaining bars which went to E and F.
In the first case the sum of the remainders come to 1 bar, so the largest remainder (S’s) must be more than 1/3:
In the second case the sum of the remainders come to 2 bars, so the smallest remainder (S’s) must be less than 2/3:
And the only value in these two ranges is: S = 76.
LikeLike
Jim Randell 11:21 am on 1 July 2023 Permalink |
Here is a different approach that calculates bounds on the population sizes of the different groups using the distributions of chocolate bars given in the puzzle text. It then tries population sizes within the calculated bounds to see which give the required distributions.
It also has an internal runtime of <1ms.
from enigma import (irange, inf, divc, divf, cproduct, item, first, printf) # distribute <k> bars among <ns> def distribute(k, ns): t = sum(ns) ds = list() # allocation rs = list() # (index, remainder) # initial allocation for (i, n) in enumerate(ns): (d, r) = divmod(n * k, t) ds.append(d) rs.append((i, r)) # distribute remaining bars k -= sum(ds) for (i, r) in first(sorted(rs, key=item(1), reverse=1), k): ds[i] += 1 return ds # find divisions of population <t> that give distributions <dss> def solve(t, dss): # calculate bounds for each group (mn, mx) = (dict(), dict()) for ds in dss: k = sum(ds) for (i, d) in enumerate(ds): # if this distribution was rounded up x = divc((d - 1) * t, k) if x > mn.get(i, 0): mn[i] = x # if this distribution was rounded down x = divf((d + 1) * t - 1, k) if x < mx.get(i, inf): mx[i] = x # choose populations for ns in cproduct(irange(mn[i], mx[i]) for i in sorted(mn.keys())): if sum(ns) != t: continue # check distributions if all(distribute(sum(ds), ns) == ds for ds in dss): yield ns # solve for the specified distributions for (S, E, F) in solve(333, [[7, 9, 12], [6, 10, 13]]): if E != 111: continue printf("S={S} E={E} F={F}")It turns out that the condition that E = 111 is not needed, as there is only one set of population sizes that gives the required distributions with the given total population size. (i.e. line 41 is optional).
Although knowing E = 111 allows a straightforward manual solution.
LikeLike
Frits 1:43 pm on 1 July 2023 Permalink |
Without using the mn and mx boundaries and E = 111 this program runs in 100ms.
I wonder if manual solvers would have an elegant way of solving if E = 111 was omitted.
from enigma import SubstitutedExpression # calculate distribution with population numbers <s> def dist(n, s, t): guaranteed = [(n * x) // t for x in s] n_leftovers = n - sum(guaranteed) remainders = sorted([((n * x) % t, i) for i, x in enumerate(s)]) # add leftovers to the people with the highest remainders for i in range(n_leftovers): guaranteed[remainders[2 - i][1]] += 1 return guaranteed # the alphametic puzzle p = SubstitutedExpression( [ "(total := 333)", "(sprites := ABC) < (elves := DEF)", "total - sprites - DEF = GHI", "elves < (fairies := GHI)", "dist(28, [sprites, elves, fairies], total) == [7, 9, 12]", "dist(29, [sprites, elves, fairies], total) == [6, 10, 13]", ], answer="sprites", d2i=dict([(k, "ADG") for k in range(4, 10)]), distinct="", env=dict(dist=dist), reorder=0, verbose=0, # use 256 to see the generated code ) # print answers for ans in p.answers(): print(f"answer: {ans}")@Jim, notice I had to postpone the assignment of fairies and that in the calculation of GHI I could use variables sprites or elves but not both of them.
LikeLike
Frits 2:54 pm on 1 July 2023 Permalink |
or without GHI
# the alphametic puzzle p = SubstitutedExpression( [ "total := 333", "(sprites := ABC) < (elves := DEF)", "fairies := total - sprites - elves", "elves < fairies", "dist(28, [sprites, elves, fairies], total) == [7, 9, 12]", "dist(29, [sprites, elves, fairies], total) == [6, 10, 13]", ], answer="sprites, elves, fairies", d2i=dict([(k, "AD") for k in range(2, 10)]), distinct="", env=dict(dist=dist), reorder=0, verbose=0, # use 256 to see the generated code )LikeLike
Tony Brooke-Taylor 11:25 am on 2 July 2023 Permalink |
I think it is possible to infer bounds for the number of sprites without knowing 111, simply by recognising that with 28 bars, the sprites have the largest remainder (implying > 1/3) while with 29 bars, the sprites have the smallest remainder (implying < 2/3). Only 1 integer value for the number of sprites fits between these bounds.
LikeLike
Jim Randell 11:41 am on 2 July 2023 Permalink |
@Tony: Very neat.
LikeLike
Frits 6:51 pm on 30 June 2023 Permalink |
Not many iterations.
T, E, N = 333, 111, 28 RS = [[7, 9, 12], [6, 10, 13]] # in 1st round the sprites win against the elves # N.S / T > RS[1][0] + 1/3 # in 2nd round the sprites lose against the elves # (N + 1).S / T < RS[1][0] + 2/3 for s in range((RS[1][0] * T + T // 3) // N + 1, (RS[1][0] * T + 2 * T // 3) // (N + 1) + 1): f = T - E - s # play 2 rounds for rnd in range(2): n = N + rnd guaranteed = [(n * x) // T for x in (s, E, f)] n_leftovers = n - sum(guaranteed) remainders = sorted([((n * x) % T, i) for i, x in enumerate([s, E, f])]) # add leftovers to the people with the highest remainders for i in range(n_leftovers): guaranteed[remainders[2 - i][1]] += 1 # check with actual distribution if guaranteed != RS[rnd]: break else: # no break print("answer:", s)LikeLike