I found this puzzle recently. I should say I rediscovered it, as I knew it from before. I wanted to solve it in Clojure – here’s one possible solution, with comments on the thought process involved in solving it (in the comments before the actual code).
(ns com.icyrock.clojure.prb.xynum) ; http://puzzling.stackexchange.com/questions/251/i-dont-know-the-two-numbers-but-now-i-do ; http://en.wikipedia.org/wiki/Impossible_Puzzle ; http://people.sc.fsu.edu/~jburkardt/fun/puzzles/impossible_solution.html ; Two numbers, 1 < x < y, x + y < n (n = 100 in the linked question) ; p = x * y ; s = x + y ; p: I cannot determine the two numbers. ; => p not unique: p = x1 * y1 = x2 * y2 = ... ; Let's call this an ambiguous product ; s: I knew that. ; => s can be created from one or multiple pairs: s = x1 + y1 = x2 + y2 = ... ; Those pairs form these products: ; p1 = x1 * y1 ; p2 = x2 * y2 ; ... ; Each of these products can be created from multiple pairs (i.e. is ambiguous): ; p1 = x11 * y11 = x12 * y12 = ... ; p2 = x21 * y21 = x12 * y22 = ... ; ... ; Let's call this product-ambiguous sum ; p: Now I can determine them. ; => p = x1 * y1 = x2 * y2 = ... ; Only one of (xk, yk) forms a product-ambiguous sum ; Let's call this unambiguous product ; s: So can I. ; => s = x1 + y1 = x2 + y2 = ... ; Only one of all the possible products: ; p1 = x1 * y1 ; p2 = x2 * y2 ; ... ; is an unambiguous product ; Let's call this unambiguous sum (defn xynum [n] (let [pairs (for [y (range 2 n) x (range 2 y) :when (< (+ x y) n)] [x y]) sum-map (group-by (partial apply +) pairs) prod-map (group-by (partial apply *) pairs) ; Pair forms a product. That product can be formed from at least some other pair. is-ambiguous-product (fn [pair] (> (count (prod-map (apply * pair))) 1)) ; Pair forms a sum. That sum can be formed from other pairs. Those pairs form some products. All those products are ambiguous. is-product-ambiguous-sum (fn [pair] (every? true? (map is-ambiguous-product (sum-map (apply + pair))))) ; Pair forms a product. That product can be formed from other pairs. Only one of those pairs forms a product-ambiguous sum. is-unambiguous-product (fn [pair] (= 1 (count (filter true? (map is-product-ambiguous-sum (prod-map (apply * pair))))))) ; Pair forms a sum. That sum can be formed from other pairs. Only one of those pairs forms an unambiguous product. is-unambiguous-sum (fn [pair] (= 1 (count (filter true? (map is-unambiguous-product (sum-map (apply + pair))))))) is-pair-a-candidate (fn [pair] (and (is-ambiguous-product pair) (is-product-ambiguous-sum pair) (is-unambiguous-product pair) (is-unambiguous-sum pair))) candidates (filter is-pair-a-candidate pairs)] (println "Pair count:" (count pairs)) (println "Sum map count:" (count sum-map)) (println "Product map count:" (count prod-map)) (println "Candidates count:" (count candidates)) (println "Candidates: " candidates))) (defn -main [] (xynum 100)) (-main)
Note also the Wikipedia entry, which contains solutions in other languages. I particularly liked the Scala version, notably for its conciseness and readability.