Damned logicians...

[Tim West]

This is one I found on a website. The answer's there but I haven't looked at it, so I'm as new to this as anyone else.

There's also a hint on the website, but I'm not checking that yet


--Tim

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

Two perfect logicians, S and P, are told that integers x and y have been chosen such that 1 < x < y and x+y < 100. S is given the value x+y and P is given the value xy. They then have the following conversation.

P: I cannot determine the two numbers.

S: I knew that.

P: Now I can determine them.

S: So can I.

Given that the above statements are true, what are the two numbers? (Computer assistance advisable.)

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

[ravinder thirumala]

is there any logical information in there coversation..,

[Tim West]

Yup, there is....gawd, I can't remember the exact name of this sort of logic, but it's something like knowledge representation logic - the logic of what's known, and who knows what.

I'll look it up when I get home and post a better intro - basically you have predicate symbols for "knowing", ie, K(i, f) means person i knows predicate f. Then, you might say K(j, K(i, f)), that is, person j knows that person i knows f.

So, in this situation, you can start to say things like:

 
f1 = "knows the value x + y".
K(S, f1)          (S knows the value x + y)
K(P, K(S, f1))    (P knows that S knows the value x + y)
C(K(S, f1))       (see below)

The last one is (I'm really scraping my memory here, updates later) the "Kleene closure" of predicate K(S, f1). It means basically "everyone knows this fact, and everyone knows that everyone knows it, and everyone knows that everyone knows that everyone knows it"...and so-on forever.

[UPDATE: it's not "Kleene closure" - that's the closure of a set...I'll look it up later.]

Anyway, I don't know if this level of formal logic is required to answer the problem, but certainly you'll need work with every available fact...things like "P knows that S knows the value x + y, and if P knew if S could determine x and y individually, he could also determine x and y individually".

Erm, I'll leave it at that for now. It really takes a certain sort of mind to "get into" formal logic, and I'm pretty sure that I don't have it



--Tim
[ May 21, 2004: Message edited by: Tim West ]

[Tim West]

Ahh, it's epistemic logic. "Belief representation" and suchlike. Requires some amount of modal logic to understand it, so I advise anyone with some semblance of a social life to stay well away. (For my part, I'm leaving work in an hour )



-Tim

[Stan James]

P says xy is not enough to tell me the answer ( telling S that xy is not the product of 2 primes )

S says I knew that ( telling P that x+y is not the sum of two primes )

P says There are only two numbers that do not add up to the sum of two primes that also multiply to my number!

S says no kidding?

I'm guessing x & y must be fairly small?

[luc ndabaneze]

hi
i may be wrong and the odds are i probably am , but those S and P remind me of quadratic equations formula x^2 + Sx + p where S = x+y and P = xy and knowing both can resolve the roots
could it have anything to do with it?

[C Chavan]

IMO, numbers are x=3 and y=4.

S is given value 7 (x + y) and P is given value 12 (xy).

For P, 12 can result into x=2, y=6 or x=3 and y=4. therefore, he/she can not figure of numbers x and y.

For S, 7 can result into x=2 and y=5 or x=3 and y=4.

The logic S applies is, if numbers were 2 and 5, their product (xy) will be 10 and if P has that value, he/she can figure out the numbers. If numbers were 3 and 4, their product (xy) will be 12 and if P has that value, he/she can not determine whether numbers are 2 and 6 or 3 and 4. As P says it can not figure out the numbers, it means the numbers are not 2 and 5. That leaves x=3 and y=4.

[Stefan Wagner]

3,4 must be wrong.
3x4=12 so far, so good.
P says: I don't know - because 2x6 would have matched too.
S says: I knew (past tense - he knew before!)
His sum is 7.
Might be of 2+5, or 3+4.
If 2+5, then P would have been (2*5)=10. But 10 cannot be split into other factors, so P would have known before.
Therefore S couldn't have known before, that P doesn't knew.

A step ahead is 2 and 9.
Sum is 11.
Every summary leads to ambigious products:
2 * 9 = 18 Ps: 2
3 * 8 = 24 Ps: 3
4 * 7 = 28 Ps: 2
5 * 6 = 30 Ps: 3
So S may know before, that P can not know.
If P is 18, he knows: factors migth be 2*9 or 3*6.
If it was 3*6, S must be 9.
But 2+7 leads to S 9 as well, and 2*7 is 14, and 14 is an unambigious Product which contradicts Rule 2.
So S would know, that (2,9) is the solution.

But I didn't test any further, to see, whether there are more matches.
Very funny to test Product 102.
[ May 26, 2004: Message edited by: Stefan Wagner ]

[Stan James]

I like 2 & 9 using the bits I laid out before:

P says I don't know the two numbers because 18 is not the product of two primes

S say I knew that because 11 is not the sum of two primes

P says 3,6 would add up to 9, the sum of two primes. Can't be 3,6.
P says 2,9 would add up to 11, not the sum of two primes, bingo!

Who wants to prove 2,9 is the only pair that works?

You could shorten the conversation to one line: S says "You can't tell the two factors by looking at the product."

[Stefan Wagner]

Well - take p=24 or 28

Ppx, pysx, sySP(S)count possible factors
p=18
px=2, y=9 sum=11
x=2, y=9prod =18matcher:2
x=3, y=8prod =24matcher:3
x=4, y=7prod =28matcher:2
x=5, y=6prod =30matcher:3
px=3, y=6 sum=9failed!
 
p=24
px=2, y=12 sum=14failed!
px=3, y=8 sum=11
x=2, y=9prod =18matcher:2
x=3, y=8prod =24matcher:3
x=4, y=7prod =28matcher:2
x=5, y=6prod =30matcher:3
px=4, y=6 sum=10failed!
 
p=28
px=2, y=14 sum=16failed!
px=4, y=7 sum=11
x=2, y=9prod =18matcher:2
x=3, y=8prod =24matcher:3
x=4, y=7prod =28matcher:2
x=5, y=6prod =30matcher:3

failed! means: There is at least one Product, with 'matcher:1',
so P would have known before.

[Stan James]

I don't follow that approach atoll. Did you propose an x-y pair that the two philosophers can solve?

[Tim West]

I think the problem with approaches so far is that they don't prove that the numbers given are the only numbers that have the properties proposed.

In order for the logicians to work out the numbers, we need to demonstrate that they can rule out every other pair of numbers x, y.

I have some ideas but I haven't got time to type them up now


--Tim

[Stefan Wagner]

Well - I'm somehow stuck.

I'm trying to test all possible products.
Let's start with 10, which could be the product of (2,5).
P could tell immediately that the factors are (2,5).
This violates Sentence a) (of a,b,c,d)

For 12, there are two pairs, (2,6) and (3,4).
Ok with a).
S would have a sum of 8 or of 7.
If he has a sum of 8, he can split it into 2,6 and 3,5.
If the terms where (3,5) their product would be 15, and there is only one factorcombination possible to solve x*y=15. But S says in b), he knew before, that P doesn't know.
If the sum is 7, the terms might be 2,5 or 3,4.
2*5 = 10 leads to knowledge of P - violates b)
Both possibilities are violated, so 12 can't be P.

My program so far generates every Product, and counts the possibilities, to generate that product.
If the count is 1, condition a) is violated.
If the count is > 1, I generate the sum for every matching combination of factors.
Then I divide the sum into every possible addends, it could have been build from, because S doesn't know the addends, but only the sum.
For these addends, I build the product, and search again for all factors, which can build this product.
If there is a product, which can only be build in one way, P could have known the factors, which violates b) and my program prints: 'failed'.

The remaining products are candidates, to solve the problem, but I don't know how to go ahead from here.

[Stan James]

Would this work?

compute all primes to 100
compute all sums of two primes 
compute all products of two primes 
for possible product (2 .. 9900)
   if the product is not in the product list
      for each possible set of terms
         if the sum of terms is not in the sum list
            count++
         end if
      next
      if count is exactly 1
         the terms are solvable
      end if
   end if
next

[ May 28, 2004: Message edited by: Stan James ]

[Stefan Wagner]

minor critique:
---
products from 2...9900 ?
1 < x < y -> x >=2, y>=3 -> products from 6...
x+y < 100
x=49, y=50 -> x*y = 2450
From geometry, we know the maximum area of a rectangle is a square, therefore (x-i) * (y+i) has a maximum for i=0 if x < y.

so generate products from 2...2450
---
questions:
where do you reset count?
and what means: "for each possible set of terms" ?

why don't you implement it?
Shall the whole question be solved?

[ May 28, 2004: Message edited by: Stefan Wagner ]
[ May 28, 2004: Message edited by: Stefan Wagner ]

[Stan James]

Ah, good. I missed x+y<100. I thought it was x and y are each < 100.

Possible terms are pairs of factors for the product. Reset count for each new product we try. Computing non-candidate sums & products ahead of time was an implementation idea. The real requirement is to see if a sum is the sum of two primes or a product is the prouct of two primes. Another implementation would be fine.

Are we going adrift testing all the products? Should we test all the pairs since that's what the problem is about?

[Stefan Wagner]

Something like this (1.5 notation):

public StanJames () 
{
List <Integer> lPrimes = computeAllPrimes (100);
List <Integer> lSums = computeAllSumsOfTwoPrimes (lPrimes);
List <Integer> lProducts = computeAllProductsOfTwoPrimes (lPrimes);

for (int p = 6; p < 2450; ++p)
{
int count = 0;
if ( ! lProducts.contains (p))
{
// each possible set of terms)
List<SumKombi>  lTerms = computeAllTermsFor (p);
for (SumKombi sum : lTerms)
{
if ( ! lSums.contains (sum.sum))
{
++count;
// System.out.print (".");
}
else System.out.print ("-");
}
if (count == 1)
{
System.out.println ("the terms are solvable");
}
}
}
System.out.println ();
}

(Prints only "----", not 'the terms are solvable' )

I generate lists of Product- and Sum-matchers before too (as implementation detail).

btw.: I guess I got the solution.
The product is in this list:

18 24 28 50 52 54 76 92 96 100 110 112 114 124 130 138 140
148 152 154 160 162 168 170 172 174 176 182 186 190 198 204
208 216 232 234 238 240 246 250 252 270 276 280 282 288 294
304 306 310 336 340 348 360 364 370 378 390 396 400 408 414
418 430 442 480 492 496 510 520 522 532 540 550 552 570 592
612 630 646 660 672 682 690 696 700 702

and the sum is in this list:
11 17 23 27 29 35 37 41 47 53

and the solution is:
011110000011110100110100001011000010000001111001001111010011000100110011

[Tim West]

Well done Stefan

I was gonna throw my own ideas in but I've been a bit busy at work.

FWIW, this problem and another solution can be found here.


--Tim

[Stan James]

Great fun! I had a start on the algorithm but went astray not realizing that 11 could be the sum of non primes for another product. Or something like that.

[Stefan Wagner]

Thanks, Tim.

I will not try to solve the linked problems - I could get addicted.

I didn't mention that the the other thread, Einsteins riddle, is from 2003, so I started to find a java-solution myself.
I got stuck, and looked at the posts, saw the solving immediately, but no algorithm to solve it (some posters wanted to post their solution soon .

It was only pushed up for a comment about the fish...

If somebody is interested in my code <1.5> ...