All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic
More logicians, hats and numbers (Posted on 2006-11-05) Difficulty: 4 of 5
Sam and Pete, two perfectly intelligent logicians, are sitting facing each other, each with a hat on. The number on Pete's hat, they are told, is the sum of two integers larger than 1; the number on Sam's hat is the product of these two integers. The following conversation ensues:

Sam: I don't know the number on my hat.
Pete: I don't know the number on my hat.
Sam: I don't know the number on my hat.
Pete: I don't know the number on my hat.
Sam: I don't know the number on my hat.
Pete: I don't know the number on my hat.
Sam: OK, now I know the number on my hat.
Pete: And I know the number on mine.

What are the numbers on Pete's and Sam's hats?

  Submitted by JLo    
Rating: 4.1250 (8 votes)
Solution: (Hide)
The numbers on Sam's hat is 24, the number on Pete's hat is 10, i.e. the number pair from which sum and product are built is (4,6). Credits to the solvers, it took me a fair bit longer to devise this puzzle than it took you to crack it!

To determine the numbers, one can use a bottom-up approach to figure out for which number pairs the "game" would end in round 1, 2, 3... Let's start with the result first, explanation later. The number pairs are the integers making up the sum and the product:

Round 1 (S): (2,2), (2,3)

Round 2 (SP): (3,3), (2,4), (3,5), (5,5), (2,7), (3,7), (5,7), (7,7), (3,9), (2,11),... In general, all number pairs (p,q) and (p,p^2) with primes p and q are won in round 2. That is, excluding (2,2) and (2,3) of course which are won in round 1 already.

Round 3 (SPS): (3,4)

Round 4 (SPSP): (2,6)

Round 5 (SPSPS): (4,4)

Round 6 (SPSPSP): (2,8)

Round 7 (SPSPSPS): (4,6)

For each round, the string SPS.. indicates the players who guessed in each round, starting from the left, i.e. the right-most letter always indicates the player doing the winning guess. Note that the pairs are considered "unordered", so e.g. (2,3)=(3,2). Since there is only one number pair allowing Sam to win in round 7, namely (4,6), this must be the good one.

Explanation:

Let's call the two numbers a and b. First observe that Sam knows s=a+b and Pete knows p=a*b. Without any further knowlegde, Sam only knows that (a,b) must be in (2,s-2), (3,s-2),..(s/2,s/2). Likewise, Pete can determine all possible number pairs by decomposing p into two factors and collecting all pairs of factors.

Round 1: The only way Sam can win in round 1 is if s=4 or s=5, because only these numbers allow a unique decomposition in two summands larger than 1. The decompositions are (2,2) and (2,3)

Round 2: In order for Pete to guess both numbers without any further knowledge, p must allow for a unique decomposition into two factors larger than 1. This is possible for all pairs (p,q) and (p,p^2) with primes p and q. However since (2,2) and (2,3) would be guessed in round 1 already, we have to exclude them. Can we benefit from the fact that Sam did NOT wind in round 1? Not really, because we can only tell that the number pairs are not (2,2) and (2,3), but we already know that anyway, because otherwise p=4 or p=6 respectively. But if p=4 or p=6 then (2,2) and (2,3) are the only possible number pairs, so there is nothing else that can be ruled out.

Round 3: We already know s>=6. For s=6 the decompositions (2,4) and (3,3) are possible, but these win in round 2 already. For s=7 we have the possibilities (2,5) and (3,4). Since (2,5) would be won in round 2, Sam can deduce the number pair (3,4). Larger s won't work: s=8 allows decompositions (2,6), (3,5) and (4,4) of which only (3,5) can be ruled out (wins in round 2), so Sam cannot tell if the number pair is (2,6) or (4,4). s=9 gives (2,7), (3,6), (4,5) of which only the first can be ruled out. For s=10 we have (2,8), (3,7), (4,6), (5,5), leaving the possibilities (2,8) and (4,6). For s=11 we even have (2,9), (3,8), (4,7), (5,6) of which NONE can be ruled out. For larger s it gets worse and worse, so no more winning combinations.

Now it is getting easier...

Round 4: In comparison to Pete's previous turn, the only extra bit of information Pete now has, is that the numbers are NOT (3,4); otherwise Sam would have won in the previous round. This information is only useful (i.e. new information) to Pete if p=3*4=12. 12 allows decompositions into products with pairs (2,6) or (3,4). Indeed, if p=12 Pete can deduce that the number pair is (2,6), otherwise Sam sould have won with (3,4) in the previous round.

Round 5: Now Sam know the numbers are NOT (2,6). This is new news only if s=2+6=8 which allows summand decomposition with pairs (2,6), (3,5) and (4,4). Only (4,4) does not win in previous rounds, therefore Sam can deduce that the numbers are (4,4).

Round 6: p=4*4=16 allows for (product) number pairs (2,8) and (4,4). (4,4) wins in round 5 so Pete can deduce the pair (2,8)

Round 7: s=2+8=10 allows for (sum) number pairs (2,8), (3,7), (4,6) and (5,5). All except (4,6) win in earlier rounds, hence (4,6) can be deduced in round 7.

Round 8: The fact that Pete also knows the answer in round 8 is irrelevant; since WE can deduce the numbers as shown above (not knowing either sum or product), even more so can Pete. I just wanted to add one more line to the puzzle to make it look a little more difficult.

Note: Following the described approach a little further, you'll see that if no-one determines the numbers in rounds 1-7, they can never be determined. So the choice of numbers (4,6) allows for a puzzle of maximum length.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
re: Solutionatheron2006-11-08 03:01:51
SolutionSolutionnikki2006-11-07 18:02:12
Some ThoughtsSome thoughtsatheron2006-11-07 12:47:47
Hints/TipsSpoilerRobby Goetschalckx2006-11-05 19:22:30
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information