sandp.rb

A Puzzle

Given

 1 < x < y

and

 x + y < 100

Mathematician S knows the sum x + y.

Mathematician P knows the product x * y.

 P: I can't determine x and y.
 S: I knew that.
 P: Now I can.
 S: So can I.

What are x and y?

Some observations

Copyright 2005 by Dale Brayden.

First, a couple basic observations:

 2 <= x <= 49 since x < y and x + y <= 99

 x and y cannot both be prime, since otherwise P would immediately know x and y

So lets form the set of possible products as all products for the valid x and y such that x and y are not both prime. We‘ll call that set p_poss_1.

      p_poss_1 = {}
      2.upto(49) do |x|
              (x+1).upto(99-x) do |y|
                      if not (x.prime? and y.prime?)
                              p_poss_1[x * y] ||= []
                              p_poss_1[x * y] << [x, y]
                      end
              end
      end

Also, the sum cannot be composable from 2 primes, since otherwise S could not know whether P could determine the answer. All even numbers can be written as 2 primes, therefore the sum cannot be even. And, the sum cannot be of the form 2 + p where p is prime. Let’s call the resulting set of possible sums s_poss_2.

      s_poss_2 = []
      4.upto(99) { |i| s_poss_2 << i unless i.even? or (i - 2).prime? }

Now it gets very tricky. How does P learn x and y by knowing that S knew that P didn’t originally know x and y? It could only be because P was able to partition the possible x*y = p into 2 sets : a singleton that, if it were the correct x and y, S would know that P didn’t know the answer, and other combinations such that S would not know that P didn’t know the answer. And that could only happen if exactly one of the factorizations sums to a member of s_poss_2. Let’s form the set of such cases and collect their sums into a set s_poss_3.

      s_poss_3 = []                # sum of the factors - this will be a subset of s_poss_2
      p_poss_1.each do |p, factors|
              s_poss = []         # possible sums for this set of factors
              factors.each { |xy| s_poss << xy if s_poss_2.include?(xy[0] + xy[1]) }
              if s_poss.length == 1
                      xy = s_poss[0]
                      s_poss_3 << (xy[0] + xy[1])
              end
      end

Not it gets really tricky. S has to examine each of the possible products that lead to the (known) sum, and exactly one of those products must be uniquely partitionable in the way described in the previous paragraph. The single such product that meets that criterion then leads to the solution.

      s_uniq_3 = Hash.new(0)
      s_poss_3.each {|s| s_uniq_3[s] += 1 }
      s_poss_3 = []                # reset so we can add just the one(s) that are unique
      s_uniq_3.each {|s, n| s_poss_3 << s if n == 1}

This step should (and does) yield a single possible sum : 17.

Finally, we need to identify the one remaining product that has only one S-possible solution.

      p_poss_4 = []
      s_poss_3.each do |s|
              2.upto(s / 2) do |x|
                      y = s - x
                      a = p_poss_1[x * y]
                      next if a.nil?
                      a = a.delete_if {|xy| not s_poss_2.include?(xy[0] + xy[1]) }
                      p_poss_4 << a[0] if a.length == 1
              end
      end

We have a solution only if there is a single result.

      if p_poss_4.length == 1
              f = p_poss_4[0]
              puts "x = #{f[0]}, y = #{f[1]}"
      else
              puts "No solution"
      end

You may have noticed that we used predicates even? and prime?. Here they are:

      class Numeric
              def even?; self.remainder(2) == 0; end
              def prime?
                      2.upto(self / 2) {|i| return nil if self.remainder(i) == 0 }
                      true
              end
      end

If we run the program we get :

 x = 4, y = 13