wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Variation of Daughter's age problem
        
(Message started by: Sameer on Nov 11^th, 2004, 1:14pm)

Title: Variation of Daughter's age problem
Post by Sameer on Nov 11^th, 2004, 1:14pm

This is very similar but not same.

There are two mathematicians Mr. P and Mr. S and they have two subjects S1 and S2. S1 and S2 both guess a number between 2 and 100 (not necessarily unique). They then tell Mr. P the product of their number and Mr. S the sum.

Following conversationg takes place between Mr. P and Mr. S

Mr. P: I don’t know the two numbers
Mr. S: I don’t know the numbers, but I knew you wouldn’t know them either
Mr. P: I know the numbers now!
Mr. S: I know the numbers now also

What combinations of product and sum is this possible to guess?

Title: Re: Variation of Daughter's age problem
Post by Icarus on Nov 11^th, 2004, 5:21pm

A little progress, which I am saving here since I don't have time to follow it any more right now:
[hide]P would know the solution immediately if the numbers were both prime. Therefore the fact that S knows P does not have the answer immediately means that the sum cannot be the sum of two primes. Therefore the sum is either one of the even numbers 174,182,184,188,190,192,196,198,200, or an odd number other than 5,7,9,13,15,19,21,25,31,33,39,43,45,49,55,61,63,69,73,75,81,85,91, 99.

Some of these numbers are also easily eliminated as a sum (200 for instance), but I don't have time to pursue it.
[/hide]

Title: Re: Variation of Daughter's age problem
Post by TenaliRaman on Nov 11^th, 2004, 10:33pm

::[hide]
Actually the sum domain can be restricted further i believe noting that if sum were square of prime or p+p^2, Mr.P would have found that easily (cuz p^3 = p*p^2 has only one form of representation ... the same cannot be said for p^4)....
so numbers like
4,5,9,12,16,25,30,49,56,121,132,169,182
are eliminated ..

i could possibly write up a small prog later this evening for this unless someone else beats me to it ....
[/hide]::

Title: Re: Variation of Daughter's age problem
Post by Sameer on Nov 17^th, 2004, 8:52am

I wonder if this is a pure programatic problem or if some formula exists. ??? I am lost.

Title: Re: Variation of Daughter's age problem
Post by John_Gaughan on Nov 18^th, 2004, 10:30pm

First of all, this does not belong in the "easy" forum ;)

Here is what I can figure out so far. Mr. P does not know the numbers, which implies two things. First, both numbers cannot be prime. Second, there must be at least two sets of numbers that multiply to the product he has. However, condition one is a specialized condition of condition two. Since 1 is not in the domain, a number with at least two sets of multiplicands cannot have exactly two prime factors. This also takes care of the case where n₁ is prime and n₂ == n₁². However, this is all that Mr. P knows. There are quite a few products he could possess, and by my calculations, 3,157 sets of unique multiplicands.

Mr. S. does not know the numbers, so much like Mr. P, he can remove sums that have only one set of addends (e.g. 4, 5, 199, 200). However, generalizing a case to remove any more based on the fact that he knows Mr. P does not know is difficult. This is going to be the key to the riddle. The main difficulty is that he knows from the start that neither of them know: "...but I knew you wouldn’t know them either." The real insight comes in step 3, when Mr. P uses this lack of knowledge to figure it out.

If, based on the sum, he knows that it is impossible to figure out the product, he has to work backwards: get the combinations of all the addends that produce his sum, multiply them, and see how many factors those products have. Progmatically I can keep two lists and check the sum list against the product list. When I do, I find that Mr. S's comment does not remove any possibilities. Maybe there is something I am missing...

Title: Re: Variation of Daughter's age problem
Post by towr on Nov 19^th, 2004, 1:15am

Here's a solution, in dutch
http://www.ai.rug.nl/mas/samenprosem/

Title: Re: Variation of Daughter's age problem
Post by mike1102 on Nov 19^th, 2004, 7:14am

I will assume that the two numbers are integers...
Recall:
odd number + odd number = even number
even number + even number = even number
even number + odd number = odd number

odd number * odd number = odd number
odd number * even number = even number
even number * even number = even number

1. Mr. P's statement that he doesn't know the numbers implys their product is an even number. Thus, at least one of the numbers is even.

2. Mr. S's statement saying that he didn't know the numbers implys their sum is an even number. Thus: the product was also even; Mr. P could not know the numbers and both numbers must be even numbers.

3. Mr P, after hearing Mr. S's statement can now uniquely determine the numbers.

4. I don't see how Mr. S could uniquely determin the numbers without further information. He is left with combinations of even numbers who's sum is known.

Title: Re: Variation of Daughter's age problem
Post by THUDandBLUNDER on Nov 19^th, 2004, 8:19am

Quote:

1. Mr. P's statement that he doesn't know the numbers implys their product is an even number. Thus, at least one of the numbers is even.

The numbers could be 9 and 15, for example.

Title: Re: Variation of Daughter's age problem
Post by Sameer on Nov 19^th, 2004, 9:32am

Maybe this has to do with Goldbach's conjecture. No idea how to use it though.

Title: Re: Variation of Daughter's age problem
Post by mike1102 on Nov 19^th, 2004, 10:18am

THUDandBLUNDER,
My thinking goes like this...........
If Mr. P saw the product was an odd number, e.g. 9*15, he could determine the factors by himself at step one. The fact that he does not make this determination at the onset indicates the product is an even number. Thus, one of the factors must be an even number.

Title: Re: Variation of Daughter's age problem
Post by THUDandBLUNDER on Nov 19^th, 2004, 10:27am

Mike1102, if the numbers were 9 and 15, for example, Mr P would be told 135 = 5*3³
So he couldn't tell if the numbers were
3 and 45
or
9 and 15
or
27 and 5

Title: Re: Variation of Daughter's age problem
Post by John_Gaughan on Nov 19^th, 2004, 4:18pm

THUDandBLUNDER, that is correct. Previous posters tried to make generalizations about this, for example, saying that if a sum S is composed of two primes, this can be removed. However, try taking the number 42. (5,37), (11,31), (13,29), (19,23) are all possibilities. Mr. S cannot know in advance anything about the product based on that sum.

A similar point works for odd numbers as you pointed out. I think that the even/odd issue may be a clincher, but it cannot prune out the 4,949 possible combinations needed.

Title: Re: Variation of Daughter's age problem
Post by Icarus on Nov 19^th, 2004, 10:09pm

Not so. If Mr S's number was 42, then it is possible that the summands are 19 and 23. If this were the case, Mr. P would know the numbers immediately. So Mr. S could not know that Mr. P did not know. The fact that Mr. S already knew that Mr. P did not know tells me that the number Mr. S has cannot be expressed at all as a sum of two primes less than 100 (or as the sum of a prime and its square) - no matter what other means of breaking the number down exist.

If there is even one means of breaking down a number into primes or prime & prime^2, Mr. S cannot have that number.

I can state with certainty that Mr. S's number has to be one of the ones I indicated, throwing out those that meet the sum of a prime and a square condition.

Title: Re: Variation of Daughter's age problem
Post by mike1102 on Nov 22^nd, 2004, 1:24pm

I think maybe we're makeing this riddle too hard....
Let's assume all the statements in the dialogue between Mr. P & Mr. S are true and that there is no additional source of information for either of them. The fact that Mr. P knows the two numbers by statement 3 is very revealing. It also eliminates many possible combinations of numbers.

Taking this into account, Mr P = 12 and can't know if the factors are (6,2) or (3,4). Mr S = 7 and can't decide between (3,4) and (5,2) and goes on to state that he knows Mr P couldn't know either. At this point, we are told Mr. P solves the riddle. For this to have happened, Mr. P must realize Mr. S = 7, (not 8) But I see no basis for Mr. P to have known this from the dialogue alone. He simply guesses the minimum sum for which there are two possible combinations.

Certainly larger values of P & S are possible but they would not allow Mr. P to solve the riddle uniquely. Likewise, the smallest values such as Mr. P= Mr. S =4 would require no dialogue.

Title: Re: Variation of Daughter's age problem
Post by John_Gaughan on Nov 22^nd, 2004, 4:48pm

Icarus, I think something is starting to make sense. Mr. S knows that Mr. P cannot know the numbers. So if the sum were a sum of two primes, then Mr. S would know this and wonder if maybe Mr. P knew the numbers. But he said he knows Mr. P cannot know, so the sum must not be a sum of two primes. As you mention, this works for p + p² as well.

For some reason that little bit of logic escaped me. I get it now. Thank you for explaining it in small words for me ;)

Title: Re: Variation of Daughter's age problem
Post by Icarus on Nov 22^nd, 2004, 5:53pm

Actually, just rereading my previous post and trying to track all the "knows" and "doesn't know" is giving me a headache, and I wrote it! So I'm glad you've managed to figure it out anyway.

Title: Re: Variation of Daughter's age problem
Post by Icarus on Nov 22^nd, 2004, 8:01pm

Consider all pairs of integers between 2 and 100. Call a pair a "giveaway" if the original pair can be deduced from their product. I.e. its product is not the product of another pair. A single number is a "giveaway product" if it is the product of a giveaway pair. A number is "free" if it cannot be written as the sum of a giveaway pair.

Mr. P's first comment reveals that the original pair is not a giveaway. Mr S's first comment reveals that the pair has a free sum.

So the first question is: what pairs are giveaways? The second question is: which numbers are free?

So far, the following giveaway products have been identified:

products of two primes < 100
cubes of primes <10

I would like to add one more:

any product whose largest and smallest prime factors multiply together to give a result > 100.

Such a product would tell Mr. P that the largest prime must be one of the two numbers by itself. For example , if his product were 1665 = 3²[cdot]5[cdot]37, Mr. P would know immediately that his two numbers were 37 and 45, because any other pair of factors has one number > 100.

Each entry in the above list eliminates some numbers from being free.

Any number that can be written as the sum of two primes <100. Thus all even numbers up to 200 are eliminated EXCEPT 174, 182, 184, 188, 190, 192, 196, 198, 200.
It also eliminates the odd numbers 5,7,9,13,15,19,21,25,31,33,39,43,45,49,55,61,63,69,73,75,81,85,91, 99.
Any number that can be written as p+p² for prime p < 10. (i.e. 6, 12, 30, 56) (for higher primes, p²>100).
The new condition eliminates from being free all numbers [ge] 55 = 2+53. It also eliminates all odd sums > 40 = 37 + 3.

Combining the first and third result, the only (potentially) free numbers are
11, 17, 23, 27, 35, 37.

Mr S. has to have received one of these 6 numbers.

From here the rest should be considerably easier, but I am out of time again.

Title: Re: Variation of Daughter's age problem
Post by Icarus on Nov 26^th, 2004, 3:36pm

I've finally chased this down to its end and have a definitive answer: For NO combination of product and sum is this possible.

Starting with the 6 possible values for the sum after Mr. S has made his first statement: 11, 17, 23, 27, 35, 37, I first chose all possible ways of writing these numbers as a sum of two integers >= 2. Then I took the products and for each possible product found all factorizations into two integers, and resummed. Any number with 2 factorizations that summed together to one of the 6 free numbers above, I threw out. Mr. P would not be able to know his factorization from Mr. S's comment if he had one of those products.

The remaining 45 products are: 18, 24, 28, 50, 52, 72, 76, 90, 92, 96, 110, 112, 120, 124, 130, 140, 150, 152, 160, 162, 170, 174, 176, 180, 182, 186, 196, 210, 216, 232, 234, 250, 252, 264, 270, 276, 294, 304, 306, 312, 322, 330, 336, 340, 342. Mr. P could have any one of these. They have exactly one factorization each wherein the factors sum to one of the free numbers that Mr S. could have.

Unfortunately, it breaks down here. All 6 free numbers occur multiple times as a sum of factors of the above. The least case is 17, which is the sum of factors of only 52 (4*13) and 72 (8*9). But Mr S. is supposed to know exactly what the pair is - not just be able to narrow it down to two possibilities.

So as stated, this riddle has no solution.

Title: Re: Variation of Daughter's age problem
Post by SWF on Nov 26^th, 2004, 6:39pm

Does "a number between 2 and 100" mean "an integer from 2 to 100 inclusive"? Everyone seems to be assuming it does. If that is what it means, there is a solution.

Icarus, you are getting very close, but seem to have forgotten that at the end Mr. S makes use of the 2nd statement by Mr. P.

Title: Re: Variation of Daughter's age problem
Post by Barukh on Nov 26^th, 2004, 11:39pm

on 11/11/04 at 13:14:54, Sameer wrote:

This is very similar but not same.

There are two mathematicians Mr. P and Mr. S and they have two subjects S1 and S2. S1 and S2 both guess a number between 2 and 100 (not necessarily unique). They then tell Mr. P the product of their number and Mr. S the sum.

Following conversationg takes place between Mr. P and Mr. S

Mr. P: I don’t know the two numbers
Mr. S: I don’t know the numbers, but I knew you wouldn’t know them either
Mr. P: I know the numbers now!
Mr. S: I know the numbers now also

What combinations of product and sum is this possible to guess?

This problem looks suspiciously familiar to me... But could anybody tell me to what this is similar? ???

Title: Re: Variation of Daughter's age problem
Post by rmsgrey on Nov 27^th, 2004, 5:06am

on 11/26/04 at 15:36:58, Icarus wrote:

72=3*24

[e]I couldn't bring myself to leave it here without pointing out that Icarus did all the work on this one - I've just followed along without bothering to put in the time needed to reduce 9801 possibilities to the handful remaining[/e]

Title: Re: Variation of Daughter's age problem
Post by Barukh on Nov 27^th, 2004, 7:30am

I recalled where I saw the problem: on Nick's Mathematical Puzzles (http://www.qbyte.org/puzzles/puzzle01.html) (#3). Interestingly, the conditions were slightly different, but the solution remained the same.

on 11/17/04 at 08:52:15, Sameer wrote:

I wonder if this is a pure programatic problem or if some formula exists. ??? I am lost.

Good question… One thing I know is that the solution has the form (2ⁿ, p) too often to be a coincidence.

Title: Re: Variation of Daughter's age problem
Post by Grimbal on Nov 29^th, 2004, 9:24am

on 11/26/04 at 15:36:58, Icarus wrote:

Starting with the 6 possible values for the sum after Mr. S has made his first statement: 11, 17, 23, 27, 35, 37, I first chose ...

I find 11 17 23 27 29 35 37 41 47 53

For instance 29:
2+27 2*27 = 3*18
3+26 3*26 = 6*13
4+25 4*25 = 10*10
5+24 5*24 = 10*12
6+23 6*23 = 3*56
7+22 7*22 = 14*11
8+21 8*21 = 4*42
9+20 9*20 = 18*10
10+19 10*19 = 5*38
11+18 11*18 = 22*9
12+17 12*17 = 6*34
13+16 13*16 = 26*8
14+15 14*15 = 7*30

So S knows however the sum is made, the product is ambiguous.

Anyway, here is the program I wrote. It prints only 4 and 13:

#include <stdio.h>

#define TRUE (0==0)
#define FALSE (!TRUE)

#define MAX 100
int multi_p[MAX*MAX+1];
int ok_s[MAX+MAX+1];;
int multi2_p[MAX*MAX+1];
int multi_s[MAX+MAX+1];

// this is to compress the source to a more synthetic expression
#define LOOP for( int x=2 ; x<=MAX ; x++ ) for( int y=x ; y<=MAX ; y++ )
#define S (x+y)
#define P (x*y)

// main: search and display all solutions within the range
int main()
{
// compute the multiplicity of each product
LOOP multi_p[P] = 0;
LOOP multi_p[P]++;
// "P knows" if multi_p[P]==1

// compute which sums only allows multiple products
LOOP ok_s[S] = TRUE;
LOOP ok_s[S] &= (multi_p[P]!=1);
// "S knows that P does't know" if ok_s[S] is true
printf("S knew:");
for( int s=0 ; s<=MAX+MAX ; s++ ) if (ok_s[s]) printf(" %d", s);
printf("\n");

// recompute the multiplicity of products under the condition that S knows that P doesn't know
LOOP multi2_p[P] = 0;
LOOP if (ok_s[S]) multi2_p[P]++;
// "P now knows" if multi2_p[P]==1

// compute the multiplicity of sums under condition that
// "S knows that P doesn't know" and "P now knows"
LOOP multi_s[S] = 0;
LOOP if (ok_s[S] && multi2_p[P]==1) multi_s[S]++;
// "S now also knows" if multi_s[S]==1

// print all combinations where "P now knows" and "S also knows"
LOOP if (multi2_p[P]==1 && multi_s[S]==1) printf("%d %d\n", x, y);

return 0;
}

Title: Re: Variation of Daughter's age problem
Post by Icarus on Nov 30^th, 2004, 9:08pm

on 11/26/04 at 18:39:24, SWF wrote:

Icarus, you are getting very close, but seem to have forgotten that at the end Mr. S makes use of the 2nd statement by Mr. P.

No - My argument was that Mr. P's second statement does not help Mr. S sufficiently. For each of the 6 possible values Mr. S had, it still left more than one pair of numbers that satisfied all previous statements. Or so I thought:

on 11/27/04 at 05:06:10, rmsgrey wrote:

72=3*24

That is what happens when I do it all by hand: one missed factorization, and I make a fool of myself. Since 8+9 =17 and 3+24 = 27, if Mr. P had 72, Mr. S's first statement would not help him in determining which factorization was correct. Therefore Mr. P cannot have 72, and there remains but one possibility for 17: 3,14. Which provides the solution after all, unless the other error I made fouls things up:

on 11/29/04 at 09:24:59, Grimbal wrote:

I find 11 17 23 27 29 35 37 41 47 53

I'm not sure how I missed 29. I've already thrown away my work in deriving my 6 numbers. The error leading to the other missed values is unfortunately all too clear:

Quote:

The new condition eliminates from being free all numbers [ge] 55 = 2+53. It also eliminates all odd sums > 40 = 37 + 3.

I don't know what I was thinking with that last remark. Every number [ge] 55 is eliminated because it could be broken down as 53+x, for some x [ge] 2. If Mr. P had 53*x as his number, he would know immediately that 53 has to be a factor, since any factor of x multiplied by it would give a number >100.

I was somehow under the impression that I could eliminate the odd numbers above 40 with a similar breakdown wherein Mr P would have 37*x and the smallest factor of x would be 3. Now it makes no sense, as for any odd >37, the difference would be even (x would be divisible by 2).

Trusting that Gimbal's routine works right, the answer is that the numbers must be 3 and 14.

Title: Re: Variation of Daughter's age problem
Post by Grimbal on Dec 1^st, 2004, 4:52am

on 11/30/04 at 21:08:14, Icarus wrote:

Trusting that Gimbal's routine works right, the answer is that the numbers must be 3 and 14.

hmmmm?
::)

Title: Re: Variation of Daughter's age problem
Post by rmsgrey on Dec 1^st, 2004, 10:20am

The routine looks good, though I can't be bothered to do a formal correctness proof...

I had wondered a little about the >40 thing, but couldn't convince myself either way...

Title: Re: Variation of Daughter's age problem
Post by SWF on Dec 1^st, 2004, 6:41pm

I still think "between 2 and 100" means 2 and 100 are not included. I think the answer should therefore be (13,16) instead of (4,13). Although 2 and 100 were included the first time I encountered this problem, one should answer the question posed, not the most similar problem you can find elsewhere.

on 11/30/04 at 21:08:14, Icarus wrote:

Sorry, I didn't read the details. I thought you had narrowed it down to 4*13 and 8*9.