The Riddler: A Particularly Prismatic Puzzle

19 Dec 2019

Beyond its lovely alliteration, the Riddler Classic puzzle from last Friday was particularly fun. Here’s the problem:

From Steve Abney comes a particularly prismatic puzzle:

Suppose I have a rectangle whose side lengths are each a whole number, and whose area (in square units) is the same as its perimeter (in units of length). What are the possible dimensions for this rectangle?

Alas, that’s not the riddle — that’s just the appetizer. The rectangle could be 4 by 4 or 3 by 6. You can check both of these: 4 · 4 = 16 and 4 + 4 + 4 + 4 = 16, while 3 · 6 = 18 and 3 + 6 + 3 + 6 = 18. These are the only two whole number dimensions the rectangle could have. (One way to see this is to call the rectangle’s length a and its width b. You’re looking for whole number solutions to the equation ab = 2a + 2b.)

On to the main course! Instead of rectangles, let’s give rectangular prisms a try. What whole number dimensions can rectangular prisms have so that their volume (in cubic units) is the same as their surface area (in square units)?

To get you started, Steve notes that 6 by 6 by 6 is one such solution. How many others can you find?

We’re looking for positive integer solutions to $abc = 2(ab) + 2(bc) + 2(ac)$. The brute force approach would be to check all possible combinations of three digits from 1-100 for solutions, which I implemented in R as follows:

library(arrangements)
prismatic_puzzle <- function(row) {
 if (row[1]*row[2]*row[3] == 2*row[1]*row[2] + 2*row[1]*row[3] + 2*row[2]*row[3]) {
   return(row)
 }
}

library(plyr)
compact(apply(combinations(1:100, 3, replace=TRUE), 1, FUN = prismatic_puzzle))

The function prismatic_puzzle takes in as an argument a “row”, a vector of three numbers and checks to see if the three elements of the vector multiplied are equivalent to two times the product of the first two plus two times the product of the first and third, plus two times the product of the second and third. Using apply and combinations, one can feed in every possible combination of three digit numbers from 1 to 100 into the function and return only the solutions.

My friend Ricky Martinez wrote an equivalent script in Python:

from itertools import combinations_with_replacement as cwr
for a, b, c in cwr(range(1,101), 3):
     if a*b*c == 2*a*b + 2*b*c + 2*a*c:
         print(f'a={a}, b={b}, c={c}')

Either of these return 10 solutions:

  1. (3, 7, 42)
  2. (3, 8, 24)
  3. (3, 9, 18)
  4. (3, 10, 15)
  5. (3, 12, 12)
  6. (4, 5, 20)
  7. (4, 6, 12)
  8. (4, 8, 8)
  9. (5, 5, 10)
  10. (6, 6, 6)

There are just two issues. First, this can be really slow—there are 171,700 combinations for numbers 1 through 100, which takes about half a second in R, but 20,958,500 for numbers 1 through 500, and takes about a minute to run. As you can imagine this continues to blow up. The prismatic_puzzle is really slow even though it’s applied over the rows of the array. Second, it can’t be certain that it captured all the solutions!

Thankfully, Laurent Lessard provides a way to simplify the problem significantly. Assume that $a \leq b \leq c$. This implies that $ab \geq ac \geq bc$ and so $abc = 2(ab) + 2(bc) + 2(ac) \leq 6ab$, and so $c \leq 6$. We need only to consider the triples with this characteristic… 28,820 of them. Of course, ex-post we also know that the maximum number is 42, and so we can reduce the number of triples to 4,808. Though inelegant, we can modify the R code above to:

compact(apply(combinations(1:42, 3, replace=TRUE)[combinations(1:42, 3, replace=TRUE)[,1] <= 6,], 1, FUN = prismatic_puzzle))

And “greatly” improve our computation speed to 0.05071902 seconds. Neat!

As for the exhaustive search, it looks like it’s impossible, since allowing $a \to \infty \implies bc = 2b + 2c$…

comments powered by Disqus