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

### Like this:

Like Loading...

*Related*

Congratulations, Tony. I hope I am the first of many to add comments to your blog.

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

pause Ready?

— 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

pause Ready?

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

pause Ready?

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

pause Ready?

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

pause Ready?

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 |