Products equaling sums

From The Riddler, June 25, 2021, a puzzle from Matt Enlow (which was originally published in Math Horizons, although I can’t find the original):

A bag contains 100 marbles, and each marble is one of three different colors. If you were to draw three marbles at random, the probability that you would get one of each color is exactly 20 percent.

How many marbles of each color are in the bag?

It doesn’t seem like there’s enough information, but there is. I recommend not trying to solve this puzzle in your head while navigating the day care parking lot, though.

Let’s say the numbers of the three colors are x, y and z. Then the number of sets of three marbles which contain one of each color is just xyz. And the number of total sets of three marbles is {100 \choose 3}. So we need to find positive integers x, y, z such that x + y + z = 100 and 5xyz = {100 \choose 3}.

It’ll help to find the prime factorization of {100 \choose 3}, so we expand it:

{100 \choose 3} = {100 \times 99 \times 98 \over 3 \times 2 \times 1} = {2^2 \times 5^2 \times 3^2 \times 11 \times 2 \times 7^2 \over 3 \times 2} = 2^2 \times 3 \times 5^2 \times 7^2 \times 11.

Dividing out the 5, we need xyz = 2^2 \times 3 \times 5 \times 7^2 \times 11.. The three big factors – the two 7s and the 11 – look like they’ll be worrisome. So let’s spread them out: let x and y both be multiples of 7, and let z be a multiple of 11. To get them to add up to 100, we need to find a multiple of 7 and a multiple of 11 that add up to 100; it’s easy to find 44 and 56. So z = 44.

That leaves xy = 3 \times 5 \times 7^2, so x and y must be 21 and 35.

Alternately, we can write some code to solve it, but what fun is that?

n = 100

target = (n * (n-1) * (n-2))/6
for x in range(1, n+1):
    for y in range(x, int((n-x)/2)+1):
        z = n-x-y;
        if target == 5*x*y*z:
            print(x, y, z)

which prints out

21 35 44

as expected.

But now that we have some code, is there something special about 100? Let’s iterate over the first 1000 integers:

for n in range(1, 1000):
    target = (n * (n-1) * (n-2))/6
    for x in range(1, n+1):
        for y in range(x, int((n-x)/2)+1):
            z = n-x-y;
            if target == 5*x*y*z:
                print(n, x, y, z)

returns

6 1 1 4
10 2 2 6
22 4 7 11
26 5 8 13
27 5 9 13
35 7 11 17
36 7 12 17
40 8 13 19
46 11 12 23
56 11 21 24
65 13 24 28
76 19 20 37
100 21 35 44
126 31 35 60
330 82 94 154
345 86 98 161
352 78 120 154
352 91 96 165
406 101 116 189
436 109 124 203
497 124 142 231
512 128 146 238
737 161 268 308

The sequence 6, 10, 22, 26, 27, 35… isn’t in the OEIS as of this writing, although some other Riddler puzzles have made it; it may be there later. These are all numbers where not just n has a lot of factors, but also n-1 and n-2 – for example 345 = 3 x 5 x 23, 344 = 2 x 2 x 2 x 43, 343 = 7 x 7 x 7. Thus {n \choose 3}/5 will have many factors, and many ways to be written as a product of three integers, making it more likely that one of those will have the right sum.

I had been expecting an algebraically cleaner solution, because this reminded me of another puzzle: a bag has r red and b blue balls in it. Find r, b such that the probability that two balls picked at random have different colors is exactly one-half. In this case similar code returns the solution

4 1 3
9 3 6
16 6 10
25 10 15
36 15 21
49 21 28
64 28 36
81 36 45
100 45 55

from which we can guess that the solutions are r = (n^2-n)/2, b = (n^2+n)/2.

Balancing the centrifuge – a Riddler puzzle

From the riddler:

Quoc’s lab has a microcentrifuge, a piece of equipment that can separate components of a liquid by spinning around very rapidly. Liquid samples are pipetted into small tubes, which are then placed in one of the microcentrifuge’s 12 slots evenly spaced in a circle.

For the microcentrifuge to work properly, each tube must hold the same amount of liquid. Also, importantly, the center of mass of the samples must be at the very center of the circle — otherwise, the microcentrifuge will not be balanced and may break.

Quoc notices that there is no way to place exactly one tube in the microcentrifuge so that it will be balanced, but he can place two tubes (e.g., in slots 1 and 7).

Now Quoc needs to spin exactly seven samples. In which slots (numbered 1 through 12, as in the diagram above) should he place them so that the centrifuge will be balanced? Extra credit: Assuming the 12 slots are distinct, how many different balanced arrangements of seven samples are there?

https://fivethirtyeight.com/features/can-you-break-a-very-expensive-centrifuge/

I’ve seen this one before, but I’ll take it on as a programming challenge.

I’ll say that hole k is at coordinates (\sin 2\pi k/12, \cos 2\pi k/12). This is nonstandard, but the result looks like a clock, so it’s easier to visualize:

The centrifuge layout.

Now, there are {12 \choose 7} = 792 ways that we could pick 7 out of the 12 holes. To generate a list of these I can use the following R function:

combinations = function(n, k){
  if (k == 0 & n == 0){return(list())} else {
    if (k == 0){return(list(c()))} else {
      if (n == k){return(list(1:n))} else {
        without_n = combinations(n-1, k)
        with_n = lapply(combinations(n-1, k-1), function(x){c(x, n)})
        return(c(without_n, with_n))
      }
    }
  }
}

To generate the subsets of [n] of size k, I just take:

  • the subsets that don’t contain n (which are therefore subsets of [n-1] of size k), and
  • the subsets that do contain n (which are therefore subsets of [n-1] of size k-1, with n adjoined)
    (I learned this a good two decades ago, from section 3.6 of Herb Wilf’s notes East Side, West Side.)

Then iterate over the subsets to find their centers of mass:

our_comb = combinations(12, 7)
com_x = rep(NA, length(our_comb))
com_y = rep(NA, length(our_comb))
for (i in 1:length(our_comb)){
  com_x[i] = mean(x[our_comb[[i]]])
  com_y[i] = mean(y[our_comb[[i]]])
}

So our_comb runs through the combinations, and com_x and com_y are the x- and y-coordinates of the center of mass. Plotting the centers of mass gives we get an attractive symmetric pattern. Here I’ve plotted transparent points, so the darker points are points that arise from more distinct combinations. The outermost points represent the most imbalanced centrifuges – for example the one closest to the top represents loading slots 9, 10, 11, 12, 1, 2, and 3. The main question is: how many points are on top of each other at the very center.

Centers of mass of all subsets of 7 of the 12 centrifuge positions.

I can extract those subsets from the matrix our_comb and build them into a matrix for looking at. There’s a small problem in that we used floating-point arithmetic, so the coordinates don’t come out exactly at zero, but it’s enough to ake the ones that are “close enough”:

epsilon = 10^(-6)
balanced_indices = which(abs(com_x) < epsilon & abs(com_y) < epsilon)
balanced_combs =  t(matrix(unlist(our_comb[balanced_indices]), nrow = k))

and the matrix balanced_combs, which has one row for each combination that balances the centrifuge, is

      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
 [1,]    1    2    3    6    7    9   10
 [2,]    1    2    4    5    8    9   10
 [3,]    1    2    5    6    7   10   11
 [4,]    2    3    4    7    8   10   11
 [5,]    2    3    5    6    9   10   11
 [6,]    1    2    5    6    8    9   12
 [7,]    1    3    4    7    8    9   12
 [8,]    1    4    5    6    9   10   12
 [9,]    1    4    5    7    8   11   12
[10,]    2    3    6    7    8   11   12
[11,]    3    4    5    8    9   11   12
[12,]    3    4    6    7   10   11   12

(The order here is lexicographic order, but you have to read the rows backwards.)

If you can make sense of this pile of numbers without making some pictures, good for you! But I am human, though a mathematician, so let’s plot. Here big black dots represent the loaded spots, and small blue dots represent the non-loaded spots.

(And yes, it’s in base R graphics. It’s been a while since I’ve used those – at my day job it’s all ggplot all the time.)


par(mfrow = c(4, 3), mar = c(1, 1, 1, 1))
for (i in 1:nrow(balanced_combs)){
  full = balanced_combs[i,]
  empty = setdiff(1:n, balanced_combs[i,])
  plot(x[full], y[full], pch = 19,cex = 2,
       asp = 1, axes = FALSE, xlab = '', ylab = '', 
       xlim = c(-1.25, 1.25), ylim = c(-1.25, 1.25))
  points(x[empty], y[empty], pch = 19, cex = 1, col = 'lightblue')
}

So there are 12 ways to load the centrifuge… but we can clearly see that all of them are really just rotations of a single pattern. To me the visually most convenient representative of that pattern is the third one in the third row, which has loadings at 12, 1, 4, 5, 7, 8, and 11.

We can play a little game of connect-the-dots to see why this pattern is balanced. Connect 12, 4, and 8 to form an equilateral triangle. Connect 1 and 7; connect 5 and 11. Like this:

12-hole centrifuge loaded with 7; symmetric subsets specified

Each of those three subsets has its center of mass at the center of the circle, so the whole arrangement does too.

That decomposition turns out to be the key to the general problem of which centrifuge sizes can be loaded with which number of tubes and remain balanced. Stay tuned.