# Tony’s Oracle Tips

## August 11, 2008

### SQL Puzzle – 1 – Paul and Sam

Filed under: SQL Fun — tonyhasler @ 10:28 pm

I returned from vacation to be set a logic problem by a colleague.  He suggested that though it is possible to write a program in SQL to solve the problem it would, in fact, be quite tricky to do so. Well that was a challenge I couldn’t pass up!
As it turns out my solution is a sterling example of how otherwise complex problems can be significantly simplified by two highly underutilised features of SQL: factored subqueries and analytic functions.  The COUNT function is an aggregate function that can be used as an aggregate function with the appropriate use of additional syntax.

Anyway, if you want to have a go yourself here is the problem:

There are 2 integers, a and b, between 2 and 100, with a<=b.

Paul is only told their product (a*b), and Sam is only told their sum (a+b).

When Paul and Sam first meet each other, the following conversation is overheard.

Paul: I don’t know what the numbers are

Sam : I knew that. I don’t know what the numbers are either

Paul: I do now!

Sam : So do I!

So what are the numbers?

if you would like to see one solution see the next page

## 1 Comment »

1. As an aside here is the solution I came up with many years ago, before I knew about factored subqueries and analytic functions (or possibly even before they existed).

define minval=2
define maxval=99
set numwidth 6
set pages 0
set feedback off
set verify off
column a3 format a3
column a15 format a15
column num format 9999
prompt
prompt Solve the problem set by:
prompt
prompt There are 2 integers a and b between &&minval and &maxval, with a<=b.
Prompt Paul is only told their product (a*b), and Sam is only told their sum (a+b).
prompt
prompt When Paul and Sam first meet each other, the following conversation is overheard.
prompt
prompt Paul: I don’t know what the numbers are
prompt Sam : I knew that. I don’t know what the numbers are either
prompt Paul: I do now!
prompt Sam : So do I!
prompt
prompt So what are the numbers?
prompt
— nums = numbers &&min_val to &&maxval
— pairs = all possible pairs a, b from nums with a <= b
— sums = all possible sums formed by pairs
— products = all possible products formed by pairs
— poss_sums = all sums that cannot be formed uniquely by 2 numbers
— between &&minval and &&maxval (cc=1 in products)
— poss_prods= all products that can be formed uniquely by a pair matching the
— values in poss_sums

create table nums
as select rownum+&&minval-1 num from dual connect by level = a.num;

create or replace view sums as select a+b s,count(*) cc
from pairs
group by a+b;

create or replace view products as select a*b p,count(*) cc
from pairs
group by a*b;

prompt
prompt Paul: I don’t know what the numbers are
prompt Sam : I knew that. I don’t know what the numbers are either
prompt
prompt Paul’s first statement is more helpful than it first appears
prompt The pair of numbers cannot be uniquely determined by their product
prompt This includes not just 2 primes such as 7 and 11,
prompt but also pairs like 19 and 38, or 4 and 53, 77 and 17
prompt (assuming we are only looking at 2 digit numbers)
prompt
prompt Sam’s first statement is even more helpful.
prompt Sam knows that Paul can’t possibly know the numbers
prompt So whatever his sum is, it cannot
prompt be formed by a pair that uniquely determines their product
prompt For example : the sum cannot be 18, or 57 or 94 using the above examples
prompt
prompt generate poss_sums as
prompt the only sums that cannot possibly be made by distinct product pairs
prompt There are surprisingly few

create or replace view poss_sums as
select s from sums where cc > 1
minus
select pairs.a+pairs.b s from pairs where pairs.a*pairs.b in
(select p from products where cc=1);

prompt
prompt From Sam’s first statement the sum must be one of
prompt
select s from poss_sums
order by s;

prompt
prompt Paul’s last statement:
prompt Paul: I do now!
prompt
prompt So Paul knows that Sam knew that he did not know the numbers and so
prompt must have a sum matching the above criterion
prompt This enables him to deduce the pairs.
prompt So Paul must have a product that decomposes to one of the sums
prompt in the above list
prompt in exactly one way (2 or more would not give him a solution and 0
prompt would violate Sam’s previous statement)
prompt find all products that can have exactly one sum matching the list of sums above
prompt

create or replace view poss_prods as
select products.p,max(poss_sums.s) s
from products,pairs,poss_sums
where products.cc > 1
and pairs.a*pairs.b = products.p
and pairs.a+pairs.b = poss_sums.s
group by products.p
having count(poss_sums.s) = 1;

select ‘product is ‘, p, ‘sum is’, s from poss_prods
order by p,s;

— now find the sum that has only one possible product fitting that criterion

prompt
prompt Sam’s last statement:
prompt Sam : So do I!
prompt
prompt So we need to find a sum that only occurs once in the above list
prompt Otherwise Sam could still not deduce the pair.
prompt and as we know both the product and the sum we can find the pair
prompt

col plan_plus_exp for a120
set lines 160

select ‘In the range’ a15,min(num) num,’to’ a3,max(num) num from nums;

set autotrace on explain

select ‘The numbers are’ a15, a num,’and’ a3, b num
from pairs,
( select max(p) p,s from poss_prods group by s having count(*) = 1) pp
where pairs.a*pairs.b = pp.p
and pairs.a+pairs.b= pp.s
order by a,b;

set autotrace off

drop view poss_prods;
drop view poss_sums;

drop view products;
drop view sums;
drop view pairs;

prompt
prompt or to be perverse, and use only in-line views
prompt

— using the with clause is much too slow in 10.1
— with nums as (select rownum+&&minval-1 num from sys.tab\$
— where rownum < &&maxval+1-&&minval)
select ‘In the range’ a15,min(num) num,’to’ a3,max(num) num from nums;

set timing on
set autotrace on explain

— with nums as (select rownum+&&minval-1 num from sys.tab\$
— where rownum = a.num
) pairs,
( select max(p) p,s
from ( select products.p,max(poss_sums.s) s
from ( select a.num*b.num p,count(*) cc
from nums a, nums b
where b.num>= a.num
group by a.num*b.num
having count(*) > 1
) products,
( select a.num a, b.num b
from nums a, nums b
where b.num >= a.num
) prs,
(
select s
from ( select a.num+b.num s
from nums a, nums b
where b.num >= a.num
group by a.num+b.num
having count(*) > 1
) sums
minus
select prs2.a+prs2.b s
from ( select a.num a, b.num b
from nums a, nums b
where b.num >= a.num
) prs2
where prs2.a*prs2.b in
( select a.num*b.num p
from nums a, nums b
where b.num >= a.num
group by a.num*b.num
having count(*) = 1
)
) poss_sums
where prs.a*prs.b = products.p
and prs.a+prs.b = poss_sums.s
group by products.p
having count(poss_sums.s) = 1
)
group by s having count(*) = 1
) pp
where pairs.a*pairs.b = pp.p
and pairs.a+pairs.b= pp.s
order by a,b;

set autotrace off
set timing off

drop table nums;

Comment by Mike Brandt — September 24, 2008 @ 10:12 am

Create a free website or blog at WordPress.com.