**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^{a }b, 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^{a }b). 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^{a }b, it must be the case that b = 1.

Some
powers of 2 in this category: **8** [= 2^{3
} which factors as 2 ( 2^{2} )
with sum 2 + 2^{2 } = 2 + 4 = 1 + 5]; **32** [= 2^{5} which factors as 2 ( 2^{4}
) with sum 2 + 2^{4 } = 2 + 16 = 1 +
17; and as 2^{2} ( 2^{3} ) with sum 2^{2} + 2^{3 } = 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.

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