Author |
Topic: More Numbered Hats (Read 1052 times) |
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
More Numbered Hats
« on: Jun 23rd, 2008, 9:07am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: More Numbered Hats
« Reply #1 on: Jun 23rd, 2008, 10:10am » |
Quote Modify
|
I'm not convinced that B could definitely know the values, but here is my working so far... 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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: More Numbered Hats
« Reply #2 on: Jun 23rd, 2008, 12:05pm » |
Quote Modify
|
Continuing Sir Col's analysis: 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. Edit: a = 4, b = 19 appears to also be a solution. --SMQ
|
« Last Edit: Jun 23rd, 2008, 12:14pm by SMQ » |
IP Logged |
--SMQ
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: More Numbered Hats
« Reply #3 on: Jun 23rd, 2008, 12:47pm » |
Quote Modify
|
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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: More Numbered Hats
« Reply #4 on: Jun 23rd, 2008, 2:23pm » |
Quote Modify
|
on Jun 23rd, 2008, 12:05pm, SMQ wrote: I haven't finished checking uniqueness, but a = 4, b = 13 meets the conditions: [...] |
| This is correct. on Jun 23rd, 2008, 12:05pm, SMQ wrote:Edit: a = 4, b = 19 appears to also be a solution. |
| This is not: ===== 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. ===== EDIT: 8) smiley removed.
|
« Last Edit: Jun 23rd, 2008, 2:29pm by FiBsTeR » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: More Numbered Hats
« Reply #5 on: Jun 23rd, 2008, 2:44pm » |
Quote Modify
|
on Jun 23rd, 2008, 2:23pm, FiBsTeR wrote: Ahh, yes, I was defining the posibilities too narrowly: 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. --SMQ
|
|
IP Logged |
--SMQ
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: More Numbered Hats
« Reply #6 on: Jun 23rd, 2008, 2:55pm » |
Quote Modify
|
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.
|
« Last Edit: Jun 23rd, 2008, 11:32pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: More Numbered Hats
« Reply #7 on: Jun 24th, 2008, 5:23am » |
Quote Modify
|
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
|
« Last Edit: Jun 24th, 2008, 12:58pm by Hippo » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: More Numbered Hats
« Reply #8 on: Jun 24th, 2008, 11:10am » |
Quote Modify
|
on Jun 23rd, 2008, 9:07am, 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
|
« Last Edit: Jun 25th, 2008, 6:15am by SMQ » |
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: More Numbered Hats
« Reply #9 on: Jun 24th, 2008, 7:17pm » |
Quote Modify
|
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 &] |
|
|
« Last Edit: Jun 24th, 2008, 7:47pm by Eigenray » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: More Numbered Hats
« Reply #10 on: Jun 25th, 2008, 6:11am » |
Quote Modify
|
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 site... my results now match yours, Eigenray. --SMQ
|
|
IP Logged |
--SMQ
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: More Numbered Hats
« Reply #11 on: Jun 25th, 2008, 7:39am » |
Quote Modify
|
The posted problem was originally a USAMTS problem (a high school math talent search in the US) a few years ago. This 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).
|
« Last Edit: Jun 25th, 2008, 7:41am by FiBsTeR » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: More Numbered Hats
« Reply #12 on: Jun 25th, 2008, 9:39am » |
Quote Modify
|
on Jun 25th, 2008, 7:39am, 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
|
|
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: More Numbered Hats
« Reply #13 on: Jun 25th, 2008, 2:37pm » |
Quote Modify
|
on Jun 25th, 2008, 7:39am, 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.
|
« Last Edit: Jun 25th, 2008, 2:38pm by Eigenray » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: More Numbered Hats
« Reply #14 on: Jun 25th, 2008, 6:05pm » |
Quote Modify
|
on Jun 25th, 2008, 7:39am, 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 100). on Jun 25th, 2008, 9:39am, 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? |
| 149 = 67 + 82
|
« Last Edit: Jun 25th, 2008, 8:41pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: More Numbered Hats
« Reply #15 on: Jun 25th, 2008, 8:46pm » |
Quote Modify
|
on Jun 25th, 2008, 2:37pm, 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 N
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: More Numbered Hats
« Reply #16 on: Jun 25th, 2008, 11:01pm » |
Quote Modify
|
on Jun 25th, 2008, 6:05pm, ThudanBlunder wrote: Are you sure? Or is that the answer if A,B already know that neither a,b is a power of 2?
|
« Last Edit: Jun 25th, 2008, 11:31pm by Eigenray » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: More Numbered Hats
« Reply #17 on: Jun 27th, 2008, 2:12pm » |
Quote Modify
|
on Jun 25th, 2008, 11:01pm, Eigenray wrote: Are you sure? 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.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|