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. 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 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: