A friend of mine (Hillel Kahana) shared with me a riddle that his 10-year old son brought from a math workshop. At first, the riddle sounded easy…
You’ve got the first 6 digits 1,2,3,4,5 and 6.
You have to partition the digits into 3 numbers
xis a 3-digit number
yis a 2-digit number
zis a single digit number
Such that the multiplication
x*y*z is maximal.
Each digit must be used only once.
(* 123 45 6)
But, obviously we can do better.
Sounds easy. Right?
So give it a try.
Before reading the rest of this article, take a pencil and a sheet of paper and try to find the solution.
Have fun with the digits!
Elegant or brute force
Maybe, you are a math genius and you are able to find the elegant solution to this riddle and to prove mathematically that your solution is correct.
It’s not my case, so we are going to go with a brute force algorithm with a couple of lines of
We are going to go over the
6! permutations and take the one that leads to the greatest number.
But, wait a minute
How are we going to generate those 720 permutations?
Clojure.math.combinatorics to the rescue
There is a
clojure library named
clojure.math.combinatorics (by Mark Engelberg) that has a
permutations function (and a lot of other useful functions: check it here).
For instance, let’s generate all the
3! permutations of
[1 2 3]:
(ns my.combinatorics (:require [clojure.math.combinatorics :refer [permutations]])) (permutations [1 2 3])
permutations, it’s really easy to find the solution to the riddle:
(apply max-key (fn [[a b c d e f]] (* (+ (* 100 a) (* 10 b) c) (+ (* 10 d) e) f)) (permutations (range 1 7)))
max-key returns the value for which the function is greatest.
If you want to play with more digits, you’d find it more convenient to open the KLIPSE repl, because in this article the code is evaluated as you type…
PS: Do you have a more elegant solution to this riddle? Let us know in the comments below…