Want to share your content on R-bloggers? click here if you have a blog, or here if you don’t.
From Henry Dudeney’s “Perplexities” article in the March 1925 issue of The Strand Magazine:
A man went into a bank with 1,000 silver dollars and 10 bags. He said, “Place this money, please, in the bags in such a way that if I call and ask for a certain number of dollars you can hand me over one or more bags, giving me the exact amount called for without opening any of the bags.” How was it to be done? We are, of course, only concerned with a single application, but he may ask for any exact number of dollars from 1 to 1000.
(In the original article it was “sovereigns” and “pounds”—but I’m in the U.S., so…)
This is similar in spirit to Bachet’s Four Weights Problem, so if you’ve solved that one, you should certainly be able to solve this one.
The solution is below Chirico’s The Mathematicians.
The Solution
Unlike the weights problem, the combination of bags here is strictly additive:
where 
So instead of a trinary system, we have a good old binary system. This means if we have 
ith bag, we can represent any value between 0 and 
Let’s show that with 3 bags, which should give us the numbers 0:7.
# fill the bags
bags = vapply(1:3, function(i) {2^(i-1)}, numeric(1))
bags
# get all the possible combinations of bags
signs = c(0,1)
S = expand.grid (s1 = signs,
s2 = signs,
s3 = signs) |>
as.matrix()
S
s1 s2 s3 [1,] 0 0 0 [2,] 1 0 0 [3,] 0 1 0 [4,] 1 1 0 [5,] 0 0 1 [6,] 1 0 1 [7,] 0 1 1 [8,] 1 1 1
# get the total number of coins for each combination as.numeric(S %*% bags)
We have 10 bags, so we can represent any value from 0 to 
So the solution is: The first 9 bags hold
Let’s verify that.
# fill the bags
bags = vapply(1:10, function(i) {2^(i-1)}, numeric(1))
bags[10] = 489 # the last bag is a little short.
# get all the possible combinations of bags
slist = lapply(1:10, function(i) signs)
names(slist) = paste0("bag", 1:10)
S = expand.grid (slist) |> as.matrix()
dim(S)
Note that there are still 1024 combinations of bags; we know that we can only represent the numbers 0:1000, so some of the totals will be duplicated. In other words, for some numbers, there are multiple combinations of bags that give the same sum.
# get the total number of coins for each combination x = as.numeric(S %*% bags) # find all the unique values we can achieve x_unique = sort(unique(x)) # confirm that this gives us every value from 0 to 1000 stopifnot(x_unique==0:1000)
So we have achieved the customer’s ask, and the banker is no longer perplexed!
We can go a little further. Which sums can be achieved multiple ways?
x[duplicated(x)]
[1] 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 [20] 508 509 510 511
Note that 489 is the number of coins in bag10, and 511 is 
For fun, let’s see the different ways to achieve x = 500:
ix = which(x==500) S[ix, ]
bag1 bag2 bag3 bag4 bag5 bag6 bag7 bag8 bag9 bag10 [1,] 0 0 1 0 1 1 1 1 1 0 [2,] 1 1 0 1 0 0 0 0 0 1
The first solution is the “standard” solution, meaning 500 encoded in binary (backwards). The second solution is because our last bag doesn’t have the correct number of coins in it, and in fact contains fewer than 500 coins. You can tell it’s not the standard answer because we use bag 1, meaning the answer appears to be odd. But this evens out, because bag10 has an odd number of coins in it.
Nina Zumel is a data scientist based in San Francisco, with 20+ years of experience in machine learning, statistics, and analytics. She is the co-founder of the data science consulting firm Win-Vector LLC, and (with John Mount) the co-author of Practical Data Science with R, now in its second edition.
Related
