Two numbers and two logicians [Archive] - Two Plus Two Older Archives

View Full Version : Two numbers and two logicians

jason_t

07-23-2005, 07:14 PM

Two perfect logicians, Godel and Tarski, are told that two integers m and n are chosen so that 1 < m < n and m + n < 100. Godel is told the value of m + n and Tarski is told the value of mn. The following dialogue takes place.

Tarski: I cannot determine the two numbers.
Godel: I already knew that.
Tarski: Now I can determine them.
Godel: As can I.

The above statements are true. What are the two numbers?

Please post solutions in white.

The Dude

07-23-2005, 07:20 PM

Anaheim is not Los Angeles.

random

07-23-2005, 07:24 PM

I gave up and cheated. Yeah, there was no way I was going to get that.

Piz0wn0reD!!!!!!

07-23-2005, 08:00 PM

3 and 17?

jason_t

07-23-2005, 08:34 PM

[ QUOTE ]
 3 and 17? 

[/ QUOTE ]

No.

Xelent

07-23-2005, 09:15 PM

I just don't understand how the fact that Godel knows Tarski cannot determine the numbers would lead to them both knowing because there are so many combinations that work.

Xelent

07-23-2005, 09:25 PM

nevermind I understand, I overlooked the fact that they are perfect logicians. ick, didn't realize how much work involved in this problem. I'll do it over lunch.

kurosh

07-23-2005, 09:37 PM

I'm sick at the moment so I can't think very well. Once I'm better I'll be able to figure out a formula, but basically the way it's done is like this. For the m + n guy, the only requirement is that the number be greater than 7 for him not to be able to determine it. For the other guy, the number has to <=2450, >=6 and have more than two factors, not including 1 (i think that's the right term).

I'm sure there's a formula way of doing it and like I said, once I'm not feverish I'll figure it out but it'd go something in the manner of, ok, addition guy has 7. That means possible m and n values are 4/3 and 5/2. That means multiplication guy can have 10 or 12. It can't be 10 because it only has two factors besides 1 and the guy could figure it out on his own. Can it be 12? Factor combinations for 12 are 6/2 and 4/3... and I just lost it. I'll be back when I don't have a fever and can think well.

Piz0wn0reD!!!!!!

07-23-2005, 09:38 PM

3 and 7!?!?!

Xelent

07-23-2005, 09:59 PM

multiplying all valid products, the only standalone sum was 17. All other eligible sums had multiple combinations. My answer is 4 and 13.

jason_t

07-23-2005, 10:18 PM

[ QUOTE ]
 multiplying all valid products, the only standalone sum was 17. All other eligible sums had multiple combinations. My answer is 4 and 13. 

[/ QUOTE ]

You didn't even use the conversation.

jason_t

07-23-2005, 10:21 PM

[ QUOTE ]
 3 and 7!?!?! 

[/ QUOTE ]

No.

PairTheBoard

07-24-2005, 01:01 AM

Begin


I'll refer to Tarski's and Godel's statements as T1,G1,T2,G2

Pairs of primes are excluded by T1. Also excluded are any two numbers over 50. Also exluded are pairs where any prime factor of one number is greater than 99 divided by the other number. Also excluded are the pairs (2,4),(3,9),(5,25),(7,49)

G1 Sums exclude those numbers which can be written as the sum of two numbers excluded by T1.

T2 pairs are those not excluded by T1, such that exactly one combination of primes in the product yields a sum not excluded by G1.

Finally, a G2 sum is one not excluded by G1, such that exactly one pair yielding the sum is a T2 pair.

List primes for reference:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61, 67,71,73,79,83,89,97

Listing G1 numbers. Notice 57=53+4, 59=53+6 etc.
11,17,23,27,29,35,37,41,47,51,53

11=9+2 is a T2 pair since 3+6 is not G1
11=8+3 is a T2 pair since 4+6 and 2+12 are not G1
So 11 does not produce a unique T2 pair and thus is not G2.

17=15+2 is not T2 since 5+6 is G1
17=14+3 is not T2 since 2+21 is G1
17=13+4 is T2 since 26+2 is not G1
17=12+5 is not T2 since 3+20 is G1
17=11+6 is not T2 since 33+2 is G1
17=10+7 is not T2 since 2+35 is G1
17=9+8 is not T2 since 3+24 is G1
So 17 produces the unique T2 pair (13,4).

We could exhastively show the remaining G1 numbers do not produce unique T2 pairs but this is unnecessary because the logicians must have already done this in order to make the G2 statement possible.

Therefore the numbers are 4 and 13.


End

I'm still thinking about those 12 marbles though.

PairTheBoard

snappo

07-24-2005, 01:12 AM

2 and 3

PairTheBoard

07-24-2005, 01:42 AM

Addendum

I should probably correct my last statement to say, it's not the G2 statement that allows us to dismiss the other G1 numbers as candidates but the fact that the puzzle master has told us we can reach the conclusion based on the information given. If we checked the other G1 numbers and found another that produced a unique T2 pair, then we could not come to a conclusion. Since the puzzle says we can come to a conclusion we know that if we did check the other G1 candidates none would produce a unique T2 pair.


End

PairTheBoard

jason_t

07-24-2005, 05:59 AM

[ QUOTE ]
2 and 3 

[/ QUOTE ]

No.

Darryl_P

07-24-2005, 08:27 AM

I agree with 4 and 13 because you can use a sieve of Eratosthenes-type method to reduce the possibilities for the sum of n+m to:

11,17,23,27,29,35,37,41,47,51,53,57,59,65,67,71,77 ,79,83,89,93,95,97

after the first two parts of the conversation. If the sum were anything else, it would have been impossible for Godel to make the statement he did.

Then starting with a sum of 11 you can check the possible pairs of numbers to see if the rest of the conversation makes sense...

With 11 it can't happen because the possible numbers are:

2,9
3,8
4,7
5,6

Here Godel could not possibly have known whether (2,9) or (4,7) were correct because the first three lines of the conversation could have taken place in either case. So a total of 11 must be ruled out.

Next is 17...

Here the possibilities are:

2,15
3,14
4,13
5,12
6,11
7,10
8,9

Here the only pair for which Tarski could have stated what he did is (4,13). For all others there are at least 2 sums that could have been possible from Godel's statement. For example, in the case of (2,15), the product of 30 could be arrived at with (2,15) or (5,6), each of which would have produced a sum on the above list making it impossible for Tarski to know the sum. The other possiblilities can be ruled out accordingly.

We now have one possible solution. To prove that there are no others we'd have to examine all the sums above 17 which is a tedious task indeed, but we can at least rest assured that either we have found the solution or the question has no unique solution.

SL__72

07-26-2005, 05:36 PM

2 and 8?

jason_t

07-26-2005, 05:51 PM

[ QUOTE ]
 2 and 8? 

[/ QUOTE ]

No.

sirio11

07-26-2005, 06:23 PM

The numbers are 4 and 13

hobbsmann

07-26-2005, 07:18 PM

m = 2 and n = 6
Tarski knows that the product is 12 so therefore m=2 and n=6 or m=3 and n=4.
Then since Godel states that he already knew that Tarski didn't know, Tarski was able to deduce that the sum of m+n must be greater than 7 and therefore the numbers have to be 2 and 6.

I'm not completely sure about this because I've assumed a priori what the product is, but since this would fit lets go with it...

man

07-26-2005, 10:44 PM

from my friend
2 and 6 can't be right. 2+6 is 8. 3+5=8 as well. if m and n are 3 and 5, then mn is 15, and the only factors of 15 are 1, 3, 5 and 15. since m and n can't be 1, they must be 3 and 5. therefore, if the second man sees 8, he can't be sure. my guess is 2 and 9.

RJT

07-26-2005, 10:58 PM

Just started thinking here. I think it has something to do with n being a negative integer. No n is 0 maybe. Gotta think on this.

ihardlyknowher

07-26-2005, 11:23 PM

Since, Tarski does not now, at least one on m or n is non-prime. Since Godel already knew that, m+n cannot be expressed as the sum of two primes. Since, Tarski now knows, mn's prime factorization contains exactly three terms.

mn=a*b*c, where a, b, & c are all prime
WLOG, m+n=ab+c, which cannot be expressed as the sum of 2 primes.

I am stuck there. My brain hurts. /images/graemlins/mad.gif

HolyBejeesus

07-27-2005, 08:56 AM

[ QUOTE ]

WLOG, m+n=ab+c, which cannot be expressed as the sum of 2 primes.

[/ QUOTE ]

 Goldbach's conjecture, which is unproven, (but has certainly been tested for numbers less than 100), states that any even number can be expressed as the sum of 2 primes. Therefore m+n is odd, and exactly one of m and n is even. I don't know how to continue from there though.

man

07-27-2005, 09:16 AM

they key is the fact that only one of the pair of numbers that adds up to m+n can be such that mn is the product of 3 primes. Probability dictates that m+n must be a small number, because the odds of there being no other two numbers that qualify become impossible. So start with the low numbers, and you find that 11 works at m+n, and the only possible solution is 2 and 9

Darryl_P

07-27-2005, 09:58 AM

2 and 9 is not the answer because Godel could not have been able to figure it out from the first 3 statements.

Assume 2 and 9 is the answer. In this case Godel knows the sum is 11 which makes the possibilities (2,9), (3,8), (4,7) or (5,6)

Tarski knowing the numbers from Godel's statement only rules out (5,6) and nothing else.

There is no way Godel could have known it was not (3,8) or (4,7) because Tarski would have made the same statements in these cases as well.

durron597

07-27-2005, 11:07 AM

Ok I had a whole writeup of this before but I managed to confuse myself and then got sidetracked so I lost it. Alright. Let's start from the beginning:

If Tarski cannot determine the two numbers then we know that they are not both prime. Also they cannot multiply to the cube of a prime (since 5^3 can only be factored into 5 and 25).

If Godel already knew that, then the number must be one that can never be split in such a way that we get two primes, or the sum of a number and it's square, or two numbers that because of the 100 sum rule can only be factored in 1 way. Because of the "two primes" rule, by Goldbach's Conjecture we can eliminate all the even numbers for the sum. Further, we know that all odd numbers can only be expressed as the sum of an even and an odd, and the only even prime is 2. Thus as a preliminary list we can start with all the odd numbers that are two greater than a composite. This list is: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53... Note that 51 (or any prime above 10 * 3) can be removed off the list because if the two numbers were 17 and 34 then we know that is the only possible factorization of 578, as 2 * 289 sums to greater than 100. Similar logic holds for any prime above 10 * 3. Also at this point numbers start to be expressable as 2 * prime1 + prime2, where prime1 and prime2 are both above 10, so 2 and prime1 * prime2 are not possible factorizations. I didn't rigorously check every possible sum up to 99 but I decided that the answer was almost certainly in the range 11, 17, 23, 27, 29, 35, 37, 41, 47, 53. (This is the spot where I confused myself earlier, when I got lazy about rigorously proving that 53 is the highest possibility with the information we have so far).

Now, if Tarski can figure out what the answer was from the fact that Godel already knew that, then that means that his number cannot be factored into more than one of these choices. So if we start checking even products that have more than 1 factor (2 * prime omitted for brevity), (I didn't get very far with this until I found what must be the answer), 12 cannot be done, 18 has 2/9 which is 11, 24 has 3/8 which is 11, 28 has 4/7 which is 11, 30 has more than 1 (5/6 = 11, 2/15 = 17), 32 cannot be done (trivially, it is a power of 2) 36 cannot be done, 40 cannot be done, 42 has more than 1 (2/21 = 23, 14/3 = 17), 44 cannot be done, 48 cannot be done, 52 has 4/13 which is 17, 54 has 2/27 which is 29, 56 cannot be done, 60 has more than 1 (12/5 = 17, 20/3 = 23), 64 is trivial (power of 2), 66 has more than 1 (2/33 = 35, 6/11 = 17), 68 cannot be done, 70 has more than 1 (2/35 = 37, 7/10 = 17), 72 has more than 1 (8/9 = 17, 24/3 = 27). Thinking ahead, I stopped here for the reason described below.

Thinking about the last statement, Godel would only be able to figure out the number if it was a sum that occured only once in the above list. Notice that 17 only occurs once as a sum in the valid choices above (4/13 case). All of it's other cases are invalidated because then Tarski could not figure it out. While it is theoretically possible that there could be another number that only occurs once validly in the above list, the fact that the original question is even askable proves the solution is unique (I think). So I stopped when I had one valid answer.

The two numbers are m = 4, n = 13.

wheeler

07-27-2005, 11:43 AM

Answer: 1 and 16

I can't believe no one got it already. (I must admit I used Mathematica to do the tedious bits.)

Edit: neat puzzle!

mack848

07-27-2005, 11:51 AM

[ QUOTE ]
Answer: 1 and 16

[/ QUOTE ]

But both m and n are >1.

wheeler

07-27-2005, 11:57 AM

[ QUOTE ]
But both m and n are >1.

[/ QUOTE ]

Thank you. I'm an idiot. I screwed up and solved the 1 <= m < n problem, which surpising also has a unique answer!

durron597

07-27-2005, 01:36 PM

[ QUOTE ]
Answer: 1 and 16

I can't believe no one got it already. (I must admit I used Mathematica to do the tedious bits.)

Edit: neat puzzle!

[/ QUOTE ]

Um, I got it, and my answer is correct unlike yours.

Sirio got it before me except he didn't post the solution, just the answer.

TomCollins

07-27-2005, 04:39 PM

T1: I cannot determine the two numbers- He can only deduce his number is not the multiple of two primes.
G1: I already knew that- He knows that his number cannot be the sum of two primes.

Now the tedious parts.

PairTheBoard

07-27-2005, 05:08 PM

[ QUOTE ]
[ QUOTE ]
Answer: 1 and 16

I can't believe no one got it already. (I must admit I used Mathematica to do the tedious bits.)

Edit: neat puzzle!

[/ QUOTE ]

Um, I got it, and my answer is correct unlike yours.

Sirio got it before me except he didn't post the solution, just the answer.

[/ QUOTE ]

I got it, and I think my proof is easy to follow.

PairTheBoard

kyro

07-27-2005, 05:10 PM

I spent a lot of time on this one. I'm patting myself on the back now.

durron597

07-27-2005, 07:21 PM

[ QUOTE ]

I got it, and I think my proof is easy to follow.

PairTheBoard

[/ QUOTE ]

I'm a douche /images/graemlins/wink.gif

wmspringer

07-30-2005, 01:28 AM

Hmm.

Since T cannot determine m and n, mn must be some number with more than 2 distinct factors other than itself and 1 (as 1 is not allowed and n,m are different)

Since G knew T couldn't determine m,n, n+m must have no two distinct prime numbers that add up to get it. (Every composite number is the sum of primes, but not necessarily of two distinct primes)

After the first two statements, T takes every set of two numbers that multiply to get mn, removes those that add up to a number which is the product of two primes, and has one possibility left.

After the third statement, G knows that T was able to do that, so he can find the numbers as well.

But I'm not gonna go through all the integers up to 100 to figure out which ones it was :-p

wmspringer

07-30-2005, 01:34 AM

[ QUOTE ]
Just started thinking here. I think it has something to do with n being a negative integer. No n is 0 maybe. Gotta think on this. 

[/ QUOTE ]

 You forget that it's given that m and n are both greater than 1

lgas

08-16-2005, 11:57 PM

I think the answer is: 2 and 15