Science: Puzzles
==============================
by John Derbyshire
July 31st, 2003
My National Review Online “Diary” column for July 2003 included the following brainteaser.
Product and Sum
——————
Of two unknown integers, each between 2 and 99 inclusive, a person P is told the product and a person S is told the sum. When asked whether they know the two numbers, the following dialogue ensues:
P: “I don’t know them.”
S: “I knew that already.”
P: “Then I now know the two numbers.”
S: Then I now know them, too.”
What are the two numbers? Prove that your solution is unique.
———————————————
This is an exceptionally elegant puzzle. You start by noticing that if the numbers were two primes (7 and 11, for example), then P would know them at once on being given the product (77). Since he begins by telling us he doesn’t know them, they are not both primes.
Furthermore, none of the prime factors of either number can be bigger than 47. Why not? Well, consider a case where one of them is; let’s say, it’s 59. The smallest number this is a factor of is 59, the next smallest is 118, and so on. Since we have been told that our unknown integers are both between 2 and 99 inclusive, 59 must be one of the numbers. The other one must be the product, divided by 59. P could work all this out from just the product, once he’d spotted that factor 59. Since he didn’t, there can’t be any prime factor like this--i.e. bigger than 50.
All that is deduced from just the first one of those statements--the statement, by P, that after being given the product, he does not know the numbers!
==============================
January 31st, 2002
My National Review Online “Diary” column for January 2003 included the following brainteaser.
A woman is walking down the street and meets her neighbor. The woman says, “I can’t remember the ages of your 3 children.” The neighbor replies, “The product of their ages is 36.” The woman thinks a minute and says, “I still don’t know the ages of your 3 children.” The neighbor replies, “The sum of their ages is your address.” The woman thinks a minute and says, “I still don’t know their ages.” The neighbor replies, “The oldest has red hair.”
What are the ages of the three children?
——————————————–
Solution. We have to find three whole numbers that, when multiplied together, make 36, There are just eight possibilities: 1-1-36, 1-2-18, 1-3-12, 1-4-9, 1-6-6, 2-2-9, 2-3-6, 3-3-4. If you add up the numbers in each triplet, you get: 38, 21, 16, 14, 13, 13, 11, 10.
Now, when the second woman was told that the ages added up to her address, she still didn’t know the answers. Her address must therefore be 13. If it had been one of the other numbers — 38, 21, 16, 14, 11, or 10 — she would have been able to pin down the triplet. Only with 13 can she not do this, because two triplets add up to 13: 1-6-6 and 2-2-9.
However, once the neighbor says: “The oldest...,” she knows it must be 2-2-9, since if the kids’ ages are 1-6-6, there is no oldest!
Answer: the children are aged 2, 2, and 9.
==============================
October 31st, 2003
My National Review Online “Diary” column for October 2003 included the following brainteaser.
The Square Root Fallacy
——————
Readers of Prime Obsession will know that, contrary to what your schoolteachers told you, the number “minus one” does so have a square root, the friendly little number i. In fact, not only is the square of i equal to -1, so, by the rule of signs, is the square of -i.
If you are still with me, see if you can find the flaw in the following argument. Out of consideration for Aaron the Webbie, I am going to use “Sqr(x)” to indicate the square root of x and an asterisk to indicate multiplication.
Start from this obvious truth: Sqr(x — y) = i * Sqr(y — x).
Since this is plainly the case for any numbers x and y, put x = a and y = b.
Then: Sqr(a — b) = i * Sqr(b — a).
On the other hand, since that obvious truth I started with is the case for any numbers x and y, I could equally well put x = b and y = a, to get another, equally true statement:
Sqr(b — a) = i * Sqr(a — b).
Now, if P = Q and R = S, then obviously P * R = Q * S.
So: Sqr(a — b) * Sqr(b — a) = i 2 * Sqr(b — a) * Sqr(a — b).
Since i 2 = -1 and the other components of each side are identical, it follows that 1 = -1. It easily follows that every minus sign can be replaced by a plus, all debits are credits, all liabilities are assets, and the Pope is Jewish. (Proof of the latter: Since 1 = -1, adding 1 to each side gives 2 = 0. Halving both sides, 1 = 0. Adding 1 to both sides, 2 = 1. Now, the Pope and Jackie Mason — who is Jewish — are two people, therefore they are one person, therefore the Pope is Jewish.)
Where is the logical flaw?
———————————————
The flaw is right up there at the beginning. Since, for any number X whatsoever — positive, negative, real or complex — there are two numbers whose square is equal to X, we have to settle on a precise definition of the term “square root.” The usual definition is as follows: The square root of X is the number whose square is equal to X, and whose amplitude (Prime Obsession, Figure 11-2) is between zero (inclusive) and pi (exclusive).
This means that the square root of 4 is 2, not -2; and the square root of -4 is 2i, not -2i.
If you put x = 13 and y = 9, you will now see that the “obvious truth” I started with is, in fact, false!
(Because the left-hand side is the square root of 4, which is 2, while the right-hand side is i times the square root of -4, which is i times 2i, which is -2.)
==============================
September 30th, 2003
My National Review Online “Diary” column for September 2003 included a brainteaser: “Edward and Edwin.” I took this from Raymond Smullyan’s engrossing little book of logic puzzles, The Riddle of Scheherazade. Here is the puzzle, followed by a worked solution, both in Smullyan’s precise words.
Edward and Edwin
————————
There is a pair of identical twins named Edward and Edwin, who are indistinguishable in appearance. One day shortly after they were grown, a strange disease struck them both and changed their lives forever. Henceforth, each twin was in one of three psychological states — State 1, or State 2, or State 3 — that alternated in a constant cyclical pattern: 1, 2, 3, 1, 2, 3, 1,... and so on. Curiously enough, at any given time, both brothers were in the same state — both were in either State 1, or State 2, or State 3. There was, however, a crucial difference. Edward always lied when he was in State 1, but told the truth in the other two states. Edwin, on the other hand, lied when in State 2, but told the truth when in State 1 or State 3.
One day, one of the brothers was asked: “Are you either Edwin in State 2 or Edward not in State 1?” From his answer, is it possible to deduce what state he is in? From his answer, can one deduce whether he is Edward or Edwin?
———————————————
Solution:
You cannot tell what state he is in, but you can tell who he is.
Suppose he answers yes. If he is in a truthful state, then he really is either Edwin in State 2 or Edward not in State 1. But he then can’t be Edwin in State 2 (in which he lies); hence he must be Edward, but not in State 1.
On the other hand, if he lied, then, contrary to what he said, he is neither Edwin in State 2 nor Edward not in State 1; hence he is either Edwin not in State 2 (and thus in a truthful state) or Edwin in State 1, but he can’t be Edwin not in State 2, since he lied; hence he must be Edward in State 1.
This proves that if he answers yes, he must be Edward (maybe in State 1 or maybe not).
Now, suppose he answers no. If his answer is truthful, then he is neither Edwin in State 2 nor Edward not in State 1; hence he is either Edwin not in State 2 or Edward in State 1. But he can’t be Edward in State 1, since he told the truth; so he must be Edwin (but not in State 2).
On the other hand, if he lied, then he is either Edwin in State 2 or Edward not in State 1, but the latter alternative is not possible (since Edward not in State 1 doesn’t lie), so he must then be Edwin in State 2. Thus, if he answers no, he must be Edwin.
In summary, if he answers yes, he is Edward, and if he answers no, he is Edwin.
==============================
May 31st, 2003
My National Review Online “Diary” column for May 2003 included a brainteaser about two brothers who sold their sheep at market.
Selling Sheep
——————
Brothers Angus and Hughie raise sheep in the Highlands. They take the flock to market one day and sell all the sheep. By odd coincidence, the price per sheep was the same as the number of sheep, that is, the total sum received by the brothers was a perfect square.
The brothers collect their earnings as a stack of 10-pound notes and less than ten 1-pound coins. They go home with the intention to divide it 50-50. The ten-spots are counted out, but Hughie winds up with one more ten-spot than Angus. Hughie shoves the stack of coins across the table to Angus and says: “That makes it close to even, but not quite. I’ll write you a draft to square our accounts.”
How much was the draft for?
———————————————
The solution hinges on the following fact about perfect squares. (That is, the squares of whole numbers.)
A perfect square that has an odd number of tens must end in 6.
This is because, if you square a whole number, your answer is (a) an even number of tens, plus (b) the square of your number’s units. Examples:
Square 12. You get 140 (that is, fourteen tens) plus 4 (the square of 2).
Square 37. You get 1320 (that is, 132 tens) plus 49 (the square of 7).
Square 7,239. You get 52,403,040 (that is, 5,240,304 tens) plus 81 (the square of 9).
This is bound to be the case. If the number of tens in your original number is T, and the number of units is U, then your number is 10T+U. Squaring that gives you 100*T2 + 20*T*U + U2. The number of tens in this answer is 10*T2 + 2*T*U, which is certainly an even number: it is 2 times the whole number 5*T2 + T*U.
The only way a perfect square can have an odd number of tens, therefore, is by acquiring them when you add U2. If I add something to an even number and get an odd result, the thing I added must have been odd. The number of tens in U2 therefore needs to be odd. Since U is a single digit from 0 to 9, U2 is one of the following: 0, 1, 4, 9, 16, 25, 36, 49, 64, 81. The only ones with an odd number of tens are 16 and 36. Q.E.D.
Now, since the total sum the brothers are dividing is a perfect square, and since we know that the number of tens is odd, we know that the number of units is 6. In bills, Hughie has one more 10-spot than Angus. After giving him the 6 coins, he is up by only 4 pounds.
Therefore the draft is for two pounds.
==============================
November 30th, 2002
My National Review Online “Diary” column for November 2002 included a brainteaser about monkeys and doors. Here it is..
Monkeys and Doors
—————————
There are 100 doors, all closed. In a nearby cage are 100 monkeys. The first monkey is let out, and runs along the doors opening every one. The second monkey is then let out, and runs along the doors closing the 2nd, 4th, 6th,... all the even-numbered doors. The third monkey is let out. He attends only to the 3rd, 6th, 9th,... doors (every third door, in other words), closing any that is open and opening any that is closed. The fourth monkey does the same for the 4th, 8th, 12th, 16th,... doors, opening the closed ones and closing the open ones. The fifth monkey does the same to the 5th, 10th, 15th,... doors, and so on. After all 100 monkeys have done their work in this way, which doors are left open?
One nice thing about this puzzle is that the number “100” is arbitrary. In fact, the question would still make sense, and still have the same answer, if the number of doors and monkeys was infinite!
———————————————
Solution. Look at it from the doors’ point of view. I am door number N. How many monkeys will attend to me? The first monkey, obviously. If N is even, the second monkey. If N divides by 3, the third monkey. ... In fact, the number of monkeys that will attend to me is equal to the number of numbers that divide exactly into N. Now, the number of numbers that divide exactly into N is what mathematicians call “an arithmetic function.” This particular function is d(N), most properly described as “the number of factors of N.”
Door number N will be left open if d(N) is an odd number. The only N for which d(N) is an odd number are the perfect squares. If N is a perfect square, then it has an odd number of factors. For example, 36 is a perfect square, and it has nine factors: 1, 2, 3, 4, 6, 9, 12, 18, and 36. Contrariwise, 28 is not a perfect square, and so it has an even number of factors — actually six:1, 2, 4, 7, 14, and 28.
The answer is therefore: “Any door whose number is a perfect square.” In the case of 100 doors and 100 monkeys, this means doors number 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. The answer as stated, however, applies equally well to a thousand monkeys and doors, or a million, or an infinite number.
==============================
October 31st, 2002
In my October diary on National Review Online I posed the following little math problem.
Three teams compete in a hockey tournament. Team A beats team B, team B beats team C, and team C beats team A. Fewer than 40 goals were scored in the tournament. Team A says they should win the tournament because they scored the most goals. Team B says they should win the tournament because they had the best goal differential (goals-for minus goals-against). Team C says they should win because they had the best goal ratio (goals-for divided by goals-against). While the judges are deciding who to give the trophy to, determine the score of each game.
To my embarrassment (having confessed, when I posed the problem, that I didn’t know how to do it), plenty of readers worked through it to get the correct game scores, which were: 13-12, 3-0, and 7-3.
The solutions fell into two broad categories, the “verbal” and the “algebraic.” From an esthetic point of view, the “verbal” solutions — those that use a minimum of algebraic symbols — are of course superior. I show a couple of the most succinct ones below. For the sake of mathematical rigor, I also give a third, purely “algebraic,” solution.
All solutions, of both types, rest on two key insights: (1) that we seek the minimum possible answer to every question that arises in solving the problem, and (2) that the three goal differentials must net to zero, so that at least one of them must be positive and at least one negative.
Forcing everything to the minimum gives the minimum possible number of total goals, 38. There is no solution with fewer total goals than this. The next solution has 40 total goals, so the 38 total is the only one satisfying the problem as stated. (“Fewer than 40 goals were scored in the tournament.”) If you remove the “fewer than 40 goals” condition, there is a solution with 40 goals, no solution with 41 goals, and then a solution for every number from 42 onwards. The smallest solution with no zero scores is 16-15, 4-1, 8-4 (I think), for a total 48 goals.
Verbal solution 1 (from DanFMarsh@aol.com)
The trick is to think in terms of scoring margins. Since we have a constraint on scoring, we’re going to frequently look for the smallest possible values.
Since Team C has the highest winning percentage, it must have also have more wins than losses. So its scoring margin is at least +1. Team B has the largest scoring margin, so it must be at least +2.
For team B have a +2 winning margin in spite of losing to team A, it must have beaten team C by three points. For team A have more points than team B, they also have to score 3 points against team C. Since team C gave up at least 6 points, it must have scored at least 7.
Since any points scored against team B ruins team B’s scoring differential, team C must have scored all their points against team A. That means team C beat team A, 7-3, but lost to team B, 0-3.
Now, team B must have a scoring ratio lower than 7:6, but a +2 scoring differential. The lowest such ratio is 15:13. That means they lost to Team A, 12-13. And sure enough, that means team A scored 16 points, 1 more than team B.
OK, that ratio works all the way around. We have a total of 38 points scored, and 38 points given up. The equation is balanced, and the total is under 40.
Verbal solution 2 (from Hei Lun Chan)
<1> Since C has the best goal ratio, their goal differential must be at least +1.
<2> Since B has the best goal differential, it must be at least +2. That means B must beat C by at least 2 more goals than A beat B.
<3> B must beat C by at least 3, since they lost to A by at least 1.
<4> C must beat A by at least 4, from <1> and <3>.
<5> In the C-A game, A must score at least 3, from <2> and they must also score the most overall goals. (Since B’s total score is at least two more than the sum of A’s score in A-B and C’s score in B-C, and A’s total score is at least 1 higher than B’s total score, it must follow that A’s score in C-A must be at least 3 higher than C’s score in B-C, which right now is at least 0.)
<6> C-A must be at least 7-3, from <4> and <5>.
<7> B-C must be at least 3-0, from <3>.
<8> If the exact scores from <6> and <7> are true, then A must beat B by only 1 goal, since any bigger margin would make B’s goal differential fewer than 2.
<9> C’s goal ratio is 7:6. B’s goal ratio must be less. With a +2 goal differential, B must at least score 15 goals and allow at least 13.
<10> A-B must be at least 13-12 to satisfy <8> and <9>.
<11> A-B could potentially be 14-13, 15-14, etc., but that would violate the “fewer than 40” condition.
So the scores must be: 13-12, 3-0, and 7-3.
Typical “algebraic” solution (from several readers)
<01> Rename the teams Alpha, Bravo, and Charlie for improved clarity.
<02> Use upper-case letters for winning scores, lower-case for losing scores.
<03> The scores of the three games are then A:b, B:c, and C:a.
<04> We have to find the six numbers A, B, C, a, b, and c.
<05> Note they are all whole numbers; and the winning scores A, B, and C are all greater than zero; and, since there were no ties, every game was won by at least one goal.
<06> For Alpha, total goals “for” are A+a, total goals “against” are C+b, differential is A+a-C-b, ratio is (A+a)/(C+b).
<07> For Bravo, total goals “for” are B+b, total goals “against” are A+c, differential is B+b-A-c, ratio is (B+b)/(A+c).
<08> For Charlie, total goals “for” are C+c, total goals “against” are B+a, differential is C+c-B-a, ratio is (C+c)/(B+a).
<09> If you add all three differentials, they net to zero. So at least one is positive and one negative.
<10> Since Bravo’s is the biggest differential, it must be positive.
<11> I.e. B+b-A-c > 0
<12> I.e. B+b > A+c
<13> Since both A and B are positive, I can divide: (B+b)/(A+c) > 1
<14> But that is just Bravo’s ratio...
<15> ...which is smaller than Charlie’s ration (because Charlie’s is the biggest ratio).
<16> So Charlie’s ratio (C+c)/(B+a) is also bigger than 1.
<17> I.e. (C+c)/(B+a) > 1.
<18> So C+c > B+a.
<19> I.e. C+c-B-a is positive.
<20> That is just Charlie’s differential.
<21> Being positive, and a whole number, it is at least 1.
<22> So Bravo’s differential, which is bigger, is at least 2.
<23> Since the three differentials net to zero, Alpha’s differential is at most -3.
<24> Since Alpha won the A:b game by at least 1, they must have lost the C:a game by at least 4, to get such a differential.
<25> I.e. C >= a+4.
<26> Alpha has scored the most goals, so A+a > B+b.
<27> I.e. A > B+b-a.
<28> From <22>, Bravo’s differential is at least 2.
<29> I.e. B+b-A-c is at least 2.
<30> I.e. (B+b-c)-A is at least 2.
<31> But <27> says that A > B+b-a.
<32> If, instead of subtracting A in <30>, I subtract the smaller thing, the result must then be bigger than 2
<33> I.e. (B+b-c)-(B+b-a) > 2.
<34> I.e. a-c > 2.
<35> I.e. a > c+2.
<36> So a is at least 3.
<37> And so, from <25>, the minimum score for the C:a game is 7:3. On the minimizing principle, I shall suppose this is the actual score.
<38> Since the differential in the C:a game is then 4, if Charlie is to have his minimum net differential of 1 (see <21>), the differential in the B:c game must be 3.
<39> I.e. B = c+3.
<40> Since the differential in the B:c game is 3, for Bravo to get his minimum net differential of 2, the differential in the A:b game must be 1.
<41> I.e. A = b+1.
<42> Charlie’s for/against ratio is (C+c)/(B+a).
<43> From <37> and <39>, this is equal to (7+B-3)/(3+B).
<44> I.e. (B+4)/(B+3),...
<45> ...which is 1 + 1/(B+3).
<46> Bravo’s for/against ratio is (B+b)/(A+c).
<47> From <39> and <41>, this is equal to (B+A-1)/(B-3+A),...
<48> ...which is 1 + 2/(A+B-3).
<49> Since Charlie’s ratio in <45> is greater than Bravo’s in <48>, 1/(B+3) > 2/(A+B-3).
<50> Cross-multiplying: A+B-3 > 2B+6.
<51> So A > B+9.
<52> From <39>, B is at least 3.
<53> So A is at least 13.
<54> From <40>, the minimum possibility for the A:b game is then 13:12.
<55> In <37> we decided that the C:a score is 7:3. So to get the right differentials, the B:c score must be 3:0.
<56> These scores — 13:12, 3:0, and 7:3 — satisfy all the conditions of the problem, as shown above.
<57> Since we took minimum possibilities at every point, no smaller solution is possible.
<58> Since the problem requires less than 40 goals scored altogether, and this solution has 38, the only bigger solution possible is one with total 39 goals scored. Is there such a solution?
<59> To get a 39-goal total, either Alpha, or Bravo, or Charlie needs an extra goal.
<60> If Alpha in the A:b game, then Bravo loses the lead in differential: -2, 1, 1.
<61> If Alpha in the C:a game, then Charlie loses the lead in ratio: 17/19, 15/13, 7/7.
<62> If Bravo in the A:b game, then Alpha no longer wins this game, it’s a tie.
<63> If Bravo in the B:c game, then Alpha no longer has most goals (it’s 16, 16, 7).
<64> If Charlie in the B:c game, then Bravo no longer leads in differentials (it’s -3, 1, 2).
<65> If Charlie in the C:a game, same problem (it’s -4, 2, 2).
<66> There is thus no other solution in less than 40 goals.
==============================