Introduction

This is a response to the Riddler Classic of June 19, 2020.

The puzzle is to divide gold spheres into equal groups by weight. There is one of each unit of diameter: 1 centimeter, 2 centimeters, 3 centimeters, etc. What is the minimum number of spheres that are needed to divide these spehres into two, three, four, five, etc. groups?

Calculating weights

Since we are told that the spheres are solid gold, we know they have equal density. Taking the common density as unit density, and taking the radius as units of 1, 2, 3, etc. rather than as centimeters, the weights are multiples of 13, 23, 33, etc.

Looking in my trusty math textbook, I see that \(\sum_{k=1}^{n} k^3 = \frac{1}{4} n^2 (n+1)^2\)

Starting with partitioning into three groups:

Looking at the curve as you increase the number of spheres, the largest sphere starts off as always larger than one-third of the total weight, but eventually there is some weight where it is feasible for this largest sphere to be in a group. This can be found by using the sum above and setting one-third of it greater than n3.

# calculate the total weight of n spheres
sum_of_weight <- c()
for(n in 1:100){
  sum_of_weight[n] = (n^2 * (n+1)^2)/4
}

plot(1:15, sum_of_weight[1:15]/3, type="b", cex=0.5, xlab = "size of sphere", ylab="one-third of the total weight")  # target weight of each group
lines(1:15, (1:15)^3, col="red")  # weight of largetst sphere

As soon as it meets the goal line, it ducks under it. Sl we need to find a combination of spheres that “pack in” to be exactly equal to the curve.

Let’s write some code

I’m sure there’s a way of calculating the exact values using simultaneous inequalities or something, but since I don’t have that much time this weekend, I’ll write a short code rather than work the math. Shout out to this guy who posted a very efficient algorithm for this type of search on youtube.

# calculate the total weight of n spheres
sum_of_weight <- c()
for(n in 1:100){
  sum_of_weight[n] = (n^2 * (n+1)^2)/4
}

# determine if the remaining spheres can be split evenly by iter_child children
canPartition <- function(k, assigned, iter_child, weight_so_far, goal){
  # weight_so_far is the weight assigned to iter_child so far.
  #   "assgined" keeps track of whether the sphere of each size is already assigned
  #   k tells the recursive search to only begin from sphere of unit radius k (k/2 cm), and count backwards
  if(iter_child == 1){
    # all other children are complete and reached goal
    return(T)
  } else if(weight_so_far == goal){
    # iter_child is at goal, move on to next iter_child
    return(canPartition(length(assigned), assigned, iter_child-1, 0, goal))
  } else {
    while(k > 0){ # count backwards to the smallest sphere
      if(!assigned[k] & (weight_so_far+k^3)<= goal){
        # try to assign sphere k to iter_child
        assigned[k] <- T
        if(canPartition(k-1, assigned, iter_child, weight_so_far+k^3, goal)){
          return(T)
        } else {
          # didn't work, unassign this sphere
          assigned[k] <- F
        }
      }
      k <- k - 1
    }
    return(F) # failed to find an equal weight
  }
}

# run this function to assign n spheres among the childen equally by weight
partition <- function(n, children = 3, sum_of_weight){
  if(sum_of_weight %% children != 0){
    # total is not divisible by number of children - can't divide equaly
    return(F)
  } else {
    # assign the largest to the first iter_child, and continue from there
    assigned <- rep(F, times=n)
    assigned[n] <- T
    return(canPartition(n-1, assigned, children, n^3, sum_of_weight/children))
  }
}

Ok, now let’s get the answers!

for (children in 2:6){ # keep increasing the number of spheres until you get the minium
  found <- F
  n <- 1
  while(!found & n < 30){ 
    n <- n+1
    found <- partition(n, children, sum_of_weight[n])
  }
  if (found)
    print(paste(n,"spheres can be assigned to", children, "children equally by weight"))
  else
    print(paste("it's probably not posisble to assign spheres to", children, "children equally by weight"))
}
## [1] "12 spheres can be assigned to 2 children equally by weight"
## [1] "23 spheres can be assigned to 3 children equally by weight"
## [1] "24 spheres can be assigned to 4 children equally by weight"
## [1] "24 spheres can be assigned to 5 children equally by weight"
## [1] "it's probably not posisble to assign spheres to 6 children equally by weight"

Answers to previous Riddler puzzles