PAST PIZZA PROBLEMS

BLOCK 8, 2008

For Non-Majors:

A man wanted to get into his work building, but he had forgotten his code. However, he did remember five clues.

These are what those clues were:

The fifth number plus the third number equals fourteen.

The fourth number is one more than the second number.

The first number is one less than twice the second number.

The second number plus the third number equals ten.

The sum of all five numbers is 30.

What were the five numbers and in what order?

Answer:

 

For Majors:

There are 4 mathematicians - Marlow, Fred, Stefan and Amelia - having lunch in a hotel. Suddenly, Marlow thinks of 2 distinct integer numbers greater than 1 and says, "The sum of the numbers is..." and he whispers the sum to Fred. Then he says, "The product of the numbers is..." and he whispers the product to Stefan. After that, the following conversation takes place:

Fred : Stefan, I don't think that we know the numbers.
Stefan : Fred, you're always the pessimist. Now I know the numbers.
Fred : Oh, now I also know the numbers.
Stefan: It's about time. Amelia? Are you on this boat?
Amelia : Now I also know the numbers.

How did they know the numbers?

 

Answer:

---

BLOCK 7, 2008

For Non-Majors:

Once upon a time, and old lady went to sell her vast quantity of eggs at the local market.

When asked how many she had, she replied:

If you divide the number of eggs by 2 there will be one egg left.
If you divide the number of eggs by 3 there will be one egg left.
If you divide the number of eggs by 4 there will be one egg left.
If you divide the number of eggs by 5 there will be one egg left.
If you divide the number of eggs by 6 there will be one egg left.
If you divide the number of eggs by 7 there will be one egg left.
If you divide the number of eggs by 8 there will be one egg left.
If you divide the number of eggs by 9 there will be one egg left.
If you divide the number of eggs by 10 there will be one egg left.

Finally. If you divide the Number of eggs by 11 there will be NO EGGS left!

How many eggs did the old lady have?

Answer:

25,201 eggs. This puzzle has a few different methods for finding the solution, one of which is:

Find a number X into which all of the numbers from 2 to 10 divide evenly. You can do this by simply using 2*3*4*5*6*7*8*9*10, but you can find a smaller number by finding the prime factors, a subset of which can be used to form any number from 2 to 10. 2*2*2*3*3*5*7 will do. This comes out to be 2520, and is the lowest number into which all the numbers 2-10 divide evenly. We can add 1 to this number to satisfy the first 9 constraints of the puzzle (the remainder of 2521/2, 2521/3 ... 2521/10 is one), but this does not satisfy the last constraint, divisibility by 11. Fortunately, we can multiply X (=2520) by any integer and add 1 and we will still satisfy constraints 1-9. So what Y do we multiply X by so that (X*Y) + 1 is divisible by 11. 2520/11 has a remainder of 1. Thus two 2520s divided by eleven would have a remainder of 1+1 = 2, and so forth...so ten 2520s divided by 11 would have a remainder of 10. This number plus one would divide eleven evenly, as well as also satisfy the first 9 constraints - thus 25201 is the answer.

For Majors:

What number comes next in this sequence:
1/1
3/2
7/5
17/12
41/29
… ?

Answer:
99/70: each successive term better approximates the square root of two and is formed as (a + 2b) / (a + b).

BLOCK 6, 2008

For Majors:

Let and , for > 0

Determine .

Answer: Since , one can show by induction that

    so  

Congrats to Leon for getting the correct answer!

For NON-Majors:

About 2000 B. C. there lived Ahmes, a royal secretary and mathematician of the Pharaoh Amenemhat III. In 1853 an Englishman Rhind found one of Ahmes's papyruses near the temple of Ramses II. in Thebes. The papyrus is a rectangle 33 cm wide and about 5 m long. There is the following math brain teaser on it (besides others): 100 measures of corn must be divided among 5 workers, so that the second worker gets as many measures more than the first worker, as the third gets more than the second, the fourth more than the third and the fifth more than the fourth. The first two workers shall get seven times less measures of corn than the three others. Assuming a measure of corn is able to be divided into smaller portions, how many measures of corn shall each worker get?
Answer: 1st worker = 10/6 measures of corn; 2nd worker = 65/6 measures of corn; 3rd worker = 120/6 (20) measures of corn; 4th worker = 175/6 measures of corn; 5th worker = 230/6 measures of corn

BLOCK 5, 2008

Math Majors:

ANSWER:

You have 12 stones that all look the same. Inside one of the stones is a diamond. The stone with the diamond is either heavier or lighter than the other 11 stones. You have three balancing scales that have signs that say “One use only”. How do you find out which stone has the diamond and whether or not the stone is heavier or lighter than the other stones with only three weighings total?

For simplicity's sake, we will refer to one side of the scale as Side A, and the other as Side B.

Step 1: Weigh four balls against four others.

Case A: If, on the first weighing, the balls balance
If the balls in our first weighing balance we know the odd ball is one of those not weighed, but we don't know whether it is heavy or light. How can we gain this information easily? We can weigh them against the balls we know to be normal. So:

Step 2 (for Case A): Put three of the unweighed balls on the Side A; put three balls that are known to be normal on Side B.

I. If on this second weighing, the scale balances again, we know that the final unweighed ball is the odd one.

Step 3a (for Case A): Weigh the final unweighed ball (the odd one) against one of the normal balls. With this weighing, we determine whether the odd ball is heavy or light.

II. If on this second weighing, the scale tips to Side A, we know that the odd ball is heavy. (If it tips to Side B, we know the odd ball is light, but let's proceed with the assumption that the odd ball is heavy.) We also know that the odd ball is one of the group of three on Side A.

Step 3b (for Case A): Weigh one of the balls from the group of three against another one. If the scale balances, the ball from the group of three that was unweighed is the odd ball, and is heavy. If the scale tilts, we can identify the odd ball, because we know it is heavier than the other. (If the scale had tipped to Side B, we would use the same logical process, using the knowledge that the odd ball is light.)

Case B: If the balls do not balance on the first weighing
If the balls do not balance on the first weighing, we know that the odd ball is one of the eight balls that was weighed. We also know that the group of four unweighed balls are normal, and that one of the sides, let's say Side A, is heavier than the other (although we don't know whether the odd ball is heavy or light).

Step 2 (for Case B): Take three balls from the unweighed group and use them to replace three balls on Side A (the heavy side). Take the three balls from Side A and use them to replace three balls on Side B (which are removed from the scale).

I. If the scale balances, we know that one of the balls removed from the scale was the odd one. In this case, we know that the ball is also light. We can proceed with the third weighing as described in step 3b from Case A.

II. If the scale tilts to the other side, so that Side B is now the heavy side, we know that one of the three balls moved from Side A to Side B is the odd ball, and that it is heavy. We proceed with the third weighing as described in step 3b in Case A.

III. If the scale remains the same, we know that one of the two balls on the scale that was not shifted in our second weighing is the odd ball. We also know that the unmoved ball from Side A is heavier than the unmoved ball on Side B (though we don't know whether the odd ball is heavy or light).

Step 3 (for Case B): Weigh the ball from Side A against a normal ball. If the scale balances, the ball from Side B is the odd one, and is light. If the scale does not balance, the ball from Side A is the odd one, and is heavy.

Non-Majors:

ANSWER:
You have 12 stones that all look the same. Inside one of the stones is a diamond. The stone with the diamond is heavier than the other 11 stones. You have three balancing scales that have signs that say “One use only”. How do you find out which stone has the diamond with only three weighings total?

Since we know the Diamond is heavier, we split the stones into groups of 6. Then weigh 6 stones on each side of the scale. Whichever side is heavier has the diamond. Then we split that group of 6 into two groups of 3 and put those on each side of the scale. Again, the heavier side has the diamond. We take those three and pick two random stones and place those on the scale for the final weighing. If those two are the same weight, then we know the third stone we did not weigh has the diamond. If one of the two stones is heavier than the other, then we know that the heavier stone has the diamond.

 

---

BLOCK 4 2007

Math Majors:

In the center of this figure is a circle with radius one. Circumscribed about it is an equilateral triangle. Circumscribed around that is a circle. And circumscribed about that is a square. Circumscribed about that is another circle. About that circle a pentagon is circumscribed. And so forth, with circles alternating with regular polygons with more and more sides adinfinitum. What is the limit of the radii of the circles?



ANSWER in PDF : CLICK HERE

Non Math Majors:

You have two very hungry termites and two sticks of wood. One stick of wood is 12 inches long and the other is 16 inches long. One termite can eat sticks at the rate of one inch every 3 minutes. The other termite can eat one inch in 4 minutes. How would you use the termites and sticks to measure 61 minutes?

ANSWER: Start the slow termite eating the longer stick. It will take the slow termite 16 minutes to eat the 4 inches that will make the sticks the same size. When the sticks are the same size, start the fast termite on the other stick. This termite will finish his 12 inch stick in 36 minutes. That's 52 minutes elapsed so far and the slow termite still has 3 inches left on his stick. Remove the slow termite and let the fast termite finish off the 3 inches in 9 minutes for a total of 61 minutes.

---

BLOCK 3 2007

Math Majors:

Before the question can be answered, we need to define a term. Let's say we have the five numbers 10, 20, 30, 40, 50. The total distance to a point, say 22, is

(22-10) + (22-20) + (30-22) + (40-22) + (50-22)

Mathematically, the total distance from x to a set of numbers is the sum of the absolute values of the differences between each number and x.

Stefan: "There are 17 numbers that are not all distinct (different). Their minimum is 30, their mean is 34, and their median is 35. And I like grapes."

Marlow: "What is their total distance to 35?"

Stefan: "I won't tell you, but the total distance to 35 is 5 less than the total distance to 38. Whoops! I shouldn't have told you that."

Marlow: "You're right. Silly Stefan. Now I know the numbers! Mwahahahaha…. No grapes for you!"

What are the 17 integers??

(As a side note, I, Lauren Bose, actually solved this problem, so it's not impossible.)

ANSWER: Before the question can be answered, we need to define a term. Let's say we have the five numbers 10, 20, 30, 40, 50. The total distance to a point, say 22, is

(22-10) + (22-20) + (30-22) + (40-22) + (50-22)

Mathematically, the total distance from x to a set of numbers is the sum of the absolute values of the differences between each number and x.

There are 17 numbers that are not all distinct (different). Their minimum is 30, their mean is 34, and their median is 35. The total distance to 35 is 5 less than the total distance to 38.

What are the 17 integers??

30, 30, 30, 30, 30, 30, 30, 30, 35, 37, 38, 38, 38, 38, 38, 38, 38

For Non-Majors:

Amelia: "I have five integers that may or may not be distinct (different)."

Jane: "What is the minimum (smallest number)?"

Amelia: "20."

Jane: "Which of the following would not allow me to infer all of the numbers: the number that are distinct, the mean of all of the numbers, the median of all of the numbers, or the maximum (largest) of all of the numbers?

Amelia: "Only the median."

Jane: "Great! Now I know the numbers!"

What are the five numbers??

ANSWER: I have five integers that may or may not be distinct (different). The minimum (smallest number) is 20.

"Which of the following would not allow me to infer all of the numbers: the number that are distinct, the mean of all of the numbers, the median of all of the numbers, or the maximum (largest) of all of the numbers?"

Only the median.

What are the five numbers??

20, 20, 20, 20, 20

For Computer Science Majors:

Write a program that would print the integers up to n^2 in this type of a spiral:

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

Now, whenever there is a prime, put an asterisk:

*   16   15   14  *
18   *   4     *   12
*    6    *    *     *
20    *   8   9  10
21   22   *   …

 

---

BLOCK 2 2007

Computer Science Majors:

This is a problem about betting. Each bet works as follows. There are some number of "advisors" and you. One advisor will write either 1 or 0 on a piece of paper, show it to the other advisors but not to you, and put the paper face down in front of you. Each advisor will tell you what the number is. They are all very good actors, so no obvious trick or facial expression will reveal to you who is telling the truth and who is not. The amount you can wager on each bet is anything from $0 to the total amount of money you have.

You have four bets, but there is a "partial truth teller". That advisor is not guaranteed to tell the truth all the time, but must do so three out of four times. Further, the advisors can actually change the number on the paper once they hear your bet. However, they cannot change the result if doing so would eliminate the possibility that at least one of them is a partial truth telling advisor.

What can you guarantee to win in four bets, starting with $100, with four advisors, three of whom can lie at will, and one who must tell the truth at least three out of four times?

Math Majors:
coming soon

Non-Majors:
coming soon

---

BLOCK 1 2007

Problem/Solution in PDF
Congratulations to Leon for getting the correct answer!

BLOCK 5, 2007

Pizza Problem for Non-Majors

Every day, a father drives to pick up his son after school. The route is easy, and the dad has it timed so well that he always arrives at the exact instant that school lets out. The boy wastes no time in hopping in the car, and they turn around and drive home.

One day, school lets out an hour early. The boy wishes to save his father some time, so he starts walking home from school along the same route the father will take. On his way to the school, the father sees the son on the side of the road. The boy gets in the car, and they turn around and drive home. To their delight, they arrive home 20 minutes early.

How long was the boy walking?

Pizza Problem for Majors

In an LCD display some numbers, when viewed upside-down, are imaged of the other numbers.  For example, 1995 becomes 5661.  The fifth number that can be read upside-down is 8, and the 15^th is 21, which is 12 when viewed up-side down.  What is the millionth number that is meaningful upside-down?

Notes: An LCD numeral is obtained by filling out some of the 7 lines in the figure below:

--

|  |

--

|  |

--

0: All but central hyphen

1: The two right-hand verticals (when flipped, the two left-hand verticals are filled; this is still considered 1 when read upside down)

8: All

    --      

   |  |         |

0:         1:        

   |  |         |

    --

    --        --    

      |         |     |  |

2:  --    3:  --   4:  --

   |            |        |

    --        --

    --        --       --

   |         |        |  |

5:  --    6:  --   7:

      |      |  |        |

    --        --

    --        --

   |  |      |  |

8:  --    9:  --

   |  |         |

--        --

BLOCK 2

Problem 2

(intended for math majors)

Juliet is in love with Romeo, who happens (in our version of the story) to be a fickle lover. The more Juliet loves him, the more he begins to dislike her. When she hates him, his feelings for her warm up. On the other hand, her love for him grows when he loves her and withers when he hates her. A model for this ill-fated romance is

dj/dt = Ar
dr/dt = -Bj,

where A and B are positive constants, r(t) represents Romeo's love for Juliet, and j(t) represents Juliet's love for Romeo at time t. (Negative love represents hate.)

a) The constant on the right hand side of Juliet's equation (dj/dt) has a positive sign, while the constant in Romeo's equation is negative. Explain why this follows from the story.

b) Derive a second-order differential equation for r(t) and solve it. (Your equation should involve r and its derivatives, but not j and its derivatives.)

c) Express r(t) and j(t) as functions of t, given r(0)=1 and j(0)=0. Your answer will contain A and B.

d) As you may have discovered, the outcome of the relationship is a never-ending cycle of love and hate. Find what fraction of the time they both love each other.

BLOCK 1

Using four 4's and any operations, try to write equations that have the numbers from 0 to 100 as the answer.

Examples:

4*4-4*4 = 16-16 =0
(4+4)/(4+4) = 1
4*4/(4+4) = 16/8 = 2

Submit answers to Courtney or Benjamin in Tutt Sci 210 or email answers to mathcsparaprof@coloradocollege.edu

Problem 2 (for Math majors)

For each rational number x, write x as p/q where p, q are integers with no common factors and q > 0, and then define f(x) = 1/q. Also, define f(x) = 0 for all irrational x. Thus f(x) = 1 for each integer, f(1/2) = f(-1/2) = f(3/2) = ... = 1/2, etc. Show that f is continuous at each irrational point and continuous at each rational point.

Submit answers to Courtney in Tutt Sci 210 or email answer to courtney.gibbons@coloradocollege.edu

BLOCK 4 2005 Problems

Problem #1
A highly divisible number

What is the smallest positive whole number that consists of the ten digits 0 through 9, each used just once, and is divisible by each of the digits 2 through 9.

Problem #2
Boolean Rings

A ring A is Boolean if x.x = x for all x in A. In a Boolean ring A, show that:

1.2x = 0 for all x in A
2.every ideal of the form <x, y>, where x and y are in A, is a principal ideal.

Problem #3
Roommate Selection

Each year, the Southern North Shangri La College must pair students who choose to live on campus. The College asks each student for her roommate preferences as an ordered list of up to four other students. The College would like to pair students to minimize the following sum:

each student who is matched with her first choice contributes 1 point,
each student who is matched with her second choice contributes 2 points,
each student who is matched with her third choice contributes 4 points,
each student who is matched with her fourth choice contributes 6 points,
each student who is matched with any other student contributes 12 points,
only one student may have a single-occupancy room, and that student does not contribute to the sum.


Your task is to write a program that attempts to minimize the matching score above.

Input

Your program should take as input lines containing up to five student user names.

Output

Your program should output lines containing roommate pairs. All students must be matched, unless there are an odd number of students, in which case only one student can remain unmatched. Each student may only be matched with one roommate.

Sample Input
a_dork q_tee u_duman g_whiz o_bequiet
c_dragon i_wanttolivealon o_bequiet
b_nice q_tee l_hombre d_dodah u_duman
d_dodah g_whiz b_nice q_tee u_duman
g_whiz a_dork i_wanttolivealone o_bequiet b_nice
i_wanttolivealone
l_hombre u_duman ru_sleepy b_nice q_tee
o_bequiet a_dork i_wanttolivealone
q_tee b_nice d_dodah g_whiz u_duman
r_usleepy i_wanttolivealone g_whiz o_bequiet a_dork
u_duman l_hombre ru_sleepy q_tee b_nice

Sample Output
a_dork c_dragon
b_nice d_dodah
g_whiz i_wanttolivealone
l_hombre o_bequiet
q_tee ru_sleepy
u_duman

What to Submit

Submit to Jonathan by the end of block 5, your source code to pair roommates. A prize will be awarded to the author of the program that can construct the best summed matchings for three sets of roommates selected by Jonathan. Your program must complete each matching decision in less than five minutes on a 2GHz Pentium 4 personal computer to be judged.

BLOCK 3 2005 Problems

Problem #1 (Open to All)

Sequencing Digits

How many ways are there to write the numbers 0 through 9 in a row, such that each number other than the left-most is within one of some number to the left of it?

Problem #2 (Primarily for Math majors)

Counting pigeons!

Does every set of 10 distinct numbers between 1 and 100 contain two disjoint nonempty subsets with the same sum? Prove or disprove. Hint: What do pigeons (especially ones that can count) have anything to do with the problem?

Problem #3 (Primarily for Computer Science majors)

Crypt Kicker

A common but insecure method of encrypting text is to permute the letters of the alphabet. That is, in the text, each letter of the alphabet is consistently replaced by some other letter. So as to ensure that the encryption is reversible, no two letters are replaced by the same letter.

Your task is to decrypt several encoded lines of text, assuming that each line uses a different set of replacements, and that all words in the decrypted text are from a dictionary of known words.

Input
The input consists of a line containing an integer /n/, followed by /n/ lower case words, one per line, in alphabetical order. These /n/ words comprise the dictionary of words which may appear in the decrypted text. Following the dictionary are several lines of input. Each line is encrypted as described above.

There are no more than 1000 words in the dictionary. No word exceeds
16 letters. The encrypted lines contain only lower case letters and
spaces and do not exceed 80 characters in length.

Output
Decrypt each line and print it to standard output. If there is more than
one solution, any will do. If there is no solution, replace every letter of
the alphabet by an asterisk.

Sample Input
6
and
dick
jane
puff
spot
yertle
bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

Sample Output
dick and jane and puff and spot and yertle

What to Submit
Submit to Jonathan your source code that decrypts the following
program input:
27
a
art
brown
can
cannot
challenge
computer
do
else
enough
everything
explain
how
i
is
kitchen
mathematics
not
preconceptions
science
to
understand
we
well
will
what
you
mighcih gm wnsp wh qcthkmpsct whaa hcdqrn pd hxfasgc pd s idbfqphk
skp gm huhkypngcr hamh wh td
lrvffahsa yiqm jmalihlajpeiho im pray weff lrvffahsa yiq

BLOCK 8, 2005

BLOCK 7, 2005

Can You Find the Key?
(from Which Way did the Bicycle Go? ...and other intriguing mathematical mysteries by Joseph D.E. Konhauser, Dan Velleman, and Stan Wagon)
Suppose you have n keys on a circular key chain and wish to put a colored sleeve on each key so that it is identifiable by its color alone, without reference to its shape. For some n this can be done with fewer than n colors. For example, if you have 4 keys then you can place the colors on the keys as shown in the figure. The top key is "the RED key that is across from the BLUE key"; and the leftmost key is "the RED key that is adjacent to a BLUE one": the other two are identifiable by their colors.
An identification scheme must work even if the key chain is flipped over, so one cannot sue the words "right" and "left." Let f (n) be the least number of colors necessary so that each key on a chain of n keys can be uniquely identified as explained above. Then f (1) = 1, f (2) = 2 and f (3) = 3. What is f (139)?

BLOCK 6, 2005

(from More Mathematical Puzzles of Sam Loyd
Selected and Edited by Martin Gardner)

BLOCK 5, 2005

Twelve identical-looking stones and three balance scales are on a table. Each scale is clearly labeled, "One Use Only." Embedded within one of the stones is a diamond. Eleven of the stones weigh the same, but the stone containing the jewel weighs slightly more or slightly less than the others. You are only permitted to use each balance scale once. You must find the right stone and determine whether it is heavier or lighter than the others. Explain how you determined this

BLOCK 4, 2004

Sums and Differences

25 different positive numbers were walking down the street. One number had a great idea: “What if we gave the following problem as a pizza problem to the Colorado College Math Department?

Prove that you can choose two of us
such that none of the rest of us is their
sum or difference.

(from Mathematical Puzzles: A Connoisseur's Collection, by Peter Winkler. )

THE SOLUTION:
This problem also appeared on the 5th All Soviet Union Mathematical Competition. Let the numbers be x1 < x2 <…<xn. If xn is unavailable to be taken as one of the desired numbers, it must be that for each lower number xi, there is another xj with xi + xj = xn. Thus, the first 24 numbers are paired in such a way that xi + xn-i-1 = xn. Now consider xn-1 together with any of x2,…,xn-2 must also be paired, this time satisfying x2+i + xn-2-i = xn-1. But that leaves x(n-1)/2 paired with itself so the numbers xn-1, x(n-1)/2 solve the problem.

BLOCK 3, 2004

Three Prisoners
Three prisoners are given an unusual jail sentence. They are taken to three different jail cells, far enough away from each other so that they can't see or hear each other. At random times and in random order, the jailor comes to each of their cells, and takes them into an empty room with a switch on the wall. The switch controls nothing, and has two positions, up or down. At the beginning of their sentence, the switch is in an unknown position. When a prisoner is in the room, he may choose to switch the switch or leave it the way it is, after which he is returned to his cell. This continues indefinitely, with the jailor visiting each prisoner many times, possibly visiting one of them many times in succession, or each in turn. At any time, a prisoner may bang on the bars of his cell, and announce to the jailor that all three prisoners have been in the room. If he is right, all three are released. If he is wrong, all three are executed.

At the beginning of this sentence, the prisoners are explained the rules and have some time to confer on a strategy before they get taken to their cells. What strategy can they use to ensure their eventual release?

THE SOLUTION:
If two prisoners flip the switch up and the third switches it down, then the third prisoner will be able to determine when each of the prisoners have been in the room. The first two prisoners will flip the switch up if it is already down, or will not touch it if it is already up. After flipping it up twice, the first two prisoners will no longer touch the switch. Once the third prisoner has seen the switch in the "up" position four times, he knows that the other two prisoners had each been in the room.
Note: If he only sees it up three times, both other prisoners may not have already been in the room. If the switch started in the "up" position and one prisoner entered the room twice, it is possible that the third prisoner saw it up three times before the second prisoner was taken to the room.

-------

BLOCK 2, 2004

(From Cliff Corzatt, St. Olaf College)

Forty Thieves
Forty thieves have acquired a large pile of gold coins by nefarious means. They agree to divide up the pile according to the following plan: Thief #1 chooses how the coins are divided. All forty thieves then vote on whether they like the distribution of gold. If at least half of the thieves vote for the distribution, they use it, otherwise, they kill thief #1 and pass the responsibility on to thief #2. They then repeat until some distribution is accepted (if necessary, when there is only one thief left).
Thief #1 wants the maximum amount of gold without getting killed. What gold distribution should he propose to make this happen? Assume all of the thieves are intelligent, forward-thinking, and good at mathematics.

THE SOLUTION:
First consider the problem with only the two thieves #39 and #40 left. Since thief #39 can vote for himself, thief #40 has no influence on the vote. So thief #39 is free to take all the gold, and thief #40 gets nothing. Thief #39 wins the vote 1-1.

Now consider the case where there are three thieves left, #38, #39, and #40. Thief #40 knows that if thief #38 gets killed, he will be left with nothing, by the analysis above. Therefore since he is intelligent and forward-thinking, he will vote for any gold distribution in which he gets more than nothing. Therefore thief #38 can give thief #40 1 gold piece and keep the rest for himself. He wins the vote 2-1.

Now suppose there are four thieves left, thieves #37-40. Thief #39 knows that if thief #37 gets killed, he will recieve nothing, by the analysis above. Therefore thief #37 can give thief #39 1 gold piece, and keep the rest for himself. He wins the vote 2-2.

Now suppose there are five thieves left. By the same analysis, thief #36 gives thief #38 and #40 1 gold piece each, and they will both vote for him. Thief #36 wins the vote 3-2.

Now we can trace all the way back to the first thief. His optimal strategy is to give 1 gold piece to thieves #3, #5, #7, ..., #39. He wins the vote 20-20, and gets all but 19 pieces of gold.

-------

BLOCK 1, 2004

Saving Time

Every day, a father drives to pick up his kid after school. The route is easy, and the dad has it timed so well that he always arrives at the exact instant that school lets out. The kid wastes no time in hopping in the car, and they turn around and drive home.
One day, school lets out an hour early. The kid wishes to save his dad some time, and starts walking home from school along the route the father will take. On his way to the school, the father sees his kid on the side of the road. The kid gets in the car, and they turn around and drive home. To their delight, they arrive home 20 minutes early.
How long was the kid walking?

THE SOLUTION:
Call the point on the road at which the dad and kid meet the "meeting point." Since they arrive home 20 minutes early, they meet each other at the meeting point 20 minutes early, since it takes them the same time to get home from there as it usually would. Therefore the dad arrives at the meeting point 20 minutes earlier than he usually does, and so it would normally take him exactly 20 minutes to drive from there to the school and back. Therefore it would normally take him exactly 10 minutes to drive to the school, and since he is planning to get there exactly when school lets out, he arrives at the meeting point 10 minutes before school lets out. Therefore the kid has been walking for 50 minutes.