-
Notifications
You must be signed in to change notification settings - Fork 0
/
puzzles.html
1117 lines (1035 loc) · 70.3 KB
/
puzzles.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<html>
<head>
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<title>Rustan Leino's Puzzle Page</title>
<style type="text/css">
.style1 {
font-family: Verdana;
}
</style>
</head>
<body>
<font face='verdana, arial, geneva, sans-serif'>
<h1>Puzzles</h1>
<img alt="puzzles" border="0" src="images/puzzle.gif" align="right" width="120" height="90">
<p>Here are some mathematical puzzles that
I (Rustan Leino) have enjoyed. Most of them
are of the kind that you can discuss and solve at a dinner table, usually
without pen and paper. So as not to spoil your fun, no solutions are given
on this page, but for some problems I have provided some hints. </p>
<ul>
<li>
<img border="0" src="images/new.gif" width="28" height="19" alt="new, October 2014">
<a href="#Half the area of an L">Half the area of an L</a></li>
<li>
<img border="0" src="images/new.gif" width="28" height="19" alt="new, October 2014">
<a href="#A game of 2014 cards">A game of 2014 cards</a></li>
<li>
<img border="0" src="images/new.gif" width="28" height="19" alt="new, October 2014">
<a href="#Evaluating a polynomial">Evaluating a polynomial</a></li>
<li><a href="#Picking the larger of two cards">Picking the larger of two cards</a></li>
<li><a href="#Enclosing land by fence pieces">Enclosing land by fence pieces</a></li>
<li><a href="#Planar configuration of straight connecting lines">Planar
configuration of straight connecting lines</a></li>
<li><a href="#Reducing nearby enemies">Reducing nearby enemies</a></li>
<li><a href="#Transporting bananas">Transporting bananas</a></li>
<li><a href="#Car and key hide-and-seek">Car and key hide-and-seek</a></li>
<li><a href="#Handshakes at a dinner party">Handshakes at a dinner party</a></li>
<li><a href="#Rectifying a pill mistake">Rectifying a pill mistake</a></li>
<li><a href="#Chomp">Chomp</a></li>
<li><a href="#Alternating T-shirt colors">Alternating T-shirt colors</a></li>
<li><a href="#Digit sums of multiples of 11">Digit sums of multiples of 11</a></li>
<li><a href="#Weighing piles of coins">Weighing piles of coins</a></li>
<li><a href="#Guessing each other's coins">Guessing each other's coins</a></li>
<li><a href="#The duck and the fox">The duck and the fox</a></li>
<li><a href="#Dropping eggs">Dropping eggs</a></li>
<li><a href="#Age of children">Age of children</a></li>
<li><a href="#Capturing a pirate ship">Capturing a pirate ship</a></li>
<li><a href="#3-person duel">3-person duel</a></li>
<li><a href="#The genders of the neighboring family's children">The
genders of the neighboring family's children</a></li>
<li><a href="#Finding a hermit">Finding a hermit</a></li>
<li><a href="#Witches at a coffee shop">Witches at a coffee shop</a></li>
<li><a href="#Lemmings on a ledge">Lemmings on a ledge</a></li>
<li><a href="#Poisoned wine">Poisoned wine</a></li>
<li><a href="#Dropping 9-terms from the harmonic series">Dropping 9-terms from the harmonic series</a></li>
<li><a href="#Finding a restaurant in a park">Finding a restaurant in a park</a></li>
<li><a href="#Opening boxes in a prison courtyard">Opening boxes in a prison courtyard</a></li>
<li><a href="#Frugal selection of weights to determine the weight of a thing">Frugal selection of weights to determine the weight of a thing</a></li>
<li><a href="#Initializing an array in constant time">Initializing an array in constant time</a></li>
<li><a href="#Translation error in a cookbook">Translation error in a cookbook</a></li>
<li><a href="#Making a square larger">Making a square larger</a></li>
<li><a href="#Catching a spy">Catching a spy</a></li>
<li><a href="#Average clan size">Average clan size</a></li>
<li><a href="#Colored balls in boxes">Colored balls in boxes</a></li>
<li><a href="#Mixed up airplane seats">Mixed up airplane seats</a></li>
<li><a href="#Multiples in the Fibonacci series">Multiples in the Fibonacci series</a></li>
<li><a href="#Coins in a line">Coins in a line</a></li>
<li><a href="#Determining the number of one hat">Determining the number of one hat</a></li>
<li><a href="#Voting on how to distribute coins">Voting on how to distribute coins</a></li>
<li><a href="#Subsequence of coin tosses">Subsequence of coin tosses</a></li>
<li><a href="#Children and light switches">Children and light switches</a></li>
<li><a href="#Finding a counterfeit coin">Finding a counterfeit coin</a></li>
<li><a href="#Cutting cheese">Cutting cheese</a></li>
<li><a href="#Fair soccer championship">Fair soccer championship</a></li>
<li><a href="#Path on the surface of the Earth">Path on the surface of the Earth</a></li>
<li><a href="#Random point in a circle">Random point in a circle</a></li>
<li><a href="#Mixing vinegar and oil">Mixing vinegar and oil</a></li>
<li><a href="#Psycho killer">Psycho killer</a></li>
<li><a href="#A special squarish age">A special squarish age</a></li>
<li><a href="#Passing alternating numbers of coins around">Passing alternating numbers of coins around</a></li>
<li><a href="#The exact batting average">The exact batting average</a></li>
<li><a href="#Summing pairs of numbers to primes">Summing pairs of numbers to primes</a></li>
<li><a href="#Right triangle with a 23">Right triangle with a 23</a></li>
<li><a href="#The worm and the rubber band">The worm and the rubber band</a></li>
<li><a href="#Placing coins on a table">Placing coins on a table</a></li>
<li><a href="#Determining a hidden digit">Determining a hidden digit</a></li>
<li><a href="#Boris and Natasha">Boris and Natasha</a></li>
<li><a href="#Burning ropes to measure time">Burning ropes to measure time</a></li>
<li><a href="#Flipping cards">Flipping cards</a></li>
<li><a href="#Three hat colors">Three hat colors</a></li>
<li><a href="#The line of persons with hats">The line of persons with hats</a></li>
<li><a href="#The prisoners and the switch">The prisoners and the switch</a></li>
<li><a href="#Table with four coins">Table with four coins</a></li>
<li><a href="#Stabilizing nodes from an anchor">Stabilizing points from an anchor</a></li>
<li><a href="#Points on a circle">Points on a circle</a></li>
<li><a href="#The electrician problem">The electrician problem</a></li>
<li><a href="#The hidden card">The hidden card</a></li>
<li><a href="#Knight, knave, commoner">Knight, knave, commoner</a></li>
</ul>
<h2><a name="Half the area of an L"></a>Half the area of an L</h2>
<!-- added Oct 2014 -->
<p><img alt="new Oct 2014" height="19" src="images/new.gif" width="28">[I was
asked this puzzle by Vlad Rusu, who in turn heard it from Grigore Rosu and family]</p>
<p>Two arbitrary rectangles are placed to form an "L". That is, the lower left-hand corner
of the two rectangles share the same point. (What I'm trying to say is that there's an
"L" whose "I" and "_" parts have arbitrary widths and heights.) Using only a (pen and a)
straightedge (that is, no measuring device and no compass), figure out a way to, with a
single straight cut, divide the "L" into two pieces of equal area. </p>
<h2><a name="A game of 2014 cards"></a>A game of 2014 cards</h2>
<!-- heard Jan 2014, added Oct 2014 -->
<p><img alt="new Oct 2014" height="19" src="images/new.gif" width="28">[I got this
problem from Radu Grigore, who I think told me it was a problem used in the 2009 Math
Olympics. I suppose perhaps the problem then involved 2009 cards.]</p>
<p>There is a table with a row of 2014 cards. Each card has a red side and
a blue side. We'll say that a card is red if the color on its visible face
is red, and analogously for blue. Two players take turns to do the
following move: select any 50 consecutive cards where the left-most card
is red, then flip each of those 50 cards (thus, for those 50 cards, turning red
cards into blue cards and blue cards into red cards). Both players look at
the cards from the same side of the table, so "left-most" means the same to both
of the players (that is, you can think of one of the ends of the table as being
designated as the left end). When it is a player's turn, if that player
cannot make a move (that is, if there is no way to select 50 consecutive cards
the left-most one of which is red), then that player loses and the other player
wins. If you are one of the players and all cards are initially red, can
you be sure to win, and if so, do you want to be the player who goes first or
second?</p>
<h2><a name="Evaluating a polynomial"></a>Evaluating a polynomial</h2>
<!-- heard Jan 2014, added Oct 2014 -->
<p><img alt="new Oct 2014" height="19" src="images/new.gif" width="28">[Prakash Panangaden
told me this problem]</p>
<p>There is a polynomial and you have access to a function that evaluates that
polynomial at a given number. You don't know the degree of the polynomial,
nor do you know any of the coefficients of its terms. However, you are
told that all coefficients are non-negative integers. How many times do
you need to call the evaluation function in order to identify the polynomial
(that is, to figure out the values of its coefficients)?</p>
<h2><a name="Picking the larger of two cards"></a>Picking the larger of two cards</h2>
<!-- added Sep 2012 -->
<p><img alt="new Sep 2012" height="19" src="images/new.gif" width="28">[Roger
Wattenhofer told me this puzzle]</p>
<p>Someone picks, at their will, two cards from a deck of cards. The cards have
different numbers, so one is higher than the other. (In other words, the person
picks two distinct numbers in the inclusive range 1 through 13.) The cards
are placed face down on a table in front of you. You get to choose one of
the cards and turn it face up. Now, you will select one of the two cards
(one of whose face you can see, the other one you can't). If you select
the highest card, you win. Design a card-selection strategy for which your
chance of winning is strictly greater than 50%. </p>
<h2><a name="Enclosing land by fence pieces"></a>Enclosing land by fence pieces</h2>
<!-- received September 2011, added October 2011 -->
<p>[I got this puzzle from Serdar Tasiran.]</p>
<p>You are given one 44-meter piece of fence and 48 one-meter pieces of fence.
Assume each piece is a straight and unbendable. What is the large area of
(flat) land that you can enclose using these fence pieces?</p>
<h2><a name="Planar configuration of straight connecting lines"></a>Planar configuration of straight connecting lines</h2>
<!-- added September 2011 -->
<p>[Radu Grigore told me this problem. I think may have heard it 20 years earlier from Jan van de Snepscheut.]</p>
<p>Given an even number of points in general positions on the plane (that is, no
three points co-linear), can you partition the points into pairs and connect the
two points of each pair with a single straight line such that the straight lines
do not overlap?</p>
<h2><a name="Reducing nearby enemies"></a>Reducing nearby enemies</h2>
<!-- received July 2011, added September 2011 -->
<p>[I got this puzzle from Jason Koenig.]</p>
<p>You are given an irreflexive symmetric (but not necessarily transitive)
"enemies" relation on a set of people. In other words, if person A is an
enemy of a person B, then B is also an enemy of A. How can you divide up
the people into two houses in such a way that every person has at least as many
enemies in the other house as in their own house?</p>
<p>[Hint: As Radu Grigore pointed out to me, solving the
<a href="#Planar configuration of straight connecting lines">Planar
configuration of straight connecting lines</a> puzzle may provide a hint to
solving this puzzle.]</p>
<h2><a name="Transporting bananas"></a>Transporting bananas</h2>
<!-- received August 2011, added September 2011 -->
<p>[Rupak Majumdar told me this intriguing puzzle.]</p>
<p>You have 3000 bananas that you want to transport a distance of 1000 km.
The transport will be done by a monkey. The monkey can carry as many as 1000 bananas
at any one time. With each kilometer traveled (forward or backward), the money
consumes 1 banana. How many bananas can you get across to the other side?</p>
<h2><a name="Car and key hide-and-seek"></a>Car and key hide-and-seek</h2>
<!-- received August 2011, added September 2011 -->
<p>[A puzzle Aistis Simaitis gave me inspired this puzzle.]</p>
<p>In a room are three boxes that on the outside look identical. One of
the boxes contains a car, one contains a key, and one contains nothing.
You and a partner get to decide amongst yourselves to each point to two boxes.
When you have made your decision, the boxes are opened and their contents
revealed. If one of the boxes your partner is pointing to contains the car
and one of the boxes you are pointing to contains the key, then you will both win.
What strategy maximizes the probability of winning, and what is the probability
that you will win?</p>
<h2><a name="Handshakes at a dinner party"></a>Handshakes at a dinner party</h2>
<!-- added September 2011 -->
<p>[Pamela Zave shared this problem with me.]</p>
<p>Hilary and Jocelyn are throwing a dinner party at their house and have invited
four other couples. After the guests arrive, people greet each other by
shaking hands. As you would expect, a couple do not shake hands with each
other and no two people shake each other's hands more than once. At some
point during the handshaking process, Jocelyn gets up on a table and tells
everyone to stop shaking hands. She also asks each person how many hands
they have shaken and learns that no two people on the floor have shaken the same
number of hands. How many hands has Hilary shaken?</p>
<h2><a name="Rectifying a pill mistake"></a>Rectifying a pill mistake</h2>
<!-- received January 2011, added 17 March 2011 -->
<p>[This is a slight rewording of a problem I got from Phil Wadler, who said he read the problem on
<a href="http://wiki.xkcd.com/irc/Puzzles">xkcd</a>.]</p>
<p>A man has a medical condition that requires him to take two kinds of pills,
call them A and B. The man must take exactly one A pill and exactly one B pill
each day, or he will die. The pills are taken by first dissolving them in
water.</p>
<p>The man has a jar of A pills and a jar of B pills. One day, as he is about
to take his pills, he takes out one A pill from the A jar and puts it in a glass
of water. Then he accidentally takes out <em>two</em> B pills from the B jar and
puts them in the water. Now, he is in the situation of having a glass of
water with three dissolved pills, one A pill and two B pills. Unfortunately,
the pills are very expensive, so the thought of throwing out the water with the
3 pills and starting over is out of the question. How should the man proceed in
order to get the right quantity of A and B while not wasting any pills?</p>
<h2><a name="Chomp"></a>Chomp</h2>
<!-- received March 2010, added 2 December 2010 -->
<p>[Clark Barrett told me this problem.]</p>
<p>Given is a (possibly enormous) rectangular chocolate bar, divided into small squares
in the usual way. The chocolate holds a high quality standard, except for the square in the lower left-hand corner, which is poisonous. Two players take turns eating
from the chocolate in the following manner: The player whose turn it is points to any
one of the remaining squares, and then eats the selected square and all squares
positioned above the selected square, to the right of the selected square, or both above
and to the right of the selected square. Note, although the board starts off rectangular,
it may take on non-rectangular shapes during game play. The object of the game is to
avoid the poisonous square. Assuming the initial chocolate bar is larger than 1x1, prove
that the player who starts has a winning strategy.</p>
<p>Hint: To my knowledge, no efficient strategy for winning the game is known. That is,
to decide on the best next move, a player may need to consider all possible continuations
of the game. Thus, you probably want to find a non-constructive proof. That is, to prove
that the player who starts has a winning strategy, prove just the existence of such a
strategy; in particular, steer away from proofs that would construct a winning strategy for
the initial player.
</p>
<h2><a name="Alternating T-shirt colors"></a>Alternating T-shirt colors</h2>
<!-- received summer 2010, added 2 December 2010 -->
<p>[I received this puzzle from Vladislav Shcherbina, but I changed gloves into T-shirts to emphasize
the people rather than the spaces between them.]</p>
<p>Ten friends walk into a room where each one of them receives a hat. On
each hat is written a real number; no two hats have the same number. Each
person can see the numbers written on his friends' hats, but cannot see his own.
The friends then go into individual rooms where they are each given the choice
between a white T-shirt and a black T-shirt. Wearing the respective T-shirts they
selected, the friends gather again and are lined up in the order of their hat
numbers. The desired property is that the T-shirts colors now alternate.</p>
<p>The friends are allowed to decide on a strategy before walking into the room
with the hats, but they are not otherwise allowed to communicate with each other
(except that they can see each other's hat numbers). Design a strategy that
lets the friends always end up with alternating T-shirt colors.</p>
<h2><a name="Digit sums of multiples of 11"></a>Digit sums of multiples of 11</h2>
<!-- added February 2010 -->
<p>[I got this one from Madan Musuvathi.]</p>
<p>Some multiples of 11 have an even digit sum. For example, 7*11 = 77 and
7+7 = 14, which is even; 11*11 = 121 and 1+2+1 = 4, which is even. Do all multiples of 11 have
an even digit sum? (Prove that they do or find the smallest that does
not.)</p>
<h2><a name="Weighing piles of coins"></a>Weighing piles of coins</h2>
<!-- added January 2010 -->
<p>[I got this puzzle from Dave Detlefs, who read it in an MIT Alumni magazine.
This puzzle is a bit more involved than most puzzles on my page, so you may want
a paper and pen (and some tenacity) for this one. Once you get into it,
though, it's a hard puzzle to put aside until you've solved it.]</p>
<p>There are two kinds of coins, genuine and counterfeit. A genuine coin weighs
X grams and a counterfeit coin weighs X+delta grams, where X is a positive
integer and delta is a non-zero real number strictly between -5 and +5. You are
presented with 13 piles of 4 coins each. All of the coins are genuine, except
for one pile, in which all 4 coins are counterfeit. You are given a precise
scale (say, a digital scale capable of displaying any real number). You are to
determine three things: X, delta, and which pile contains the counterfeit
coins. But you're only allowed to use the scale twice! </p>
<h2><a name="Guessing each other's coins"></a>Guessing each other's coins</h2>
<!-- added September 2009 -->
<p>[I got this puzzle from Raphael Reischuk, who also has a little
<a href="http://www.infsec.cs.uni-sb.de/~reischuk/riddles/">puzzle collection</a>.]</p>
<p>You and a friend each has a fair coin. You can decide on a
strategy and then play the following game, without any further
communication with each other. You flip your coin and then write
down a guess as to what your friend's coin will say. Meanwhile,
your friend flips her coin and writes down a guess as to what your
coin says. There's a third person
involved: The third person collects your guesses and inspects
your coins. If both you and your friend correctly guessed each
other's coins, then your team (you and your friend) receive 2
Euros from the third person. But if either you or your friend (or
both) gets the guess wrong, then your team has to pay 1 Euro to the third person. This procedure is repeated all day. Assuming your object is to
win money, are you happy to be on your team or would you rather trade
places with the third person?
</p>
<h2><a name="The duck and the fox"></a>The duck and the fox</h2>
<!-- added March 2009 -->
<p>[I got this problem from Koen Claessen.]</p>
<p>A duck is in circular pond. The duck wants to swim ashore, because it
wants to fly off and this particular duck is not able to start flying from the
water. There is also a fox, on the shore. The fox wants to eat the
duck, but this particular fox cannot swim, so it can only hope to catch the duck
when the duck reaches the shore. The fox can run 4 times faster than the
duck can swim. Is there always a way for the duck to escape?</p>
<h2><a name="Dropping eggs"></a>Dropping eggs</h2>
<!-- added January 2009 -->
<p>[I think I've heard some version of this problem before, but heard this one
from Sophia Drossopoulou and Alex Summers.]</p>
<p>There's a certain kind of egg about which you wonder: What is the
highest floor of a 36-story building from which you can drop an egg without it
breaking? All eggs of this kind are identical, so you can conduct
experiments. Unfortunately, you only have 2 eggs. Fortunately, if an
egg survives a drop without breaking, it is as good as new--that is, you can
then conduct another dropping experiment with it. What is the smallest
number of drops that is sure to determine the answer to your wonderings?</p>
<h2><a name="Age of children"></a>Age of children</h2>
<!-- added January 2009 -->
<p>[I got this problem from the book <em>In code: a mathematical journey </em>by
Sarah Flannery and David Flannery.]</p>
<p>A (presumed smart) insurance agent knocks on a door and a (presumed smart)
woman opens. He introduces himself and asks if she has any children.
She answers: 3. When he then asks their ages (which for this problem we
abstract to integers), she hesitates. Then she decides to give him some
information about their ages, saying "the product of their ages is 36". He
asks for more information and she gives in, saying "the sum of their ages is
equal to our neighbors' house number". The man jumps over the fence,
inspects the house number, and the returns. "You need to give me another
hint", he begs. "Alright", she says, "my oldest child plays the piano".
What are the ages of the children?</p>
<h2><a name="Capturing a pirate ship"></a>Capturing a pirate ship</h2>
<!-- added January 2009 -->
<p>[Howard Lederer sent me this problem.]</p>
<p>You're on a government ship, looking for a pirate ship. You know that
the pirate ship travels at a constant speed, and you know what that speed is.
Your ship can travel twice as fast as the pirate ship. Moreover, you know
that the pirate ship travels along a straight line, but you don't know what that
line is. It's very foggy, so foggy that you see nothing. But then!
All of a sudden, and for just an instant, the fog clears enough to let you
determine the exact position of the pirate ship. Then, the fog closes in
again and you remain (forever) in the thick fog. Although you were able to
determine the position of the pirate ship during that fog-free moment, you were
not able to determine its direction. How will you navigate your government
ship so that you will capture the pirate ship? </p>
<h2><a name="3-person duel"></a>3-person duel</h2>
<!-- added January 2009 -->
<p>[I got this problem from Johannes Kinder, who said he heard it from his
brother. I reformulated the setting.]</p>
<p>A particular basketball shootout game consists of a number of duels. In
each duel, one player is the challenger. The challenger chooses another
player to challenge, and then gets one chance to shoot the hoop. If the
player makes the shot, the playing being challenged is out. If the player
does not make the shot, or
if the player chooses to skip his turn, then the game continues with the next
duel. A player wins when only that player remains.</p>
<p>One day, this game is played by three players: A, B, and C. Their skill
levels vary considerably: player A makes every shot, player B has a 50%
chance of making a shot, and player C has a 30% chance of making a shot.
Because of the difference in skill levels, they decide to let C begin, then B,
then A, and so on (skipping any player who is out of the game) until there is a
winner. If everyone plays to win, what strategy should each player follow?</p>
<p>[For this follow-up question, it will be helpful to have a paper and pen--not
because the calculations are hard, but because it helps in remembering the
numbers.]</p>
<p>If A, B, and C follow their winning strategies (as determined above), which
player has the highest chance of winning the game?</p>
<h2><a name="The genders of the neighboring family's children"></a>
The genders of the neighboring family's children</h2>
<!-- added January 2009 -->
<p>[This problem was inspired by some basic probability questions mentioned in a
lecture by Eric Hehner (and that can be formalized and solved by calculation
using this <a href="http://www.cs.utoronto.ca/~hehner/ProPer.pdf">Probability
Perspective</a>), and some subsequent discussions with him, Itay Neeman, Jim
Woodcook, Ana Cavalcanti, and Leo Freitas.]</p>
<p>The house next door has some new neighbors. They have two children, but
you don't know what mix of boys and girls they are. One day, your wife
tells you "At least one of the children is a girl". What is the
probability that both are girls?</p>
<p>Your wife then tells you "The way I found out that at least one of the
children is a girl is that I saw one of the children playing outside, and it was
a girl". Now, what is the probability that both are girls?</p>
<h2><a name="Finding a hermit"></a>Finding a hermit</h2>
<!-- added January 2009 -->
<p>[Claude Marché told me this puzzle. At first, it seems quite similar to
"Catching a spy" (below), but the solution is entirely unrelated.]</p>
<p>There are five holes arranged in a line. A hermit hides in one of them.
Each night, the hermit moves to a different hole, either the neighboring hole on
the left or the neighboring hole on the right. Once a day, you get to
inspect one hole of your choice. How do you make sure you eventually find
the hermit? </p>
<h2><a name="Witches at a coffee shop"></a>Witches at a coffee shop</h2>
<p>[I got this puzzle from Alex Pintilie.]</p>
<p>Two witches each makes a nightly visit to an all-night coffee shop.
Each arrives at a random time between 0:00 and 1:00. Each one of them
stays for exactly 15 minutes. On any one given night, what is the probability that
the witches will meet at the coffee shop?</p>
<h2><a name="Lemmings on a ledge"></a>Lemmings on a ledge</h2>
<p>[Vladislav Shcherbina told me this problem.]</p>
<p>A ledge is 1 meter long. On it are N lemmings. Each lemming
travels along the ledge at a constant speed of 1 meter/minute. A lemming
continues in the same direction until it either falls off the ledge or it
collides with another lemming. If two lemmings collide, they both
immediately change their directions. Initially, the lemmings have
arbitrary starting positions and starting directions. What is the longest
time that may elapse before all lemmings have fallen off the ledge?</p>
<p>[Michael Jackson suggested the following variation of the problem:
Suppose the ledge is not horizontal, but is leaning. A lemming now travels
up the ledge at a speed of 1 meter/minute and travels down the ledge at a speed
of 2 meters/minute. What is the longest time before all lemmings have
fallen off?]</p>
<h2><a name="Poisoned wine"></a>Poisoned wine</h2>
<p>[I got this problem from Vladislav Shcherbina.]</p>
<p>You have 240 barrels of wine, one of which has been poisoned. After
drinking the poisoned wine, one dies within 24 hours. You have 5 slaves
whom you are willing to sacrifice in order to determine which barrel contains
the poisoned wine. How do you achieve this in 48 hours?</p>
<h2><a name="Dropping 9-terms from the harmonic series"></a>
Dropping 9-terms from the harmonic series</h2>
<p>[Rajeev Joshi told me this problem.]</p>
<p>The harmonic series--that is, 1/1 + 1/2 + 1/3 + 1/4 + ...--diverges.
That is, the sum is not finite. This is in difference to, for example, a
geometric series--like
<span class="style1">½<sup>0</sup></span> +
<span class="style1">½<sup>1</sup></span> +
<span class="style1">½<sup>2</sup></span> +
<span class="style1">½<sup>3</sup></span> +
...--which converges, that is, has a finite sum.</p>
<p>Consider the harmonic series, but drop all terms whose denominator
represented in decimal contains a 9. For example, you'd drop terms like
1/9, 1/19, 1/90, 1/992, 1/529110. Does the resulting series converge or
diverge?</p>
<p>[More generally, you may consider representing the denominator in the base of
your choice and dropping terms that contain a certain digit of your choice.]</p>
<p>[Here is a follow-up question suggested by Gary Leavens.]</p>
<p>Consider again the harmonic series, but drop a term only if the denominator
represented in decimal contains two consecutive 9's. For example, you'd
drop 1/99, 1/992, 1/299, but not 1/9 or 1/909. Does this series converge
or diverge?</p>
<h2><a name="Finding a restaurant in a park"></a>
Finding a restaurant in a park</h2>
<!-- updated Sep 2011 -->
<p>[Michael Jackson told me this problem, as a variation of a problem he got
from Koen Claessen.]</p>
<p>A park contains paths that intersect at various places. The
intersections all have the properties that they are 3-way intersections and that,
with one exception,
they are indistinguishable from each other. The one exception is an intersection
where there is a restaurant. The restaurant is reachable from everywhere
in the park. Your task is to find your way to the restaurant.</p>
<p>The
park has strict littering regulations, so you are not allowed to modify the
paths or intersections (for example, you are not allowed to leave a note an
intersection saying you have been there). However, you are allowed to do
some bookkeeping on a pad of paper that you bring with you at all times (in the
computer-science parlance, you are allowed some state). How can you find the restaurant?</p>
<p>You may assume that once you enter an intersection, you can continue to the
left, continue to the right, or return to where you just came from.</p>
<p>[As an
alternative puzzle, suppose you must continue through an intersection, turning
either left or right, but not turning around to exit the intersection the way
you just entered it.]</p>
<h2><a name="Opening boxes in a prison courtyard"></a>Opening boxes in a prison courtyard</h2>
<p>[I got this problem from Clark Barrett, who got it from Robert Nieuwenhuis. Just when you thought you had
heard all variations of prisoners and boxes...]</p>
<p>100 prisoners agree on a strategy before playing the following game:
One at a time (in some unspecified order), each of the prisoners is taken to a
courtyard where there is a line of 100 boxes. The prisoner gets to make
choices to open 50 of the boxes. When a box is opened, it reveals the name
of a prisoner (the prisoners have distinct names). The names written in
the boxes are in 1-to-1 correspondence with the prisoners; that is, each name is
found in exactly one box. If after opening 50 boxes, the prisoner has <em>
not</em> found his own name, the game is over and all the prisoners lose.
But if the prisoner <em>does</em> find the box that contains his name among the
50 boxes he opens, then the prisoner is taken to the other side of the courtyard
where he cannot communicate with the others, the boxes are once again closed,
and the next prisoner is brought out into the courtyard. If all prisoners
make it to the other side of the courtyard, they win.</p>
<p>One possible strategy is for each prisoner to randomly select 50 boxes and
open them. This gives the prisoners 1 chance out of 2</font><sup><span class="style1">100</span></sup><font face='verdana, arial, geneva, sans-serif'>
to win--a slim chance, indeed. But the prisoners can do better, using a
strategy that for a random configuration of the boxes will give them a larger
chance of winning. How good a strategy can you develop?
<h2><a name="Frugal selection of weights to determine the weight of a thing"></a>
Frugal selection of weights to weigh a thing</h2>
<p>[Matthew Parkinson told me this problem, or a slight variation thereof.]</p>
<p>You are given a balance (that is, a weighing machine with two trays) and a
positive integer N. You are then to request a number of weights. You
pick which denominations of weights you want and how many of each you want.
After you receive the weights you requested, you are given a <em>thing</em>
whose weight is an integer between 1 and N, inclusive. Using the balance
and the weights you requested, you must now determine the exact weight of the
<em>thing</em>.</p>
<p>As a function of N, how few weights can you get by requesting?</p>
<h2><a name="Initializing an array in constant time"></a>Initializing an array in constant time</h2>
<p>[Unlike most problems on this page, this problem requires some computer
science knowledge. Many years ago, I read a solution to this problem in
one of Donald Knuth's books (I think). The algorithm intrigued me and
stuck in my mind.]</p>
<p>Consider the following array operations. Init(N,d) initializes an array
of N elements so that each element has value d. Once Init has been called,
the following two operations can be applied: For any i such that 0 <= i <
N, Get(i) returns the array element at position i and Set(i,v) sets the array
element at position i to the value v.</p>
<p>Given any amount of memory you want, implement the three operations so that
each operation has an O(1) time complexity.</p>
<h2><a name="Translation error in a cookbook"></a>Translation error in a cookbook</h2>
<p>[This problem is a bit fuzzier than most on this page, just because I don't
know for sure that the cookbook publisher made a translation error. But I
hope you'll still enjoy the problem.]</p>
<p>Recently, I received a wonderful cookbook. In an appendix, it shows a
table that converts oven temperatures between Celsius and Fahrenheit.
(Side remark: Approximate oven temperatures are actually really simple to
convert in your head--just double the number of degrees Celsius to get the
number of degrees Fahrenheit. For oven temperatures, this will be within
10 F of the exact answer.)</p>
<p>The table has a footnote that says "If your oven has a fan, reduce the recipe
temperature by 68 F". I have a strong hunch that this footnote suffers
from a translation error. How many degrees Fahrenheit should it have said
to reduce the temperature by? (No knowledge of convection ovens required.)</p>
<h2><a name="Making a square larger"></a>Making a square larger</h2>
<p>[I got this problem from Radu Grigore.]</p>
<p>You are given four points (on a Euclidian plane) that make up the corners of
a square. You may change the positions of the points by a sequence of
moves. Each move changes the position of one point, say p, to a new
location, say p', by "skipping over" one of the other 3 points. More
precisely, p <em>skips over </em>a point q if it is moved to the diametrically
opposed side of q. In other words, a move from p to p' is allowed if there
exists a point q such that q = (p + p') / 2.</p>
<p>Find a sequence of moves that results in a larger square. Or, if no
such sequence is possible, give a proof of why it isn't possible. (The new
square need not be oriented the same way as the original square. For
example, the larger square may be turned 45 degrees from the original, and the
larger square may have the points in a different order from in the original
square.) </p>
<h2><a name="Catching a spy"></a>Catching a spy</h2>
<p>[I got this problem from Radu Grigore.]</p>
<p>A spy is located on a one-dimensional line. At time 0, the spy is at
location A. With each time interval, the spy moves B units to the right
(if B is negative, the spy is moving left). A and B are fixed integers,
but they are unknown to you. You are to catch the spy. The means by
which you can attempt to do that is: at each time interval (starting at
time 0), you can choose a location on the line and ask whether or not the spy is
currently at that location. That is, you will ask a question like "<em>Is
the spy currently at location 27?</em>" and you will get a yes/no answer.
Devise an algorithm that will eventually find the spy. </p>
<h2><a name="Average clan size"></a>Average clan size</h2>
<p>[I got this problem from Ernie Cohen, who I think had made it up. Itay
Neeman suggested the use of "clans" instead of Ernie's original "families",
because "clans" has a stronger connotation of the groups being disjoint.]</p>
<p>The people in a country are partitioned into clans. In order to
estimate the average size of a clan, a survey is conducted where 1000 randomly
selected people are asked to state the size of the clan to which they belong.
How does one compute an estimate average clan size from the data collected?</p>
<h2><a name="Colored balls in boxes"></a>Colored balls in boxes</h2>
<p>[I got this little problem from Leonardo de Moura.]</p>
<p>There are three boxes, one containing two black balls, another containing two
white balls, and another containing one black and one white ball. You
select a random ball from a random box and you find you selected a white ball.
What is the probability that the other ball in the same box is also white? </p>
<h2><a name="Mixed up airplane seats"></a>Mixed up airplane seats</h2>
<p>[I got this problem from Rajeev Joshi, who I think said he heard it from Jay
Misra.]</p>
<p>An airplane has 50 seats, and its 50 passengers have their own assigned
seats. The first person to enter the plane ignores his seat assignment and
instead picks a seat on random. Each subsequent person to enter the plane
takes her assigned seat, if available, and otherwise chooses a seat on random.
What is the probability that the last passenger gets to sit in her assigned
seat?</p>
<h2><a name="Multiples in the Fibonacci series"></a>Multiples in the Fibonacci series</h2>
<p>[Carroll Morgan told me this puzzle.]</p>
<p>Prove that for any positive K, every K<sup>th</sup>
number in the Fibonacci sequence is a multiple of the K<sup>th</sup>
number in the Fibonacci sequence.</p>
<p>
More formally, for any natural number n, let F(n) denote Fibonacci number n.
That is, F(0) = 0, F(1) = 1, and F(n+2) = F(n+1) + F(n). Prove that for any
positive K and natural n, F(n*K) is a multiple of F(K).</p>
<h2><a name="Coins in a line"></a>Coins in a line</h2>
<p>
[Rajeev Joshi told me this problem. He got it from Jay Misra.]</p>
<p>
Consider a game that you play against an opponent. In front of you are an
even number of coins of possibly different denominations. The coins are
arranged in a line. You and your opponent take turns selecting coins.
Each player takes one coin per turn and must take it from an end of the line,
that is, the current leftmost coin or the current rightmost coin. When all
coins have been removed, add the value of the coins collected by each player.
It is possible that you and your opponent end up with the same value (for
example, if all coins have the same denomination). Develop a strategy
where you take the first turn and where your final value is at least that of
your opponent (that is, don't let your opponent end up with coins worth more
than your coins).</p>
<h2><a name="Determining the number of one hat"></a>Determining the number of one hat</h2>
<p>
[This problem was told to me by Clark Barrett, who got it from his father. It may sound reminiscent of the
<a href="#Three hat colors">Three hat colors</a> problem, but it's different in many ways.]</p>
<p>
N people team up and decide on a strategy for playing this game. Then they
walk into a room. On entry to the room, each person is given a hat on
which one of the first N natural numbers is written. There may be
duplicate hat numbers. For example, for N=3, the 3 team members may get
hats labeled 2, 0, 2. Each person can see the numbers written on the
others' hats, but does not know the number written on his own hat. Every
person then simultaneously guesses the number of his own hat. What
strategy can the team follow to make sure that at least one person on the team
guesses his hat number correctly?</p>
<h2><a name="Voting on how to distribute coins"></a>Voting on how to distribute coins</h2>
[This problem was communicated to me by Sophia Drossopoulou.]<p>100 coins are to
be distributed among some number of persons, referred to by the labels A, B, C,
D, .... The distribution works as follows. The person with the
alphabetically highest label (for example, among 5 people, E) is called the <i>
chief</i>. The chief gets to propose a distribution of the coins among the
persons (for example, chief E may propose that everyone get 20 coins, or he may
propose that he get 100 coins and the others get 0 coins). Everyone
(including the chief) gets to vote yes/no on the proposed distribution. If
the majority vote is yes, then thats the final distribution. If theres a
tie (which there could be if the number of persons is even), then the chief gets
to break the tie. If the majority vote is no, then the chief gets 0 coins
and has to leave the game, the person with the alphabetically next-highest name
becomes the new chief, and the process to distribute the 100 coins is repeated
among the persons that remain. Suppose there are 5 persons and that every
person wants to maximize the number of coins that are distributed to them.
Then, what distribution should chief E propose?</p>
<p>[This problem and its solution caused my niece Sarah Brown to send me the
following
<a href="http://www.economist.com/science/displaystory.cfm?story_id=9433782">
article from The Economist</a>, which considers a human aspect of situations
like these.]</p>
<h2><a name="Subsequence of coin tosses"></a>Subsequence of coin tosses</h2>
[I got this problem from Joe Morris, who created it.]<p>Each of two players
picks a different sequence of two coin tosses. That is, each player gets
to pick among HH, HT, TH, and TT. Then, a coin is flipped repeatedly and
the first player to see his sequence appear wins. For example, if one
player picks HH, the other picks TT, and the coin produces a sequence that
starts H, T, H, T, T, then the player who picked TT wins. The coin is
biased, with H having a 2/3 probability and T having a 1/3 probability. If
you played this game, would you want to pick your sequence first or second? </p>
<h2><a name="Children and light switches"></a>Children and light switches</h2>
[I got this problem from Mariela Pavlova.]<p>A room has 100 light switches,
numbered by the positive integers 1 through 100. There are also 100
children, numbered by the positive integers 1 through 100. Initially, the
switches are all off. Each child k enters the room and changes the
position of every light switch n such that n is a multiple of k. That is,
child 1 changes all the switches, child 2 changes switches 2, 4, 6, 8,
, child
3 changes switches 3, 6, 9, 12,
, etc., and child 100 changes only light switch
100. When all the children have gone through the room, how many of the
light switches are on?</p>
<h2><a name="Finding a counterfeit coin"></a>Finding a counterfeit coin</h2>
<p>[Ernie Cohen sent me this puzzle, and I also heard it from a student who got
it from Ernie at Marktoberdorf.]</p>
<p>You have 12 coins, 11 of which are the same weight and one counterfeit coin
which has a different weight from the others. You have a balance that in
each weighing tells you whether the two sides are of equal weight, or which side
weighs more. How many weighings do you need to determine: which is
the counterfeit coin, and whether it weighs more or less than the other coins.
How?</p>
<h2><a name="Cutting cheese"></a>Cutting cheese</h2>
<p>[I got this problem many years ago, likely from Jan van de Snepscheut.]</p>
<p>You're given a 3x3x3 cube of cheese and a knife. How many straight cuts
with the knife do you need in order to divide the cheese up into 27 1x1x1 cubes?</p>
<h2><a name="Fair soccer championship"></a>Fair soccer championship</h2>
<p>[I got this question from Sergei Vorobyov.]</p>
<p>The games played in the soccer world championship form a binary tree, where
only the winner of each game moves up the tree (ignoring the initial games,
where the teams are placed into groups of 4, 2 of which of which go onto play in
the tree of games I just described). Assuming that the teams can be
totally ordered in terms of how good they are, the winner of the championship will indeed be the
best of all of the teams. However, the second best team does not
necessarily get a second place in the championship. How many additional
games need to be played in order to determine the second best team?</p>
<h2><a name="Path on the surface of the Earth"></a>Path on the surface of the Earth</h2>
<p>[I must have heard this problem ages ago, but as I remembered it, one was
always satisfied after finding just one solution. It was a math professor at
the Kaiserslautern Technical University who brought asking for <i>all</i>
solutions to my attention.]</p>
<p>Initially, you're somewhere on the surface of the Earth. You travel one
kilometer South, then one kilometer East, then one kilometer North. You
then find yourself back at the initial position. Describe <i>all</i>
initial locations from which this is possible.</p>
<h2><a name="Random point in a circle"></a>Random point in a circle</h2>
<p>[I heard this nice problem from Sumit Gulwani.]</p>
<p>You're given a procedure that with a uniform probability distribution outputs random numbers between 0 and 1 (to some
sufficiently high degree of precision, with which we need not concern ourselves in this puzzle). Using a bounded
number of calls to this procedure, construct a procedure that with a uniform
probability distribution outputs a random
point within the unit circle.</p>
<h2><a name="Mixing vinegar and oil"></a>Mixing vinegar and oil</h2>
<p>[I read this problem in a puzzle book I have.]</p>
<p>You have two jars. One contains vinegar, the other oil. The two
jars contain the same amount of their respective fluid.</p>
<p>Take a spoonful of the vinegar and transfer it to the jar of oil. Then,
take a spoonful of liquid from the oil jar and transfer it to the vinegar jar.
Stir. Now, how does the dilution of vinegar in the vinegar jar compare to the dilution
of oil in the oil jar?</p>
<h2><a name="Psycho killer"></a>Psycho killer</h2>
<p>[I got this problem from Carroll Morgan.]</p>
<p>A building has 16 rooms, arranged in a 4x4 grid. There is a door
between every pair of adjacent rooms ("adjacent" meaning north, south, west, and
east, but no diagonals). Only the room in the northeast corner has a door
that leads out of the building.</p>
<p>In the initial configuration, there is one person in each room. The
person in the southwest corner is a psycho killer. The psycho killer has
the following traits: If he enters a room where there is another person,
he immediately kills that person . But he also cannot stand the site of
blood, so he will not enter any room where there is a dead person.</p>
<p>As it happened, from that initial configuration, the psycho killer managed to
get out of the building after killing all the other 15 people. What path
did he take?</p>
<h2><a name="A special squarish age"></a>A special squarish age</h2>
<p>[Chuck Chan created this little puzzle. Greg Nelson suggested
introducing the name "squarish" in order to simplify the problem statement.]</p>
<p>Let's say that a number is <i>squarish</i> if it is the product of two consecutive
numbers. For example, 6 is squarish, because it is 2*3.<br>
<br>
A friend of mine at Microsoft recently had a birthday. He said his age is now squarish. Moreover, since the previous time his age was a squarish number, a
squarish number of years has passed. How many years would he have to wait until
his age would have this property again?</p>
<h2><a name="Passing alternating numbers of coins around"></a>Passing alternating numbers of coins around</h2>
<p>[This problem appears as a sample question on the web page for the
<a href="http://math.scu.edu/putnam/">Putnam exam</a>.]</p>
<p>A game is played as follows. N people are sitting around a table, each with
one penny. One person begins the game, takes one of his pennies (at this
time, he happens to have exactly one penny) and passes it to the person to his
left. That second person then takes two pennies and passes them to the
next person on the left. The third person passes one penny, the fourth
passes two, and so on, alternating passing one and two pennies to the next
person. Whenever a person runs out of pennies, he is out of the game and has to
leave the table. The game then continues with the remaining people.<br>
<br>
A game is <i>terminating</i> if and only if it ends with just one person sitting
at the table (holding all N pennies). Show that there exists an infinite
set of numbers for which the game is terminating.</p>
<h2><a name="The exact batting average"></a>The exact batting average</h2>
<p>[I heard this problem from Bertrand Meyer, who had heard it was once given on
the Putnam exam.]</p>
<p>At some point during a baseball season, a player has a batting average of
less than 80%. Later during the season, his average exceeds 80%.
Prove that at some point, his batting average was exactly 80%.</p>
<p>Also, for which numbers other than 80% does this property hold?</p>
<h2><a name="Summing pairs of numbers to primes"></a>Summing pairs of numbers to primes</h2>
<p>[I got this problem from Jay Misra, who got it from Gerard Huet.]</p>
<p>For any even number N, partition the integers from 1 to N into pairs such
that the sum of the two numbers in each pair is a prime number.</p>
<p>Hint: Chebyshev proved that the following property (Bertrand's
Postulate) holds: for any k > 1, there exists a prime number p in the
range k < p < 2*k.</p>
<h2><a name="Right triangle with a 23"></a>Right triangle with a 23</h2>
<p>[Madan Musuvathi asked me this question.]</p>
<p>Find two positive integers that together with 23 are the lengths of a right
triangle.</p>
<p>[Madan first told me 17, which I could solve right away, because I had just
finished reading Mark Haddon's novel <em>The curious incident of the dog in the
night-time</em>, which toward the end mentions that a triangle with sides
n<sup>2</sup>+1, n<sup>2</sup>-1,
and 2*n, where n>1, is a right triangle. Madan then asked me about 23.]</p>
<p>[A follow-up question.]</p>
<p>There's a simple technique
that, given any odd positive integer, allows you to figure out the other two
integer sides of a right triangle in your head (or with pen and paper if the
numbers get too large). Find this technique.</p>
<p>Hint: Think of every
number as a multiset of prime factors, so that multiplying the prime factors
gives you the number. Move one of the addends of the Pythagorean Theorem
to the other side and factor it (a technique I recently learned from Raymond Boute).</p>
<h2><a name="The worm and the rubber band"></a>The worm and the rubber band</h2>
<p>[Jay Misra told me this problem.]</p>
<p>A rubber band (well, a rubber string, really) is 10 meters long.
There's a worm that starts at one end and crawls toward the other end, at a
speed of 1 meter per hour. After each hour that passes, the rubber string
is stretched so as to become 1 meter longer than it just was. Will the
worm ever reach the other end of the string?</p>
<h2><a name="Placing coins on a table"></a>Placing coins on a table</h2>
<p>[I got this problem from Amit Rao.]</p>
<p>Two players are playing a game. The game board is a circular table.
The players have access to an ample supply of equal-sized circular coins. The
players alternate turns, with each turn adding a single coin to the table.
The coins are not allowed to overlap. Once a coin is placed on the table,
it is not allowed to be moved. The player who has no place to put his next coin
loses. Develop a winning strategy for the player who starts. (The
table is large enough to accommodate at least one coin.)</p>
<h2><a name="Determining a hidden digit"></a>Determining a hidden digit</h2>
<p>[I got this problem from Olean Brown, who had pointed me to the following web
page that claims to <a href="http://digicc.com/fido/">read your mind</a>.]</p>
<p>Think of a positive integer, call it X. Shuffle the decimal digits of
X, call the resulting number Y. Subtract the smaller of X,Y from the
larger, call the difference D. D has the following property: Any
non-zero decimal digit of D can be determined from the remaining digits.
That is, if you ask someone to hide any one of the non-zero digits in the
decimal representation of D, then you can try to impress the other person by
figuring out the hidden digit from the remaining digits. How is this done?
Why does it work?</p>
<h2><a name="Boris and Natasha"></a>Boris and Natasha</h2>
<p>[I got this problem from Todd Proebsting.]</p>
<p>Boris and Natasha live in different cities in a country with a corrupt postal
service. Every box sent by mail is opened by the postal service, the
contents stolen, and the box never delivered. <i>Except</i>: if the box is
locked, then the postal service won't bother trying to open it (since there are
so many other boxes whose contents are so much easier to steal) and the box is
delivered unharmed.</p>
<p>Boris and Natasha each has a large supply of boxes of different sizes, each
capable of being locked by padlocks. Also, Boris and Natasha each has a
large supply of padlocks with matching keys. The padlocks have unique
keys. Finally, Boris has a ring that he would like to send to Natasha.
How can Boris send the ring to Natasha so that she can wear it (without either
of them destroying any locks or boxes)?</p>
<h2><a name="Burning ropes to measure time"></a>Burning ropes to measure time</h2>
<p>[I first got this problem from Ernie Cohen. Apparently, it has appeared
as a <a href="http://cartalk.cars.com/content/puzzler/">Car Talk
Puzzler</a>, but I've been unable to find it on their web site.]</p>
<p>Warm-up: You are given a box of matches and a piece of rope. The
rope burns at the rate of one rope per hour, but it may not burn uniformly.
For example, if you light the rope at one end, it will take exactly 60 minutes
before the entire rope has burnt up, but it may be that the first 1/10 of the
rope takes 50 minutes to burn and that the remaining 9/10 of the rope takes only
10 minutes to burn. How can you measure a period of exactly 30 minutes?
You can choose the starting time. More precisely, given the matches and
the rope, you are to say the words "start" and "done" exactly 30 minutes apart.</p>
<p>The actual problem: Given a box of matches and two such ropes, not
necessarily identical, measure a period of 15 minutes.</p>
<h2><a name="Flipping cards"></a>Flipping cards</h2>
<p>[I have heard several versions of this problem. I first heard it from
Bertrand Meyer, who got the problem from Yuri Gurevich.]</p>
<p>You're given a regular deck of 52 playing cards. In the pile you're
given, 13 cards face up and the rest face down. You are to separate the
given cards into two piles, such that the number of face-up cards in each pile
is the same. In separating the cards, you're allowed to flip cards over.
The catch: you have to do this in a dark room where you cannot determine
whether a card is face up or face down.</p>
<h2><a name="Three hat colors"></a>Three hat colors</h2>
<p>[I think I got this puzzle from Lyle Ramshaw, who I think got it from some
collection of problems or maybe the American Mathematical Monthly.]</p>
<p>A team of three people decide on a strategy for playing the following game.
Each player walks into a room. On the way in, a fair coin is tossed for
each player, deciding that player's hat color, either red or blue. Each
player can see the hat colors of the other two players, but cannot see her own
hat color. After inspecting each other's hat colors, each player decides
on a response, one of: "I have a red hat", "I had a blue hat", or "I pass".
The responses are recorded, but the responses are not shared until every player
has recorded her response. The team <i>wins</i> if at least one player
responds with a color and every color response correctly describes the hat color
of the player making the response. In other words, the team <i>loses</i>
if either everyone responds with "I pass" or someone responds with a color that
is different from her hat color.</p>
<p>What strategy should one use to maximize the team's expected chance of
winning?</p>
<p>For example, one possible strategy is to single out one of the three players.
This player will respond "I have a red hat" and the others will respond "I
pass". The expected chance of winning with this strategy is 50%. Can
you do better? Provide a better strategy or prove that no better strategy
exists.</p>
<p>[Here's a related problem, which I got from Jim Saxe.]</p>
<p>In this variation, the responses are different. Instead of "red",
"blue", "pass", a response is now an integer, indicating a bet on having the hat
color red. Once the responses have been collected, the team's <i>score</i>
is calculated as follows: Add the integer responses for those players
wearing red hats, and subtract from that the integers of those players wearing
blue hats. For example, if the three players respond with 12, -2, -100
while wearing blue, red, blue, respectively, then the team's score is (-2) -
(12) - (-100) = 90. The team wins if and only if its score is strictly
positive.</p>
<p>For example, any strategy used in the first game can be used with this second
game by replacing "I have a red hat" with 1, "I have a blue hat" with -1, and "I
pass with 0". Such a strategy wins anytime the strategy would have
produced a win in the first game; plus, this strategy may win in some cases
where the strategy would not produce a win in the first game. For example,
for hat colors red, red, red, the strategy "red", "red", "blue" loses in the
first game, whereas 1, 1, -1 still wins in the second game. Hence, playing
this second game can only increase the team's expected chance of winning.</p>
<p>[Further generalizations.]</p>
<p>Of course, you can generalize these two problems from 3 players to N players.
The solution to the first problem with N players may require more mathematical
sophistication than the solution to the second problem with N players.</p>
<h2><a name="The line of persons with hats"></a>The line of persons with hats</h2>
<p>[Ernie Cohen told me this problem.]</p>
<p>100 persons are standing in line, each facing the same way. Each person
is wearing a hat, either red or blue, but the hat color is not known to the
person wearing the hat. In fact, a person knows the hat color only of
those persons standing ahead of him in line.</p>
<p>Starting from the back of the line (that is, with the person who can see the
hat colors of all of other 99 persons), in order, and ending with the person at
the head of the line (that is, with the person who can see the hat color of no
one), each person exclaims either "red" or "blue". These exclamations can
be heard by all. Once everyone has spoken, a <i>score</i> is calculated,
equal to the number of persons whose exclamation accurately describes their own
hat color.</p>
<p>What strategy should the 100 persons use in order to get as high a score as
possible, regardless of how the hat colors are assigned? (That is, what
strategy achieves the best worst-case score?)</p>
<p>For example, if everyone exclaims "red", the worst-case score is 0. If
the first 99 persons exclaim the color of the hat of the person at the head of
the line and the person at the head of the line then exclaims the color he has
heard, the worst-case score is 1. If every other person exclaims the hat
color of the person immediate in front and that person then repeats the color he
has just heard, then the worst-case score is 50. Can you do better?</p>
<p>[Here's a generalization of the problem.]</p>
<p>Instead of using just red and blue as the possible hat colors and
exclamations, use N different colors.</p>
<h2><a name="The prisoners and the switch"></a>The prisoners and the switch</h2>
<p>[Tom Ball told me (a close variation of) this problem. The problem has
been featured as a <a href="http://cartalk.cars.com/content/puzzler/">Car Talk
Puzzler</a> under the name
<a href="http://cartalk.cars.com/content/puzzler/transcripts/200307/answer.html">Prison Switcharoo</a> (beware: the Car Talk problem page also contains an
answer).]</p>
<p>N prisoners get together to decide on a strategy. Then, each prisoner
is taken to his own isolated cell. A prison guard goes to a cell and takes
its prisoner to a room where there is a switch. The switch can either be
up or down. The prisoner is allowed to inspect the state of the switch and
then has the option of flicking the switch. The prisoner is then taken
back to his cell. The prison guard repeats this process infinitely often,
each time choosing fairly among the prisoners. That is, the prison guard
will choose each prisoner infinitely often.</p>
<p>At any time, any prisoner can exclaim "Now, every prisoner has been in the
room with the switch". If, at that time, the statement is correct, all
prisoners are set free; if the statement is not correct, all prisoners are
immediately executed. What strategy should the prisoners use to ensure
their eventual freedom?</p>
<p>(Just in case there's any confusion: The initial state of the switch is
unknown to the prisoners. The state of the switch is changed only by the
prisoners.)</p>
<p>As a warm-up, you may consider the same problem but with a known initial
state of the switch.</p>
<h2><a name="Table with four coins"></a>Table with four coins</h2>
<p>[This problem has crossed the desk of Jan van de Snepscheut, but it may have
been due to someone else.]</p>
<p>A square table has a coin at each corner. Design an execution sequence,
each of whose steps consists of one of the following operations:</p>
<ul>