wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> medium >> More Numbered Hats
(Message started by: FiBsTeR on Jun 23rd, 2008, 9:07am)

Title: More Numbered Hats
Post by FiBsTeR on Jun 23rd, 2008, 9:07am
Visible only to A is a hat on B's head, on which is written the product ab of two positive integers b>a>1. On A's head is a hat with the sum a+b on it, visible only to B. The following conversation occurs:

A: I do not know a and b.

B: I already knew that you did not know a and b.

A: Now I know a and b.

B: I now also know a and b.

Given that a,b<20, unbeknownst to A and B, find (the unique values of) a and b.

Title: Re: More Numbered Hats
Post by Sir Col on Jun 23rd, 2008, 10:10am
I'm not convinced that B could definitely know the values, but here is my working so far...

[hide]If a and b are both prime then the product will be unique and as A said that he didn't know the values of a and b then the number must have at least three prime factors.

Now if B already knew that A couldn't deduce then he must be looking at a total for which all partitions lead to a product that is not unique.

For example, if B could see 9 then the products would be: 2*7 = 14, 3*6 = 18, and 4*5 = 10.

But this means that A could be looking at at 14, which means he could deduce the pair of numbers.

Hence we need to consider the partitions for every possible total and if a "weak link" exists then we reject that total. Below I have listed the weak link for each sum, a+b.
5: 2*3 = 6
6: 2*4 = 8
7: 2*5 = 10
8: 3*5 = 15
9: 2*7 = 14
10: 3*7 = 21
11: none!
12: 5*7 = 35
13: 2*11 = 22
14: 3*11 = 33
et cetera

I am guessing that 11 is the only sum for which each partition leads to an ambiguous product. Hence when A realises that B already knew he knows that the sum must be 11 and as he can see the product he can determine the pair of numbers; the possible products are 18, 24, 28, or 30.

However, I don't see how B could now deduce the values?

Equally I've not managed to prove that 11 is the only sum for which each partition of pairs, 1<a<b, leads to an ambiguous product.[/hide]

Title: Re: More Numbered Hats
Post by SMQ on Jun 23rd, 2008, 12:05pm
Continuing Sir Col's analysis:

[hide]Along with 11, the sums 17, 23, 27, 29 and 37 share the property of having no immediately-disqualifying a and b.

In order for B's statement to make the value unambiguous for A, the product of a and b must have only two possible solutions (a is a prime and b the square of a prime or vice-versa), and one of these must have a sum which is not one of the above (or a larger such sum).

In order for A's statement to make the value unambiguous for B, it must be the only such product which is a solution of the sum.

I haven't finished checking uniqueness, but a = 4, b = 13 meets the conditions:

- The sum, 17, can be formed as 2+15, 3+14, 4+13, 5+12, 6+11, 7+10 or 8+9, none of which are both prime
- The product 52 can only be formed as 2*26 or 4*13
- 2+26 = 28 which could be the sum of two primes, 11+17, so B's statement disambiguates the options for A
- None of the other possible products with sum 17 would be unique:
   - 30 = 2*15, 3*10 or 5*6
   - 42 = 2*21, 3*14 or 6*7
   - 60 = 2*30, 3*20, 4*15, 5*12 or 6*10
   - 66 = 2*33, 3*22 or 6*11
   - 70 = 2*35, 5*14 or 7*10
   - 72 = 2*36, 3*24, 4*18, 6*12 or 8*9
 so A's statement provides a unique answer for B.
[/hide]

Edit: [hide]a = 4, b = 19 appears to also be a solution.[/hide]

--SMQ

Title: Re: More Numbered Hats
Post by Sir Col on Jun 23rd, 2008, 12:47pm
I've made some progress with the unambiguous product idea...


A number will only have an unambiguous product if a and b are both prime.

Although it hasn't been proven, the Goldbach conjecture states that all even numbers are the sum of two primes. Hence all even numbers for which n <> 2p, will be the sum of two distinct primes and will have an unambiguous product.

If n is odd then exactly one of a or b must be even and the only even prime is 2.
Hence a = 2 and b = n-2, but then ab will composite.

In other words, all odd numbers, n, for which n-2 is composite will have ambiguous products.

That is, the set, 11, 17, 23, 27, 29, 35, 37, ...

That only leaves even numbers of the form n = 2p. Because 1 < a < b, then a and b cannot both be equal to p. Hence there may exist even numbers of the form 2p which have entirely ambiguous products.

Title: Re: More Numbered Hats
Post by FiBsTeR on Jun 23rd, 2008, 2:23pm

on 06/23/08 at 12:05:00, SMQ wrote:
[hide]
I haven't finished checking uniqueness, but a = 4, b = 13 meets the conditions: [/hide][...]

This is correct.


on 06/23/08 at 12:05:00, SMQ wrote:
Edit: [hide]a = 4, b = 19 appears to also be a solution.[/hide]


This is not:
=====
[hide]
Let a=4, b=19. Then A knows ab=4*19=76 and B knows a+b=4+19=23.

A: I do not know a and b.

This is true: 76=4*19=2*38, so A cannot deduce a,b.

B: I already knew that you did not know a and b.

This is true: we can partition 23 as:

2 21
3 20
4 19
5 18
6 17
7 16
8 15
9 14
10 13
11 12

In all cases, both numbers are not both prime, so B knew that A could not deduce a,b.

A: Now I know a and b.

This is true: of the two cases that A had -- (4,19), (2,38) -- we have already shown that 4+19=23 could not be expressed as the sum of two primes, whereas 2+38=40=13+17, so A knows (a,b)=(4,19).

B: I now also know a and b.

This is false: in order for this to be true, there must be only one way to express 23 as the sum of two numbers whose product satisfies the third line. Though (4,19)-->4*19=76 works (as shown above), (7,16) also works:

7*16=112=8*14=4*28=2*56, which in all 3 of the other cases yields an even sum; Goldbach's conjecture has already been tested on these, so we can find two primes that sum to these.

Thus B cannot deduce a,b, and (a,b)=(4,19) does not lead to this conversation.
[/hide]
=====

EDIT: 8) smiley removed.

Title: Re: More Numbered Hats
Post by SMQ on Jun 23rd, 2008, 2:44pm

on 06/23/08 at 14:23:03, FiBsTeR wrote:
This is not:

Ahh, yes, I was defining the posibilities too narrowly: [hide]the product needn't have only two possible solutions, but rather only a single one with a qualifying sum and any number with non-qualifying sums.[/hide]

--SMQ

Title: Re: More Numbered Hats
Post by Sir Col on Jun 23rd, 2008, 2:55pm
I did a quick test of all evens of the form 2p under 20 billion and none of them have entire ambiguous products. In other words, every one of them can be written as the sum of two distinct primes.

I wonder if it is possible to prove that every even number of the form 2p can also be written as the sum of two distinct primes? Does anyone know of such a conjecture? I've never heard it stated that way and if true then it seems to strengthen the Goldbach conjecture from "All even numbers greater than 2 can be written as the sum of two primes" to "All even numbers greater than 6 can be written as the sum of two distinct primes".

It is certainly true that the number of distinct prime pairs that add to make even n increases "significantly" as n increases.

Title: Re: More Numbered Hats
Post by Hippo on Jun 24th, 2008, 5:23am
Before reading answers: 2nd B's answer gives nothing.
A1: \Prod is not prime
B1: \Sum-1 is not prime
A2: whole \Prod/a+a-1 isn't prime exactly once, ... for a=1 we know it already, so one of the numbers is 1 and we get \Sum=1+\Prod. So B has the same information as A and B2 is irelevant.

At least 4,8 are two distnict solutions.

Oops >1 :(

Title: Re: More Numbered Hats
Post by SMQ on Jun 24th, 2008, 11:10am

on 06/23/08 at 09:07:04, FiBsTeR wrote:
Given that a,b<20, unbeknownst to A and B

I would conjecture that this restriction is unnecessary.  Certainly it's unnecessary for a+b < 131072 Edit: and I would be very wrong -- see below :-[
(remainder of nonsense post removed)

--SMQ

Title: Re: More Numbered Hats
Post by Eigenray on Jun 24th, 2008, 7:17pm
Maybe there's an error in my thinking, but wouldn't the following also work for {a,b}:
{4, 13}, {4, 61}, {16, 73}, {16, 111}, {64, 73}, ...?


Code:
M = 200;
A[n_] := !PrimeQ[n-2]; (* n>=5 odd *)
F = Array[0 &, M^2/4];
For[a=2, a < M/2, a++,
 For[b=a+1, a b < M^2/4, b+=2,
   If[A[a+b], F[[a b]]++];
 ]
];
G = Array[{} &, M];
For[a=2, a<M/2, a++,
 For[b=a+1, a+b < M, b+=2,
   If[F[[a b]] == 1 && A[a+b], AppendTo[G[[a+b]], {a, b}]];
 ];
];
Select[G, Length@# == 1 &]

Title: Re: More Numbered Hats
Post by SMQ on Jun 25th, 2008, 6:11am
Gaah!  :-[

Brought down by a single-character typo in code I thought I'd thoroughly tested -- a math library I wrote for Sir Col's Project Euler (http://projecteuler.net/) site...  my results now match yours, Eigenray.

--SMQ

Title: Re: More Numbered Hats
Post by FiBsTeR on Jun 25th, 2008, 7:39am
The posted problem was originally a USAMTS problem (a high school math talent search in the US) a few years ago. This (http://www.usamts.org/Solutions/Solution4_1_17.pdf) is a link to the two commended submitted solutions, if it might be of use to the current discussion. The second solution proves that (4,13) is a unique solution, though I'm not sure if this is unique in the sense that a,b<20 or not. I was inclined to believe that it would be unique without the <20 restriction since A,B in the conversation were not aware of the restriction.

EDIT: I believe the restriction a,b<20 was put in the problem to help students who could not code (like me) find the correct (a,b) more easily, since the grading of the solution came mostly from proving (a,b) worked, and not so much in finding (a,b).

Title: Re: More Numbered Hats
Post by SMQ on Jun 25th, 2008, 9:39am

on 06/25/08 at 07:39:19, FiBsTeR wrote:
I was inclined to believe that it would be unique without the <20 restriction since A,B in the conversation were not aware of the restriction.

The second solution given in the paper (which is the only one to prove uniqueness) indeed relies on a,b < 20.  Both Eigenray and I find plenty further solutions if the maximum value is unbounded.

Bonus question: what is the smallest sum a+b such that a, b is a solution and neither a nor b is a power of 2?

--SMQ

Title: Re: More Numbered Hats
Post by Eigenray on Jun 25th, 2008, 2:37pm

on 06/25/08 at 07:39:19, FiBsTeR wrote:
I was inclined to believe that it would be unique without the <20 restriction since A,B in the conversation were not aware of the restriction.

The difference is that A,B already know ab, a+b, and therefore have their own bounds on a,b.  So they can figure it out, even if we can't.

The problem changes some more if they also know that a,b < M.  For example, even though (4,61) is a solution that has 4<61<100, it would not be a solution if A,B knew that a<b<100.

Title: Re: More Numbered Hats
Post by ThudanBlunder on Jun 25th, 2008, 6:05pm

on 06/25/08 at 07:39:19, FiBsTeR wrote:
The posted problem was originally a USAMTS problem (a high school math talent search in the US) a few years ago.

I think it originated in 1969 as Problem Number 223 (by Hans Freudenthal) in the Dutch publication Nieuw Archief voor Wiskunde (New Archive for Mathematics) (with a + b  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leqslant.gif 100).  


on 06/25/08 at 09:39:12, SMQ wrote:
Bonus question: what is the smallest sum a+b such that a, b is a solution and neither a nor b is a power of 2?

[hide]149 = 67 + 82[/hide]


Title: Re: More Numbered Hats
Post by ThudanBlunder on Jun 25th, 2008, 8:46pm

on 06/25/08 at 14:37:57, Eigenray wrote:
The problem changes some more if they also know that a,b < M.  For example, even though (4,61) is a solution that has 4<61<100, it would not be a solution if A,B knew that a<b<100.

If a and b each have an upper bound of n, prove that a + b < [n/2] + 2, where [N] is the smallest prime http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/geqslant.gif N

Title: Re: More Numbered Hats
Post by Eigenray on Jun 25th, 2008, 11:01pm

on 06/25/08 at 18:05:30, ThudanBlunder wrote:
[hide]149 = 67 + 82[/hide]

Are you [link=http://www.research.att.com/~njas/sequences/A086533]sure[/link]?  Or is that the answer if A,B already know that neither a,b is a power of 2?

Title: Re: More Numbered Hats
Post by ThudanBlunder on Jun 27th, 2008, 2:12pm

on 06/25/08 at 23:01:59, Eigenray wrote:
Are you [link=http://www.research.att.com/~njas/sequences/A086533]sure[/link]?  Or is that the answer if A,B already know that neither a,b is a power of 2?

I'll try to come back to this problem when I have more time.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board