Teaser 2993: Baker’s weights
From The Sunday Times, 2nd February 2020 [link] [link]
A baker’s apprentice was given a 1kg bag of flour, scales and weights, each engraved with a different whole number of grams. He was told to separately weigh out portions of flour weighing 1g, 2g, 3g, and so on up to a certain weight, by combining weights on one side of the scales. He realised that he couldn’t do this if there were fewer weights, and the largest weight was the maximum possible for this number of weights, so he was surprised to find after one of these weighings that the whole bag had been weighed out. Upon investigation, he discovered that some of the weights weighed 1g more than their engraved weight. If I told you how many of the weights were too heavy, you would be able to work out what they all were.
What were the actual weights (in ascending order)?
[teaser2993]
Robert Brown are discussing. 
S2T2 
Jim Randell 8:24 am on 1 February 2020 Permalink |
When I first read the puzzle it didn’t seem to make any sense, or have a solution.
So I set about investigating the parts of the text that are unambiguous:
With k weights we can make (2^k − 1) different non-empty collections of weights. Using weights that are powers of 2 (i.e. 1g, 2g, 4g, 8g, …) allows us to weigh all the amounts between 1 and (2^k − 1).
So we can start weighing out increasing amounts, look at what weights have been used and look at when a collection of mislabelled weights would bring the total amount weighed out to exactly 1000g.
This Python program runs in 77ms.
Run: [ @replit ]
from enigma import (multiset, irange, inf, subsets, nsplit, ordered, call, filter_unique, item, printf) # record possible solutions: # (<number of weighings>, <number of mislabelled weights>, <sequence of weights>) ss = list() # record the labels of the weights used s = multiset() # consider possible number of weighings, and total expected amount weighed out t = 0 for n in irange(1, inf): t += n if t > 1000: break # calculate the required weights ws = list(2 ** i for (i, m) in enumerate(reversed(nsplit(n, base=2))) if m) printf("{n} -> {t}; {ws}") # add in the weights s.update_from_seq(ws) assert t == sum(k * v for (k, v) in s.items()) # now consider a subset of the weights that actually weigh 1g more than labelled for xs in subsets(s.keys(), min_size=1): # the total extra weight being... x = sum(s[x] for x in xs) # does this bring the total to exactly 1kg? if t + x == 1000: k = len(xs) printf(" -> {xs}; +{x}; {k}") ss.append((n, k, call(ordered, (w + (w in xs) for w in s.keys())))) # find solutions unique by the number of mislabelled weights (= item 1) for (n, k, ws) in filter_unique(ss, item(1)).unique: # output solutions printf("n={n} k={k} ws={ws}")Solution: The actual weights were: 2g, 3g, 5g, 9g, 17g, 32g.
So the apprentice has a set of six weights, labelled: 1g, 2g, 4g, 8g, 16g, 32g. Which, if correct, could be used to weigh any integer amount between 1g and 63g.
However, five of the weights are mislabelled. The 1g, 2g, 4g, 8g, 16g weights all weigh 1g more than their label suggests.
After the apprentice has weighed out amounts corresponding to 1g, 2g, 3g, …, 42g using the weights he would expect to have used 903g of flour, but with this set of weights he has actually used a total of 1000g of flour.
The apprentice may have set out to make weights up to 42g (expecting to use 903g of flour), up to 43g (expecting to use 946g of flour), or up to 44g (expecting to use 990g of flour). For higher amounts 1000g of flour would not be enough to complete the task.
There are also potential solutions when apprentice gets to 43g. With the set of six weights he would expect to have weighed out 946g of flour. But there are four combinations of 3 mislabelled weights, which would bring the total to exactly 1000g. (If the (1, 4, 32), (1, 8, 32), (2, 4, 32) or (2, 8, 32) weights are mislabelled).
But we are told that if we knew the number of mislabelled weights we could work out the actual weights in the set. So we must be dealing with the case where 5 of the weights are mislabelled.
The most reasonable scenario seems to be that apprentice was given a 1kg bag of flour and a set of 6 weights, labelled: 1g, 2g, 4g, 8g, 16g, 32g, and asked to weigh out amounts from 1g to 44g.
The total amount to be weighed out is T(44) = 990g, so he would be expecting to have 10g of flour left at the end.
However, after one of the weighings he has used up exactly 1000g of flour (assuming the bag of flour was actually 1000g in the first place).
There 5 ways this can happen:
We are told that if we knew the number of mislabelled weights we could work out which they were, so we must be dealing with the first situation with 5 mislabelled weights.
LikeLike
Robert Brown 8:45 pm on 1 February 2020 Permalink |
He’s told to weigh portions up to a certain weight, must be <=44 as that uses 990g of flour. Binary set of weights goes up to 63g, so some of the weights could be smaller. Text says 'the largest weight was max possible for this number of weights' – I took this to mean there's a weight engraved 32g, but others seem to think it means the largest portion was the max possible for this number of weights. We all get the same answer, but using my method I didn't need to be told how many of the weights were too heavy. Does your program incorporate this?
LikeLike
Jim Randell 8:59 pm on 1 February 2020 Permalink |
@Robert: I originally thought “the largest weight was the maximum possible for this number of weights” would refer to the largest portion that the apprentice was to weigh out. So it would have to be 31g (with 5 weights) or 63g (with 6 weights), but neither of these can give a solution.
In the end I assumed that the set of weights used was labelled as powers of 2 (i.e. 1g, 2g, 4g, 8g, …), and then used the program to look for amounts where we would expect (if the weights were correctly labelled) to have weighed out a cumulative amount less than 1000g, but if some of the weights were 1g heavier than labelled the cumulative amount is actually exactly 1000g.
I found one set with 5 mislabelled weights where this happens, and four sets with 3 mislabelled weights.
The puzzle text says if we knew the number of mislabelled weights we would know what the actual set of weights was, so the answer we want is the the set with 5 mislabelled weights.
I think the wording of the puzzle could have been clearer.
LikeLike
Robert Brown 3:49 pm on 3 February 2020 Permalink |
Jim: I agree with everything that you say, but Brian Gladman seems to think “the largest weight etc” refers to the “certain weight” that the apprentice was told to use as a limit. He then thinks it’s reasonable to set this to 63g. But the person giving instructions to the apprentice would know this was impossible, as even with correct weight labels, the flour would run out after he weighed 44 portions. Of course we don’t know if that person was aware that some of the weights were wrong, which muddies the waters a bit. But Brian’s telling me that I’m effectively solving a different problem, but as far as I can see, it’s the same problem that you have solved.
In fact, the four sets with 3 mislabelled weights occur at weighing 43, while the the set with 5 mislabelled weights occur at weighing 42. So I discounted weighing 43, which means that I didn’t need to be told the number of mislabelled weights.
Because the weights we used can give up to 63g, I looked to see what alternatives could give every 1g step up to 44, and found 323 ways to do this, (if the 32g weight is omitted). Beyond my abilities to analyse all of these to see if there’s an alternative solution!
LikeLike
Jim Randell 9:46 am on 4 February 2020 Permalink |
I think that “the largest weight was the maximum possible for this number of weights” is a roundabout way of saying that that the weights are powers of 2. In a set of 6 (correctly labelled) weights this would mean that the largest weight was 32g, so the remaining 5 weights have to be able to weigh 1g-31g, which means they also have to be powers of 2.
Using a set of weights that is powers of 2, means that there is only one combination of weights that makes up any specific amount, so when looking for how many times each weight is used in the weighings there is a single answer. Otherwise we may have to consider multiple different ways to make up a specific amount, which could give us different actual weights. So I think this would be a much harder problem (and maybe not have a unique solution).
If we take “the largest weight was the maximum possible for this number of weights” to mean that the largest amount the apprentice was asked to weigh out was the largest possible for the number of weights, then if the set has 6 weights he would have been asked to weight out amounts up to 63g. This also implies that the set of weights is a “powers of 2” set. But also means that the apprentice was being set an impossible task. (Although there is a long tradition of sending apprentices on futile or impossible tasks, and as it turns out he has been given a doctored set of weights, so his task does indeed turn out to be impossible).
I think the most reasonable interpretation is that the apprentice was given a set of 6 weights, labelled 1g, 2g, 4g, 8g, 16g, 32g and asked to weigh out amounts up to 42g, 43g or 44g (but we don’t know which). Each of these would appear to be an achievable task.
As the apprentice weighs out the amounts he finds that the entire bag has been used up after one of the weighings. This is possible in one way after weighing out the 42g portion, and 4 ways after weighing out the 43g portion. We are told that if we knew the number of mislabelled weights, then we could work out which ones they were, so I think we need to take all these cases into account.
So I think the most reasonable scenario was that the apprentice was asked to weigh out amounts up to 44g, a task which initially looks possible, but depending on the actual set of weights means you would run out of flour after weighing the 42g or 43g portion, making it impossible to complete the task.
Of the 5 possible sets of weights that lead to exactly 1000g of flour being used before we get to the 44g weight, one of them involves 5 weights being doctored and four of them involved 3 of the weights being doctored. So the answer we want is the set with 5 weights.
LikeLike