greil@guug.guug.de (Anton Greil) (08/02/90)
Can you solve the following puzzle by SQL?
"Here is an arithmetical problem which is belonging to the great
classics. Two natural numbers were selected which are greater
than 1 and less than 100. The sum of these two numbers was told
Mr. S, the product of the numbers was told Mr. P.
Each of the two men doesn't know the number of the other. Mr. P
rings up Mr. S:
P: I can't find the two numbers.
S: I knew, that you would not succeed.
P: Oh ... But now, I know them!
S: In this case, I know them too."
(from: Jaques ARSAC: Jeux et casse-tete a programmer, Paris 1985
Computer Denkspiele, selbst programmiert,
Muenchen 1987)
There is just one solution for this problem!jkenton@pinocchio.encore.com (Jeff Kenton) (08/17/90)
From article <125@guug.guug.de>, by greil@guug.guug.de (Anton Greil): > > Can you solve the following puzzle by SQL? > > "Here is an arithmetical problem which is belonging to the great > classics. Two natural numbers were selected which are greater > than 1 and less than 100. The sum of these two numbers was told > Mr. S, the product of the numbers was told Mr. P. > > Each of the two men doesn't know the number of the other. Mr. P > rings up Mr. S: > > P: I can't find the two numbers. > S: I knew, that you would not succeed. > P: Oh ... But now, I know them! > S: In this case, I know them too." > The two numbers are 3 and 14. Solved by following the clues: > P: I can't find the two numbers. Therefore, the PRODUCT has at least 3 prime factors, all less than 50. > S: I knew, that you would not succeed. Therefore, all decompositions of the SUM into two numbers must produce a product which satisfies the condition above. This leaves 11, 17, 23, 27, 29, 35, 41, 47 and 51. > P: Oh ... But now, I know them! Therefore, of all the factorings of the PRODUCT into two numbers, in only one case is the sum of those numbers in the list above. > S: In this case, I know them too." Therefore, of all decompositions of the SUM into two numbers exactly one produces a product which, when factored into pairs of numbers, has only one of those pairs whose sum is in the list above. Only the sum 17 satisfies this last condition (with the pair 4 + 13). - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - jeff kenton --- temporarily at jkenton@pinocchio.encore.com --- always at (617) 894-4508 --- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
jkenton@pinocchio.encore.com (Jeff Kenton) (08/17/90)
From article <12518@encore.Encore.COM> I wrote: > From article <125@guug.guug.de>, by greil@guug.guug.de (Anton Greil): >> >> Can you solve the following puzzle by SQL? >> > The two numbers are 3 and 14. Solved by following the clues: ^^^^^^^^ > > . . . > > Only the sum 17 > satisfies this last condition (with the pair 4 + 13). > The two numbers are 4 and 13. Amazing how my fingers betray me. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - jeff kenton --- temporarily at jkenton@pinocchio.encore.com --- always at (617) 894-4508 --- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
cosell@bbn.com (Bernie Cosell) (08/19/90)
jkenton@pinocchio.encore.com (Jeff Kenton) writes: }From article <125@guug.guug.de>, by greil@guug.guug.de (Anton Greil): }> }> Can you solve the following puzzle by SQL? }> }> "Here is an arithmetical problem which is belonging to the great }> classics. Two natural numbers were selected which are greater }> than 1 and less than 100. The sum of these two numbers was told }> Mr. S, the product of the numbers was told Mr. P. }> }> Each of the two men doesn't know the number of the other. Mr. P }> rings up Mr. S: }> }> P: I can't find the two numbers. }> S: I knew, that you would not succeed. }> P: Oh ... But now, I know them! }> S: In this case, I know them too." }... Solved by following the clues: }> P: I can't find the two numbers. }Therefore, the PRODUCT has at least 3 prime factors, all less than 50. ... But he didn't ASK to have it solved by 'following the clues' [not to mention the explicit request about 'SQL', I assume from his mentioning that it is a classic that he is familiar with the traditional solution There is no problem with posting it, of course, but we have NOT yet solved the problem he posed. It is pretty mindboggling that one could specify an SQL query that would return JUST the pair of numbers that solves theproblem... The matter at hand is NOT to solve the puzzle, per se, but to come up with *SQL* to solve it... /Bernie\
greil@guug.guug.de (Anton Greil) (08/20/90)
As a result of 'SQL finger training' my SQL solution to a fine arithmetical puzzle (to demonstrate, how 'handy' SQL can be in set theoretic reasoning ...). > "Here is an arithmetical problem which is belonging to the great > classics. Two natural numbers were selected which are greater > than 1 and less than 100. The sum of these two numbers was told > Mr. S, the product of the numbers was told Mr. P. > > Each of the two men doesn't know the number of the other. Mr. P > rings up Mr. S: > > P: I can't find the two numbers. > S: I knew, that you would not succeed. > P: Oh ... But now, I know them! > S: In this case, I know them too." > (There's exactly one single solution !) SQL - SOLUTION ============== (With SQL from ACCELL/UNIFY, but equivalently in other SQL's) 1. SQL - DDL (ACCELL IDS 1.4 / UNIFY) ========= DATA DICTIONARY REPORT Schema Listing TABLE/FIELD REF TYPE LENGTH LONG NAME DESCRIPTION numbers 100 numbers numbers 2 - 99 *number_k NUMERIC 2 value algebra 5000 algebra all sums & products *alg_key COMB key of numbers between alg_n1 NUMERIC 2 number1 2 and 99 alg_n2 NUMERIC 2 number2 alg_sum NUMERIC 3 summ alg_prod NUMERIC 4 prod p1 5000 p1 possible products *p1_v NUMERIC 4 value after P's 1st call p2 5000 p2 possible products *p2_v NUMERIC 4 value after P's 2nd call s0 200 s0 possible sums before *s0_v NUMERIC 3 value S's 1st call s1 200 s1 possible sums after *s1_v NUMERIC 3 value S's 1st call s2 200 s2 possible sums after *s2_v NUMERIC 3 value S's 2nd call DATA DICTIONARY REPORT Table List TABLE NUMBER EXPECTED LENGTH ================================================== algebra 3 5000 12 numbers 1 100 6 p1 4 5000 6 p2 5 5000 6 s0 8 200 6 s1 6 200 6 s2 7 200 6 2. SQL - DML (ACCELL IDS 1.4 / UNIFY) ========= insert into numbers: from 'DMP/numbers.dmp' / insert into algebra (number1, number2, summ, prod): select n1.value, n2.value, n1.value + n2.value, n1.value * n2.value from numbers n1, numbers n2 where n1.value <= n2.value / insert into p1: select prod from algebra group by prod having count(*) > 1 / insert into s0: select unique algebra.summ from algebra / insert into s1: select s0.value from s0 where 0 = select count (*) from algebra where s0.value = algebra.summ and not algebra.prod in select p1.value from p1 / insert into p2: select algebra.prod from algebra where algebra.summ in select s1.value from s1 ; group by algebra.prod having count (*) = 1 / insert into s2: select algebra.summ from algebra where algebra.summ in select s1.value from s1 ; and algebra.prod in select p2.value from p2 ; group by algebra.summ having count (*) = 1 / select algebra.number1, algebra.number2, algebra.summ, algebra.prod from s2, p2, algebra where s2.value = algebra.summ and p2.value = algebra.prod /