Ron Barnette's Zeno's Challenge #53 result

Ron Barnette's Zeno's Coffeehouse Challenge #53 Result

Dear Zeno's patrons: Here are the results of our previous challenge on Chris and Trudy. I have listed the original problem, with three results featured below. Thanks to all Zeno's patrons who took up the challenge! Over 100 entries were received, and I have included results which raise serious issues with this challenge, which became a very complicated one indeed! On reflection, the original question raised more issues than I anticipated! Look over these thoughts. Thanks for your critical thinking, and please take up the next Zeno's Challenge:)

Ron Barnette

While chatting with patrons at Zeno's recently, Maggie introduced two newcomers to the group gathered.

"I'd like you meet Chris and Trudy, who are visiting the Coffeehouse and who have learned about our interest in challenging puzzles and logic. They are renowned logicians, who, allegedly, are able to correctly deduce any derivable truth from any set of assumptions. So Charles and I have arranged the following, to set up our current Zeno's Challenge: We have selected two integers (not necessarily unique) such that each is within some specified range (we have kept these integers a secret between us). We now give Chris the sum of these two integers [which they do], and give Trudy the product of these two integers [which they provide]."

After receiving these numbers, Chris and Trudy do not have any communication at all except the following dialogue in the Coffeehouse:

Trudy: "I do not know the two numbers."
Chris: "I knew that you didn't know the two numbers."
Trudy: "Now I know the two numbers."
Chris: "Now I know the two numbers."

Maggie adds, "Given that the above statements are absolutely truthful, can anyone deduce the two numbers that Charles and I selected for Chris and Trudy?"

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

Three replies are included, which represent detailed thoughts expressed about this problem. My deep appreciation is extended to their analyses. RB

Topi Linkala (Finland) writes:

In the following 1 is considered to be a prime.

If either or both of the numbers are less than equal to zero then Trudy has no way to know the numbers.

If the product is zero then no way Trudy know what the other number is.

If the product is negative she cannot assign the sign to one of the numbers.

And if the product is positive but both of the numbers are negative then Trudy wouldn't know that based on the conversation.

So we need to check only the number pairs where both numbers are larger than zero.

The product cannot be a prime or Trudy would know that the numbers were 1 and the prime.

The sum of the integers cannot be 1+prime because then Chris wouldn't know that Trudy cannot know the numbers.

If this helps Trudy to know the numbers the product must be in form:

A) 2^n, n>1 such that for all i,j|i>0,j>0,i<=j,i+j=n 2^i+2^j is 1+prime in which case the pair of numbers is (2^n,1)

B) (2n+1)(2m+1),n,m>1 such that for all i>1 that is a factor of (2n+1)(2m+1) the sum i+(2n+1)(2m+1)/i is 1+prime in which case the pair of numbers is ((2n+1)(2m+1),1)

So A) gives:

2^2 = 4, 2+2 = 1+3, ok.
2^3 = 8, 2+4 = 1+5, ok.
2^4 = 16, 2+8 = 1+9, not ok.
2^5 = 32, 2+16 = 1+17, 4+8 = 1+11, ok.
2^6 = 64, 2+32 = 1+33, not ok.
2^7 = 128, 2+64 = 1+65, not ok.
2^8 = 256, 2+128 = 1+129, not ok.
2^9 = 512, 2+256 = 1+257, 4+128 = 1+131, 8+64 = 1+71, 16+16 = 1+31, ok.
etc.

All of these have unique sums in the forn 1+2^n so Chirs will know how to divide the sum properly.

B) gives:

3*3=6, 3+3=1+5, ok.
3*5=15, 3+5=1+7, ok.
5*5=25, 5+5=1+9, not ok.
3*7=21, 3+7=1+9, not ok.
3*11=33, 3+11=1+13, ok.
5*7=35, 5+7=1+11, ok.
7*7=49, 7+7=1+13, ok.
5*11=55, 5+11=1+15, not ok.
7*11=77, 7+11=1+17, ok.
11*11=121, 11+11=1+21, not ok.

3*3*3=27, 3+9=1+11, ok.
3*3*5=45, 3+15=1+17, 5+9=1+13, ok.
3*3*7=63, 3+21=1+23, 7+9=1+15, not ok.
3*5*5=75, 3+25=1+27, not ok.
3*5*7=105, 3+35=1+37,5+21=1+25, not ok.
5*5*5=125, 5+25=1+29, ok.
3*7*7=147, 3+49=1+51, not ok.
5*5*7=175, 5+35=1+39, not ok.
5*7*7=245, 5+49=1+53, 7+35=1+41, ok.
7*7*7=343, 7+49=1+55, not ok.

3*3*3*3=81, 3+27=1+29, 9+9=1+17, ok.
3*3*3*5=135, 3+45=1+47, 5+27=1+31, 9+15=1+23, ok.
3*3*5*5=225, 3+75=1+77, not ok.
3*5*5*5=375, 3+125=1+127, 5+75=1+79, 15+25=1+39, not ok.
5*5*5*5=625, 5+125=1+129, not ok.

So this gives several possible answers (4,1), (8,1), (32,1), (512,1), (6,1), (15,1), (33,1), (35,1), (49,1), (77,1), (27,1), (45,1), (125,1), (245,1), (81,1) and (135,1) amongst them.

Other forms for the product are:

C) 2^n*(2m+1), n,m>1 and

C) (2n+1)2^m can be factored into pairs (2^n,2m+1) and ((2n+1)2^m,1) both of which have sums that are not 1+prime.

Topi

William McKibben (Oxford, GA, USA) writes:

Let P and S denote, respectively, the product and sum of the numbers given to Trudy and Chris. If P is a prime then Trudy would know that the solution is {1,P}. Since she doesn’t know, it follows that P is not a prime. Since Chris knew that Trudy would not know the numbers, then his number, S, cannot be 1 greater than a prime. Now, from Chris’s statement, Trudy knows that from all the factorizations of P into two factors she must pick among those for which the corresponding sum of factors is not equal to 1 greater than a prime. Since she says she knows the numbers, it is necessary and sufficient that there is one and only one factorization of P with the property that the sum of the factors is not equal to a number that is 1 greater than a prime.

For example, suppose that Trudy were given the number 12. Then the possible factorizations of 12 into two factors yield sums 1+12 = 13 (not 1 greater than a prime); 2 + 6 = 8 (equal to 1+7); and 3 + 4 = 7 (not 1 greater than a prime). When Chris says that he knew that she didn’t know the numbers, Trudy could only determine that the solution is either {1,12} or {3,4}, but not which one. On the other hand, suppose Trudy were given the number 15. The possible factorizations lead to sums 1 + 15 = 16 (not 1 greater than a prime) and 3 + 5 = 8 (equal to 1 + 7). Since only one factorization gives a sum not 1 greater than a prime, Chris’s statement leads her to conclude that the solution is {1,15}.

In the following we denote by T the set of possible products that Trudy could be given in order for her to uniquely identify the solution pair; that is, T is defined by

T = {t: t is a positive integer such that if t = m n, then m + n -1 is not prime for

exactly one pair {m,n}}

Chris, then knows that his number S can be written as the sum of two integers whose product is an element of the set T. He could recognize the terms as the secret numbers if and only if there is one and only one partition of S into two terms whose product is in T. Since there is a partition of S, namely S = 1 + (S-1) into two terms for which the product 1 (S-1) is in T [If it were not, then 1 + (S-1) = S would be 1 greater than a prime, and Chris would not have been able to say truthfully “I knew that you did not know the numbers.”] We now show that there are no other partitions of S into a sum of two terms whose product is in T. These products are of the form i (S – i) for 2 < i < Q, where Q = S/2 if S is even and (S-1)/2 if S is odd. Two of the ways in which i (S – i) can be factored are i (S – i) and 1 [i (S – i)] leading to sums i + (S – i) and 1+ i (S – i), respectively. The former sum is equal to S, which is by assumption not 1 greater than a prime. The latter sum is clearly not 1 greater than a prime, since i (S – i) is obviously not prime for i >2. It follows that the one and only choice for the two numbers is the pair {1, S-1}.

The above demonstration leads to the following:

Theorem. The complete solution set of the problem is {{1,t}: t is an element of T}.

To shed light on the solution set it is sufficient to explore further the nature of the set T.

The following results are obtained:

(1) T contains no prime numbers, obviously.

(2) If an integer t is a product of primes, say t = p q. Then t is an element of T if and

only if p + q – 1 is prime.

If p + q – 1 is prime, then the only other factorization of t, namely t = 1(pq), produces the sum 1+ pq, which is clearly not 1 greater than a prime. Thus t has exactly one factorization into two factors with sum not 1 greater than a prime. Thus t is in T.

If t is in T, then exactly one of its factorizations into two integers is not 1 greater than a prime. Now t has at least one such factorization, namely t = 1(pq), as seen above. It follows that the only other factorization of of t, namely t = p q must have sum that is not 1 greater than a prime; i. e., p + q must be 1 greater than a prime, which is to say that p + q – 1 is a prime.

Some example in this category are as follows: 4 = (2)(2), with sum 2 + 2 = 1 + 3;

9 = (3)(3) with sum 3 + 3 = 1 + 5; 15 = (3)(5) with sum 3 + 5 = 1 + 7; 35 = (5)(7)

with sum 5 + 7 = 1 + 11.

(3) The only even integers in T are certain powers of 2; namely, {2^a : whenever r + s = a with 1 < r < s, it is true that 2^r+ 2^s – 1 is prime}

Suppose that t is in T and t is even. Then t can be written as t = 2^ab, where

a > 1, and b is odd.

If b =1, then t = 2^a, which is in T if and only if there is exactly one

factorization of t that yields a sum that is not 1 greater than a prime. There is at least one since the factorization t = 1 (2^a) that yields such a sum (The case a = 1 can be excluded, for it yields t = 2, a prime.) There cannot be others if t is to be an element of T, as assumed. The other factorizations are of the form (2^r)(2^s ), where r + s =a, and 1 < r < s. Hence t is in T if and only if for all such r and s it is true that 2^r+ 2^s is equal to 1 greater than a prime; i. e., for which 2^r+ 2^s – 1 is prime.

If b > 1, then, as usual there is one factorization yielding a sum that is not 1 greater than a prime; namely, t = 1 (2^ab). All other factorizations must yield sums that are each 1 greater than a prime. This implies that, in particular, there is a prime p such that 2^a + b = p + 1. Since b is assumed to be odd, the left side of the last equation is an odd integer. Unless p = 2, the right side of the equation is even, a contradiction. To avoid the contradiction, p must equal 2, which yields 2^a + b = 3, a statement that can only hold if a = 1 and b = 1. But since b > 1, we have a contradiction. It follows that with t = 2^ab, it must be the case that b = 1.

Some powers of 2 in this category: 8 [= 2³ which factors as 2 ( 2² ) with sum 2 + 2² = 2 + 4 = 1 + 5]; 32 [= 2⁵ which factors as 2 ( 2⁴ ) with sum 2 + 2⁴ = 2 + 16 = 1 + 17; and as 2² ( 2³ ) with sum 2² + 2³ = 4 + 8 = 1 + 11].

(4) The following are all the members of T that are < 100: 4, 8, 9, 15, 27, 32, 33, 35, 45, 49,

51, 65, 77, 81, 87, 95

These were obtained by testing individually the eligible integers (not prime, and

not even unless a power of 2, according to (1) and (3) above). It can be seen

that there are members of T that are not powers of 2 nor simple multiples of

two primes, but are multiples of three primes; for example,

27 = (3)(3)(3) in T because 3 + (3)(3) = 3 + 9 = 1 + 11

45 = (3)(3)(5) in T because 3 + (3)(5) = 3 + 15 = 1 + 17 and

5 + (3)(3) = 5 + 9 = 1 + 13

It is difficult, probably impossible, to characterize T completely. While exploring T further, one might wonder whether T contains any elements of the form p q r, where p,q, and r are distinct primes. The answer is in the affirmative:

1001 = (7)(11)(13) in T because 7 + (11)(13) = 7 + 143 = 1 + 149;

11 + (7)(13) = 11 + 91 = 1 + 101; and

13 + (7)(11) = 13 + 77 = 1 + 89

And Troy Williamson (Abilene, TX, USA) writes:

comments: In a word, no. This is a tricky one, and there is a lot of information passed back and forth in their conversation. Yet there is not quite enough information for us to discern the numbers.

First, we need to think about the range. It seems that the negative numbers must be excluded. If Trudy had a product of 5, for example, she would not know if it was (1)(5) or (-1)(-5), and the ensuing conversation would not help her make that distinction. So the range must include positive values only.

In a similar way, it seems that we can exclude 0 and 1 from the range. If 0 is included, then it simply increases the possibilities that Chris must work with, since that is the additive identity; if 1 (the multiplicative identity) is included, then Trudy has additional combinations to sift through. For this to work, we must be dealing with a range for which the lower limit is 2. We do not, however, have any upper limits to impose.

Trudy's first statement indicates that the two numbers are not both primes. Suppose she had the product 15; she would know that the numbers are 3 and 5, since that is the only way to factor that product within the range. So their must be multiple ways of factoring the product; to say this another way, the prime factorization for the product supplied to Trudy must contain at least three factors.

Chris' first statement is interesting, because he says it in the past tense ("I knew ..." instead of "I know ..."). This indicates that he knew she would be unable to determine the numbers even before she made her first statement. How could this be?

Suppose that Chris is looking at the number 8 as the sum. He would realize that one possible pair of addends would be 3 and 5. But if the numbers are 3 and 5, then Trudy has a product of 15 and knows what the numbers are. Chris is saying this is not possible. In other words, Chris cannot be looking at a number which can be written as the sum of two primes. If he was, then there would be the possibility of Trudy knowing the numbers.

Interestingly (I won't bore you with the details), this means that Chris' sum must be odd; if his sum was even, then there would be a pair of prime addends. So the information that Chris is offering is, "The sum of the factors is odd."

Using this information, Trudy is able to determine the two numbers. This means that, of the multiple factorizations possible for the product, only one of them contains factors whose sum is odd (i.e., one of the numbers is even and the other is odd). We cannot know her numbers at this point, although she can. Suppose, for example, that she has 12 for the product. This could be (2)(6) or (3)(4). Based on the information offered by Chris, she knows that it must be (3)(4), since this is the only factor pair that has an odd sum.

By stating that she now knows the numbers, she actually transmits more information back to Chris. This is the tricky one. If the prime factorization contains more than two factors, and if there is only one way for these to be combined so that one digit is even and the other odd, then the prime factorization must consist of one odd prime number and some twos (there must be at least three factors, so there have to be at least two twos in the list). Again, I won't bore you with the details.

Here is the point: For this conversation to be enough to allow Chris to know his numbers, then it has to be true that one of the numbers is an odd prime, and it has to be true that the other number is a power of 2 (4, 8, 16, 32, 64, ...). Can this help Chris decide what the numbers are? In certain cases, yes.

Let us suppose, as we did earlier, that the numbers are 3 and 4. Trudy has a product of 12, which can be (2)(6) or (3)(4). When she learns that the sum of the factors must be odd, she knows that the numbers are 3 and 4. Chris has been looking at the sum of 7. This could be 2+5 or 3+4. Now that he knows that one number must be an odd prime and the other a power of 2, he also knows that the numbers are 3 and 4.

Take another example. Suppose that Trudy has a product of 20. This could be (2)(10) or (4)(5). If the sum must be odd, then 4 and 5 must be the numbers. Chris has been looking at a sum of 9, which could be 2+7, 3+6, or 4+5. Knowing that he needs an odd prime and a power of 2, he also deduces that the numbers must be 4 and 5. So there are cases where the following conversation could have led both of them to deduce the numbers.

However, there is no way for us to know. I just provided two examples (when the numbers are 3 and 4 or when the numbers are 4 and 5) where the above conversation is "true," but we have no additional information to help us know which set of numbers they were working with. If Trudy had a product of 12 and Chris had a sum of 7, then the numbers are 3 and 4. If Trudy had a product of 20 and Chris had a sum of 9, then then numbers are 4 and 5. I have no clue which of these (or other possibilities) are actually involved. (Using the range [2...100], I found 29 pairs of numbers for which their conversation would reveal the values to them.)

Notice, also, that not just any values can work--even with the information that we have. Suppose, for example, Trudy has a product of 24, which could be (2)(12), (3)(8), or (4)(6). Since she knows that she needs factors with an odd sum, she knows that the values must be 3 and 8. Chris, however, has been looking at a sum of 11: 2+9, 3+8, 4+7, or 5+6. There are two pairs that meet the criteria he is using: 3+8 and 4+7. Which of these is it? He cannot tell. If it is 3 and 8, then Trudy had a product of 24 and the (3,8) pair is the only set of factors with an odd sum. If it is 4 and 7, then Trudy had a product of 28 and the (4,7) pair is the only set of factors with an odd sum. So Chris will be unable to distinguish between them.

So here is the way it works: If you have an odd prime and a power of 2 (greater than 2 itself) which add to a sum that cannot be expressed by two other numbers meeting the criteria, then those two numbers will "solve" the conversation between Trudy and Chris. But there are a number of such possibilities, so we cannot know their numbers.

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