September 28, 2015 at 9:23 am
Warning:
This should be seen as a puzzle and not as a solution to a problem.
I use this type of puzzle to demonstrate (especially to procedural oriented people) what can be done with SQL.
So please enjoy the puzzle, I am looking forward to contributions for this puzzle.
Only spend time on it if you enjoy this type of puzzle.
Martin Gardner writes in 1979 in his column "Mathematical Games"
“This beautiful problem, which I call “impossible”
because it seems to lack sufficient information for a solution,
began making the rounds of mathematics meetings a year or so ago. I do not know its origin.”
See the paper:
The beautiful problem:
The teacher says to Peter and Sam: I have secretly chosen two integers x and y with 2 <= x < y and x + y <= 100. I have told the sum s = x + y to Sam (but not to Peter) and the product p = x y to Peter (but not to Sam).
1. Peter says: I don't know the numbers x and y.
2. Sam replies: I already knew you didn't know.
3. Peter says: Oh, then I do know the numbers x and y.
4. Sam says: Oh, then I also know them.
Determine x and y!
I use this type of problems to demonstrate that SQL-server can solve 'problems'.
This problem specifically suetable to show set based thinking. (NO RBAR).
There are more ways to solve this puzzle. And I have found a solution, but very often there are better solutions (shorter, more elegant, more efficient etc).
Not to spoil the puzzle I have not included my solution yet. I'll post my solution later this week. I am hoping for different scripts which solve this problem.
Ben
September 28, 2015 at 2:44 pm
Well, I poked around this problem for a bit, and came up with the following. It has all sorts of warts (I'm not generating my numbers the most efficient way and my naming conventions are all silly, just to pick a couple), and I'm quite certain it's terribly inefficient (what happens when you just solve one piece at a time; I've ended up with something a bit Frankenstein's monster-ish :-)) , but I think the logic's right.
After writing it I read the paper for comparison, and it reproduces all the same results as the paper (m=1,M=11 is impossible, unless x and y are allowed to be equal; m=2,M<65, as in Gardner's original with M=20, is also impossible; m=2, 65<=M<=1684 yields the one unique solution; m=2, M>1684 adds the second solution).
Maybe tonight I'll move on to beautifying it and working on performance 🙂
A nice little puzzle, though!
--I've generated TOP 2000 to allow testing of M>1684
WITH Numbers(Num) AS
(
select TOP 2000 row_number() OVER (ORDER BY (SELECT NULL))
FROM sys.all_columns ac1
CROSS JOIN sys.all_columns ac2
)
SELECT Num1.Num AS FirstNum, Num2.Num AS SecondNum, Num1.Num*Num2.Num AS NumProduct, Num1.Num+Num2.Num AS NumSum
INTO #NumberCombinationBase
FROM Numbers Num1 INNER JOIN Numbers Num2
ON Num1.Num<Num2.Num AND Num1.Num+Num2.Num<=100
WHERE Num1.Num>=2;
--Peter doesn't know the combination yet, which means his product can be achieved by multiple eligible combinations.
--This removes 605 pairs of numbers, leaving us with 1747 potential number combinations for Peter.
WITH PeterPossibleProducts AS
(
SELECT NumProduct FROM #NumberCombinationBase GROUP BY NumProduct HAVING COUNT(*)>1
)
SELECT NCB.* INTO #PeterPossibilities FROM #NumberCombinationBase NCB INNER JOIN PeterPossibleProducts PPP
ON NCB.NumProduct=PPP.NumProduct;
--Sam already knew that Peter couldn't know the combination yet, so his sum must only exist for combinations of numbers
--that share a product with another combination, i.e., his sum most ONLY exist in Peter's possibilities.
--The RestrictedPossibilities CTE limits our results to those combinations.
--Once Peter knows that RestrictedPossibilities is his set to work with, he knows x and y.
--This means that his product only occurs once on that list. There are 86 such products, captured by ProductsAllowingPeterToKnow
--Once Sam knows that the result is among the 86 ProductsAllowingPeterToKnow, he also knows x and y, so his sum must only
--occur once in the combinations in RestrictedPossibilities that yield the 86 ProductsAllowingPeterToKnow.
--That gives us one result, 4 and 13.
WITH CombinationsWithUniqueProducts AS
(
SELECT * FROM #NumberCombinationBase
EXCEPT
SELECT * FROM #PeterPossibilities
)
SELECT * INTO #PeterImpossibilities
FROM CombinationsWithUniqueProducts;
WITH RestrictedPossibilities AS
(
SELECT * FROM #PeterPossibilities PPoss WHERE NOT EXISTS (SELECT NULL FROM #PeterImpossibilities PImp WHERE PImp.NumSum=PPoss.NumSum)
),
ProductsAllowingPeterToKnow AS
(
SELECT NumProduct FROM RestrictedPossibilities GROUP BY NumProduct HAVING COUNT(*)=1
),
SumsAllowingSamToKnow AS
(
SELECT RP.NumSum FROM RestrictedPossibilities RP INNER JOIN ProductsAllowingPeterToKnow PAPTK
ON RP.NumProduct=PAPTK.NumProduct
GROUP BY RP.NumSum HAVING COUNT(*)=1
)
SELECT RP.* FROM SumsAllowingSamToKnow SASTK
INNER JOIN RestrictedPossibilities RP
ON SASTK.NumSum=RP.NumSum
INNER JOIN ProductsAllowingPeterToKnow PAPTK
ON RP.NumProduct=PAPTK.NumPRoduct;
DROP TABLE #NumberCombinationBase,#PeterImpossibilities,#PeterPossibilities;
Cheers!
EDIT: Fixed a couple typos.
September 28, 2015 at 5:35 pm
And another answer comes out as x=4 and y=13.
Also, not great for performance, but shows a different technique.
/* Puzzle from SSC
http://www.sqlservercentral.com/Forums/Topic1723602-391-1.aspx
The beautiful problem:
The teacher says to Peter and Sam: I have secretly chosen two integers x and y with 2 <= x < y and x + y <= 100. I have told the sum s = x + y to Sam (but not to Peter) and the product p = x y to Peter (but not to Sam).
1. Peter says: I don't know the numbers x and y.
2. Sam replies: I already knew you didn't know.
3. Peter says: Oh, then I do know the numbers x and y.
4. Sam says: Oh, then I also know them.
Determine x and y!
*/
/* in-line tally table for the two sets of numbers X and Y */
with n1(x) as (select 1 from (values(1),(1),(1),(1),(1),(1),(1),(1),(1),(1)) a(a))
, tally(n) as (select row_number() over(order by @@spid) from n1 a, n1 b)
/* generate all possible X and Y combinations */
, domain(x,y,s,p) as (
select t1.n, t2.n, t1.n + t2.n, t1.n * t2.n
from tally t1
cross join tally t2
where 2<=t1.n
and t1.n<t2.n
and t1.n+t2.n<=100
)
/* Peter initially doesn't know X and Y, so P must be non-unique
So, let's count the Products */
, CountProducts (s,pCount) as (
select s, count(*) over(partition by p) as pCount
from domain
)
/* Sam's SUM must be one of the remaining ones after we remove all the unique products */
, PossibleSums(x,y,s,p,pCount) as (
select x, y, s, p, count(*) over(partition by p) as pCount
from domain
where s not in (select s from CountProducts where pCount=1)
)
/* Peter's product must now be unique within Sam's list for Peter to know the answer */
, PossibleProducts as (
select x,y,s,p,count(*) over(partition by s) as sCount
from PossibleSums
where pCount=1
)
/* Sam's SUM must now be unique within the set of Peter's unique products */
select 'Answer', x,y,s,p
from PossibleProducts
where sCount = 1;
MM
select geometry::STGeomFromWKB(0x0106000000020000000103000000010000000B0000001000000000000840000000000000003DD8CCCCCCCCCC0840000000000000003DD8CCCCCCCCCC08408014AE47E17AFC3F040000000000104000CDCCCCCCCCEC3F9C999999999913408014AE47E17AFC3F9C99999999991340000000000000003D0000000000001440000000000000003D000000000000144000000000000000400400000000001040000000000000F03F100000000000084000000000000000401000000000000840000000000000003D0103000000010000000B000000000000000000143D000000000000003D009E99999999B93F000000000000003D009E99999999B93F8014AE47E17AFC3F400000000000F03F00CDCCCCCCCCEC3FA06666666666FE3F8014AE47E17AFC3FA06666666666FE3F000000000000003D1800000000000040000000000000003D18000000000000400000000000000040400000000000F03F000000000000F03F000000000000143D0000000000000040000000000000143D000000000000003D, 0);September 29, 2015 at 2:30 am
First of all thanks Jacob and Mister Magoo, for your time and attention.
The solution method for both and mine (see below) are the same, but I allready learned something from the differences in syntax.
(On line I have seen different solutions. Starting of with reasoning which primes and or not primes should be in the solution.).
For other readers, the used recipe:
1. Start with a set of all solutions.
2. Collect all the s (sum) where there is a product which only appears once.
Remove all solutions with this s (sum)
3. From the remainder choose all solutions where the product appears once.
4. From the remainder choose all solutions where the sum appears once.
The solution I came up with:
;
WITH
L0 AS(SELECT 0 AS c UNION ALL SELECT 0 UNION ALL SELECT 0 UNION ALL SELECT 0) -- 4 rows
,L1 AS(select 0 as n from L0 A, L0 B, L0 C, L0 D) -- 4 ^4 = 256 rows
-- ,L1x AS(select 0 as n from L1 A, L1 B, L1 C, L1 D) -- NOT USED -- (4 ^ 4) ^4 = 4 Giga
,L2 AS(Select row_number() OVER(PARTITION BY n order by n ) as n from L1) -- Add row_numbers
,L3 as (select x.n x, y.n y, x.n+y.n as s, x.n*y.n as p from L2 x cross join L2 y )
,L4 as (select * ,COUNT(*) OVER(PARTITION BY p ) count_p from L3 where x>1 and x<y and x+y<=100)
,R2 as (select * ,COUNT(*) OVER(PARTITION BY p ) count_p2 from L4 where s not in (select distinct s from L4 where count_p = 1))
,R3 as (select * ,COUNT(*) OVER(PARTITION BY s ) count_s from R2 where count_p2 = 1) -- Result from Rule3
SELECT * FROM R3 where count_s = 1 -- Result after Rule4
-- L0/L1/L2/L3/L4 set up the problem. x, y, s, p and count_p, which counts the number of same p (products).
-- R2
-- Implements Line -- 2. Sam replies: I already knew you didn't know.
-- Collect all values of s which can result in a single solution of P.
-- Remove all 'solutions' which have such an s value.
-- R3.
-- Implements Line -- 3. Peter says: Oh, then I do know the numbers x and y.
-- Get all the p values which only have a single solution. (count_p2 = 1)
-- R4.
-- Implements Line -- -- 4. Sam says: Oh, then I also know them.
-- Get all the s values which only have a single solution. (count_s = 1)
The Lines L0/L1/L2/L3/L4 can be shrinked to 3 lines,by using sys.columns, but for some reason I do not find that elegant and prefere to use the above method. The method used by mister.magoo, based on powers of 10 is probably a short, elegant and very flexible solution. (My above solution is based on the power of 2, which is a bit more 'nerdy' ;-))
;
WITH
L0 as (select row_number() OVER (ORDER BY (SELECT NULL)) as x FROM sys.columns)
,L1 as (select x.x x, y.x y, x.x+y.x as s, x.x*y.x as p from L0 x cross join L0 y)
,L2 as (select * ,COUNT(*) OVER(PARTITION BY p ) count_p from L1 where x>1 and x<y and x+y<=100)
,R0 as (select * ,COUNT(*) OVER(PARTITION BY p ) count_p2 from L2 where s not in (select distinct s from L2 where count_p = 1))
,R3 as (select * ,COUNT(*) OVER(PARTITION BY s ) count_s from R0 where count_p2 = 1) -- Result from Rule3
SELECT * FROM R3 where count_s = 1
Thanks for you contributions,
Any solutions based on another 'principle' ?
Ben
October 5, 2015 at 8:48 am
Hi Ben
I don't get a single value for this puzzle, but about 22 possible values. Here's the query:
;WITH Matrix AS (
SELECT
x,
y,
s = x + y,
p = x * y,
[Peter has 2 solutions, cannot tell] = CASE WHEN COUNT(*) OVER(PARTITION BY (x * y)) = 2 THEN '1' ELSE '' END
FROM (
SELECT f.x, y = ROW_NUMBER() OVER(PARTITION BY f.x ORDER BY (SELECT NULL))
FROM (VALUES (0),(0),(0),(0),(0),(0),(0),(0),(0),(0)) d (n),
(VALUES (0),(0),(0),(0),(0),(0),(0),(0),(0),(0)) e (n),
(VALUES (1),(2)) f (x)
) d2
WHERE (x < y) AND (x + y <= 100)
), PartialSolution AS (
SELECT *
FROM Matrix m
CROSS APPLY (SELECT [Sam knows Peter cannot tell] = MIN([Peter has 2 solutions, cannot tell]) FROM Matrix mi WHERE mi.s = m.s) x
)
SELECT *
FROM PartialSolution s
CROSS APPLY (SELECT [Sams linked number qualifies too] = MIN([Sam knows Peter cannot tell]) FROM PartialSolution si WHERE si.p = s.p) x
WHERE 1 = 1
--AND [Peter has 2 solutions, cannot tell] > ''
--AND [Sam knows Peter cannot tell] > ''
--AND [Sams linked number qualifies too] > ''
ORDER BY s,p
-- Most of the values of p and s have two solutions. Peter can't tell when p has two solutions.
-- Sarah derives from s the two corresponding values of p. For values of s where the two corresponding values of p are each one of a pair, Sarah can tell that Peter cannot tell.
-- Also, for the 2 values of p (6,10) corresponding to one value of s (7), check the other value of s for each p (s=5 for p=6 and s=11 for p=10). Peter only knows his value p where
-- both values s are flagged as [Sam knows Peter cannot tell].
-- This leaves 22 possible solutions for x and y.
For fast, accurate and documented assistance in answering your questions, please read this article.
Understanding and using APPLY, (I) and (II) Paul White
Hidden RBAR: Triangular Joins / The "Numbers" or "Tally" Table: What it is and how it replaces a loop Jeff Moden
October 5, 2015 at 9:03 am
Here's another method which begins with Ben's logic but returns 22 rows, same as the last solution I posted:
;WITH Matrix AS (
SELECT
x,
y,
s = x + y,
p = x * y,
[Flag1] = CASE WHEN COUNT(*) OVER(PARTITION BY (x * y)) = 1 THEN '1' ELSE '' END
FROM (
SELECT f.x, y = ROW_NUMBER() OVER(PARTITION BY f.x ORDER BY (SELECT NULL))
FROM (VALUES (0),(0),(0),(0),(0),(0),(0),(0),(0),(0)) d (n),
(VALUES (0),(0),(0),(0),(0),(0),(0),(0),(0),(0)) e (n),
(VALUES (1),(2)) f (x)
) d2
WHERE (x < y) AND (x + y <= 100)
)
, FirstPass AS (
SELECT *, [p-pair] = COUNT(*) OVER(PARTITION BY p, [Flag1], [Flag2])
FROM Matrix m
CROSS APPLY (SELECT [Flag2] = MAX([Flag1]) FROM Matrix mi WHERE mi.s = m.s) x
) SELECT * FROM FirstPass
WHERE [Flag1] = '' AND [Flag2] = '' AND [p-pair] = 2
ORDER BY p,s
For fast, accurate and documented assistance in answering your questions, please read this article.
Understanding and using APPLY, (I) and (II) Paul White
Hidden RBAR: Triangular Joins / The "Numbers" or "Tally" Table: What it is and how it replaces a loop Jeff Moden
October 5, 2015 at 9:25 am
There are a few issues with your setup. First, you allow x to be only 1 or 2. According to the problem, x cannot equal 1 (must be >=2), and can be any value less than y such that x+y<=100 (so, for example, x=45, y=54 is allowed).
There should be 2352 x,y pairs at the beginning of the problem.
Cheers!
Viewing 7 posts - 1 through 6 (of 6 total)
You must be logged in to reply to this topic. Login to reply