The Riddler: King Auric (June 19, 2020)

Solution

First some observations:

A sphere’s weight is proportional to the cube of the diameter (with a constant = $\pi$/6), so for simplicity we will be working with the sequence $1^3, 2^3, 3^3, \dots$
Since we are working with integer weights now, the sum of all spheres weights must be divisible by 3.
Looking at the start of the sequence, we see that the largest sphere is too heavy, so a further condition is that the largest sphere’s weight must be less than or equal to 1/3 of the total weight.

We look at the first several possible collections of spheres, to see when condition (3) becomes satisfied:

From the plot we see that the minimal possible number of spheres in the set is 11.

Now, in addition to the above conditions, we must be able to split the set into 3 subsets of equal total weight. To check that, let’s try a “brute-force” approach:

For a given number of spheres $n$, the total spheres’ weight in each of the 3 subsets must be equal to $\frac{1}{3}\sum_{x=1}^nx^3$. We can go through all $2^n$ possible subsets and calculate the total weight for each. If this weight matches the above value, we call it a “good” subset. Then we’d keep only those $n$’s for which the number of good subsets is at least 3.

Here is a function that would find all good subsets for a given $n$:

goodSubsets <- function(n) {
  spheres <- seq_len(n)^3
  total <- sum(spheres)
  share <- total/3
  
  # generate all possible combinations
  subsets <- expand.grid(rep(list(c(TRUE, FALSE)), n))
  # calculate possible sums and check if their total weight is equal to `share`
  subsets[(apply(subsets, 1, function(row) sum(spheres[row]))) == share, ]
}

We run it on our candidate $n$’s: $11, 12, 14, 15, 17, \dots$ until we have at least 3 subsets:

possibleN <- dat$diams[dat$possible & dat$diams>=11]
idx <- 1
while(nrow(goodSubsets(possibleN[idx])) < 3)
  idx <- idx + 1
possibleN[idx]

## [1] 17

So now we know that there must be at least 17 spheres in the set. Here are the numbers of good subsets for the first several possible set sizes:

possibleN <- tail(possibleN, -idx+1)
nSubsets <- sapply(possibleN, function(n) nrow(goodSubsets(n)))
knitr::kable(data.frame(n = possibleN, `good subsets` = nSubsets))

n	good.subsets
17	12
18	23
20	33
21	42
23	110
24	163

The next step is to check whether any 3 of the “good” subsets form a partition of the set. We apply a “brute-force” again here: we list all possible combinations of 3 subsets out of all good subsets, and check for each such combination whether it forms a partition. We apply this algorithm for the remaining candidate $n$’s: $17, 18, 20, 21, 23, \dots$ until we find a match (hoping it will not take too long…):

findPartition <- function(n) {
  cmb <- goodSubsets(n)
  combs <- combn(nrow(cmb), 3)  # all possible combinations
  which(apply(combs, 2, function(x) all(colSums(cmb[x, ]) == 1))) # find which ones are partitions
}
 
idx <- 1
while(!length(partitionIdx <- findPartition(possibleN[idx])))
  idx <- idx + 1
finalN <- possibleN[idx]

We get our match at $n = 23$!

And the partition is the following:

spheres <- seq_len(finalN)^3
subsets <- goodSubsets(finalN)
combs <- combn(nrow(subsets), 3)  # all possible combinations of 3 subsets

out <- apply(subsets[combs[, partitionIdx], ], 1, function(x) spheres[as.logical(x)]^(1/3))
cat(paste0(1:3, ". ", lapply(out, paste, collapse = " "), collapse = "\n"))

2 5 9 11 14 15 17 23
1 4 7 8 12 16 20 22
3 6 10 13 18 19 21

A sanity check that the weights are indeed equal, also computing the exact weight using gold density:

(son <- unique(sapply(out, function(x) sum(4/3*pi*(x/2)^3*19.3))))

## [1] 256597.7

So each Auric’s son would get ~256.6kg of gold (worth ~$450K nowadays).

The Riddler: King Auric (June 19, 2020)

Maxim Nazarov

Question

Solution