[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

779.0. "integer puzzle" by CXCAD::VENNER (You're joking ... right?!) Wed Oct 28 1987 19:49

	I'm not sure of the exact origin of this puzzle, but it's
	definitely one of the harder ones I've tried.  The only
	way i found to solve this was by writing a small program
	but maybe someone else can find a better way.  after a
	little while i'll post my solution along with my program
	that found it.

			----------------------
 
Two distinct integer numbers are picked between 2 and 100 (inclusive).
Mr. P and Mr. S are two (really) outstanding mathematicians.
 
Mr. P is told only the product of the two numbers.
 
Mr. S is told only the sum of the two numbers.
 
Mr. P and Mr. S then have the following conversation:
 
 
Mr. P: "I don't know what the two numbers are."
Mr. S: "I knew that you couldn't know what the numbers are, but
	I don't know them either."
Mr. P: "Now I know what the numbers are."
Mr. S: "Now I know them, too."
 
 
What are the two numbers?
 
			----------------------
T.RTitleUserPersonal
Name
DateLines
779.1solutionCXCAD::VENNERYou're joking ... right?!Fri Oct 30 1987 16:29195
	The solution follows the form feed ...




	the only solution is the two numbers: 4 and 13;

	the following BLISS program can be compiled and link and run
	to yield the result.  hopefully the logic in the code is
	understandable enough whether you know bliss or not.

-------------------------------------------------------------------------------

MODULE a (	MAIN = a_main,
		ADDRESSING_MODE(EXTERNAL = LONG_RELATIVE,
		NONEXTERNAL = LONG_RELATIVE)) =
BEGIN

LIBRARY	'sys$library:starlet';

MACRO desc(name, buffer, size) =
    buffer : vector[size,byte],
    name : block[8, byte]
	preset(
	    [DSC$W_LENGTH] = size,
	    [DSC$B_DTYPE] = DSC$K_DTYPE_T,
	    [DSC$B_CLASS] = DSC$K_CLASS_S,
	    [DSC$A_POINTER] = buffer) %;

EXTERNAL ROUTINE	LIB$PUT_OUTPUT : addressing_mode(general);

FORWARD ROUTINE
	a_main,
	init_prod_table,
	init_sum_table,
	with_product_one_sum_cant_know,
	with_sum_one_product_can_know;

OWN
prod_table	: vector[10000, byte],
sum_table	: vector[200, byte];

!==============================================================================

ROUTINE a_main =
BEGIN

LOCAL
sum,
product,
len,
desc(out_desc, out_buf, 80);

init_prod_table();
init_sum_table();

incr i from 2 to 99 do
    incr j from (.i + 1) to 100 do
	BEGIN
	product = .i * .j;
	sum     = .i + .j;

	if (.prod_table[.product] GTR 1) then				! if product can be generated more than one way
	    if (.sum GTR 6) then					! if sum can be generated more than one way
		if (.sum_table[.sum]) then				! if every sums product can be generated more than one way
		    if with_product_one_sum_cant_know(.product) then
			if with_sum_one_product_can_know(.sum) then
			    BEGIN
			    out_desc[DSC$W_LENGTH] = 80;
			    $FAO(%ascid 'NUMBERS = !UL, !UL;', len, out_desc, .i, .j);
			    out_desc[DSC$W_LENGTH] = .len;
			    LIB$PUT_OUTPUT(out_desc);
			    END;
	END;

RETURN 1;
END;

!==============================================================================

ROUTINE init_prod_table =
BEGIN

LOCAL
product;

incr i from 2 to 99 do
    incr j from (.i + 1) to 100 do
	BEGIN
	product = .i * .j;
	prod_table[.product] = .prod_table[.product] + 1;	! number of number pairs that generate this product
	END;

RETURN 1;
END;

!==============================================================================

ROUTINE init_sum_table =
BEGIN

LOCAL
half_sum,
product,
increment;

incr sum from 5 to 199 do
    BEGIN
    sum_table[.sum] = 1;

    if (.sum)	then half_sum = (.sum / 2)		! not multiple of 2
		else half_sum = (.sum / 2) - 1;		! multiple of 2

    product = 2 * (.sum - 2);
    increment = .sum - 3;

    incr half from 2 to .half_sum do
	BEGIN
	if (.prod_table[.product] LEQ 1) then
	    BEGIN
	    sum_table[.sum] = 0;
	    EXITLOOP;
	    END;

	increment = .increment - 2;			! this is a fast way of calculating x * y from the previous value
	product = .product + .increment;		! (x + 1) * (y - 1) = (x * y) + (y - x - 1)
	END;
    END;

RETURN 1;
END;

!==============================================================================

ROUTINE with_product_one_sum_cant_know ( product ) =
BEGIN

LOCAL
j,
pair_found;

pair_found = 0;

incr i from 2 to .product do
    BEGIN
    j = .product / .i;

    if (.i GTR .j) then EXITLOOP;

    if (.j * .i EQL .product) then
	BEGIN
	if (.sum_table[.j + .i]) then				! if every sums product can be generated more than one way
	    BEGIN
	    if (.pair_found) then RETURN 0;

	    pair_found = 1;
	    END;
	END;
    END;

RETURN .pair_found;
END;

!==============================================================================

ROUTINE with_sum_one_product_can_know ( sum ) =
BEGIN

LOCAL
half_sum,
pair_found;

if (.sum)	then half_sum = (.sum / 2)		! not multiple of 2
		else half_sum = (.sum / 2) - 1;		! multiple of 2

pair_found = 0;

incr half from 2 to .half_sum do
    BEGIN
    if with_product_one_sum_cant_know(.half * (.sum - .half)) then
	BEGIN
	if (.pair_found) then RETURN 0;

	pair_found = 1;
	END;
    END;

RETURN .pair_found;
END;

!==============================================================================

END
ELUDOM
779.2BUT I NEED IT SIMPLE!BRNOUT::LESPERANCEWed Nov 04 1987 02:0228
    
    HELP!
    
    I DON'T KNOW ENOUGH BLISS TO FIGURE OUT WHAT YOU HAVE 
    
    DONE. MYSELF AND SEVERAL FREINDS HAVE PUT SOME EFFORT
    
    INTO THIS PUZZLE AND ALAS TO NO AVAIL.
    
    THIS IS A GREAT PUZZLE I WOULD LOVE TO SEND A MATH TEACHER 
    
    I ONCE HAD.  
    
    BUT, I WOULD LIKE TO KNOW IF YOU OFFER A QUALITATIVE 
    
    EXPLANATION OF YOUR SOLUTION. SO I CAN GAIN AN UNDERSTANDING OF
    
    WHERE YOU CAME FROM.. 
    
    AND THANKS FOR A GREAT BRAIN TWISTER.
    
     
    IF YOU CHOOSE TO MAIL PLEASE SEND TO : BRNOUT::LESPERANCE
    
    THANKS AGAIN,  
    
        MIKE L.
    
779.3qualitative explanationCXCAD::VENNERYou're joking ... right?!Wed Nov 04 1987 19:3534
	Hi,

	Glad you liked the puzzle.  It's really pretty difficult to
	explain this solution in words, but i'll give it a quick shot.

	The solution must be a pair of numbers such that ...

1.	Given the product, it can be generated by more than one pair
	of numbers (product is not unique).

2.	Given the sum, it can be generated by more than one pair of
	numbers (sum is not unique), and for every one of those possible
	pairs the products they generate must also be non-unique.

3.	Given the product, find all the possible values for the sums.
	There must only be exactly one of those possible sums that
	generates all non-unique products.  That's how Mr. P figures it
	out.

4.	Finally, Mr. S must be able to figure it out so ...
	Given the sum, find all possible values for the product, there
	must be exactly one of those products that meets all the criteria
	in the previous step such that Mr. P could have figure it out.  When
	Mr. S determines which of those products can do this he knows
	the solution too.

	I realize that reading these statements quickly will probably
	confuse you, but it's the only way i know of to put the solution
	in words.  If you look at this explanation together with the
	program solution maybe it will make more sense to you.

	- marty

779.4COGITO::ROTHMay you live in interesting timesThu Nov 05 1987 09:138
    I recall working that puzzle out by hand over 10 years ago... it was
    quite something the way the solution evolved.

    In the process, I empirically used something which some else told
    me was the well-known Goldbach's conjecture - that every even
    number is the sum of two odd primes.

    - Jim