Sunday Times Teaser 2993 – Baker’s Weights

by Peter Good

Published February 02 2020 (a palindrome 02-02-2020!) (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)?

5 Comments Leave one →

Brian Gladman permalink


from collections import Counter
from itertools import product

# for storing possible solutions
d2s = dict()

# for accumulating the total weight of the sequence
# of weighings
seq_wght = 0

# for accumulating the number of times each weight
# (1, 2, 4, ...) is used in weighing the sequence
wght_use_cnt = Counter()

# the maximum weight in the sequence of weighings
for max_wght in range(1, 46):
  
  # update the total sequence weight and number of times
  # each weight is used in weighing the sequence
  seq_wght += max_wght
  t = f"{max_wght:b}"[::-1]
  wght_use_cnt += Counter(i for i, d in enumerate(t, 0) if d == '1')
  
  # look for a subset of the weights used which will add the
  # weight needed to reach 1Kg if they are 1 gram overweight
  for m in product((0, 1), repeat=len(wght_use_cnt)):
    exw = sum(p * wght_use_cnt[i] for i, p in enumerate(m))
    if seq_wght + exw == 1000:
  
      # find the new weights and store this solution
      # indexed on the number of weights (if unique)
      wts = tuple(2 ** i + m for i, m in enumerate(m))      
      sm = sum(m)
      d2s[sm] = None if sm in d2s else (max_wght, wts)
 
# look for a number of overweight weights that is unique 
for m in d2s.keys():
  if d2s[m]:
    wts = ', '.join(str(x) for x in d2s[m][1])
    f, s, l = str.rpartition(wts, ', ')
    print(f"The weights are {f} and {l} grams (weighing 1..{d2s[m][0]} grams).")

from collections import Counter

from itertools import product

# for storing possible solutions

d2s = dict()

# for accumulating the total weight of the sequence

# of weighings

seq_wght = 0

# for accumulating the number of times each weight

# (1, 2, 4, ...) is used in weighing the sequence

wght_use_cnt = Counter()

# the maximum weight in the sequence of weighings

for max_wght in range(1, 46):

# update the total sequence weight and number of times

# each weight is used in weighing the sequence

seq_wght += max_wght

t = f"{max_wght:b}"[::-1]

wght_use_cnt += Counter(i for i, d in enumerate(t, 0) if d == '1')

# look for a subset of the weights used which will add the

# weight needed to reach 1Kg if they are 1 gram overweight

for m in product((0, 1), repeat=len(wght_use_cnt)):

exw = sum(p * wght_use_cnt[i] for i, p in enumerate(m))

if seq_wght + exw == 1000:

# find the new weights and store this solution

# indexed on the number of weights (if unique)

wts = tuple(2 ** i + m for i, m in enumerate(m))

sm = sum(m)

d2s[sm] = None if sm in d2s else (max_wght, wts)

# look for a number of overweight weights that is unique

for m in d2s.keys():

if d2s[m]:

wts = ', '.join(str(x) for x in d2s[m][1])

f, s, l = str.rpartition(wts, ', ')

print(f"The weights are {f} and {l} grams (weighing 1..{d2s[m][0]} grams).")

Erling Torkildsen permalink


from itertools import product

# N(T, W) returns how many times weight W in [1, 2, .., 32]
# is used in T weighings (formula created by J. Crabtree).
def N(T, W):
  return (T - T % (2 * W)) // 2 + max(0, T % (2 * W) - W + 1)

# rw(s, t) returns the real mass of flour weighed by use 
# of weights given by s, after t weighings.
def rw(s, t):
  return t * (t + 1)//2 + sum(N(t, 2 ** i) * s[i] for i in range(6))

# for solutions based on the number of overweight weights
d = dict()

# Consider all possible arrangements of overweight weights
for y in product((0, 1), repeat=6):
  for t in range(40, 46):
    if rw(y, t) == 1000:
      wts = tuple(2 ** i + y[i] for i in range(6))
      d[sum(y)] = None if sum(y) in d else wts

for wts in d.values():
  if wts != None:
    print(f"The weights (in grams) are {wts}")

from itertools import product

# N(T, W) returns how many times weight W in [1, 2, .., 32]

# is used in T weighings (formula created by J. Crabtree).

def N(T, W):

return (T - T % (2 * W)) // 2 + max(0, T % (2 * W) - W + 1)

# rw(s, t) returns the real mass of flour weighed by use

# of weights given by s, after t weighings.

def rw(s, t):

return t * (t + 1)//2 + sum(N(t, 2 ** i) * s[i] for i in range(6))

# for solutions based on the number of overweight weights

d = dict()

# Consider all possible arrangements of overweight weights

for y in product((0, 1), repeat=6):

for t in range(40, 46):

if rw(y, t) == 1000:

wts = tuple(2 ** i + y[i] for i in range(6))

d[sum(y)] = None if sum(y) in d else wts

for wts in d.values():

if wts != None:

print(f"The weights (in grams) are {wts}")

GeoffR permalink

Hi Erling

I noticed you are using a fairly narrow range to look for a solution
when you say you are considering all possible arrangements of weights:

in line 19: ie for t in range(40, 46):

Is there a logical reason why these limits are used and should it not be apparent with a comment in your code?

Geoff

Reply
- Erling Torkildsen permalink
  
  Hi Geoff
  
  Thanks for commenting.
  
  ‘All possible arrangements of weights’ refers to all the 64 possible combinations of normal and overweight weights. From (1g, 2g, 4g, 8g, 16g, 32g) -> (2g, 3g, 5g, 9g, 17g, 33g). All possible number of weighings are not considered. That is justified by the fact that the largest number of weigings to empty the bag of flour occurs when all weights are normal (former case) and smallest when all weights are overweight (latter case).
  By the function rw(s, t), defined in line 11-12, we have rw((0, 0, 0, 0, 0, 0), 44) = 990 and rw((1, 1, 1, 1, 1, 1), 41) = 966, and in both cases, for the next value of t the real weights exceed 1000. And as the values increase monotonically, the range you refer to, in fact, could have been set even narrower.
  (To be honest, I had those values in a spreadsheet before I wrote the programme, and that is where I (by convenience) get them from now. But that does not alter the justification above.)
  
  Erling
  
  Reply
- Erling Torkildsen permalink
  
  PS: To Geoff: Forgot to mention that I accept the critic that it should have been justified by a comment in the code.
  
  Reply

Sunday Times Teaser 2993 – Baker’s Weights

by Peter Good

Published February 02 2020 (a palindrome 02-02-2020!) (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta