After talking a bit about general proof techniques--induction, contradiction, pigeon-hole principle, and ``how to prove that something can't possibly work''--we divided into two teams and a jury, and worked on the problems below. (The teams on their own, the jury with my assistance.) During the second hour of the session, the teams took turns challenging each other to present solutions at the board. Everyone did extremely well, and the contest ended in a draw... although problems 3 and 6 did give people a little trouble.

Anyone who wants to know the solution to a problem should feel free to email me (mira@math.berkeley.edu) and ask. Remember, the topics are induction, pigeon-hole principle, and proving something can't be done. Good luck!

The Problems:

1. What is the maximal number of regions into which planes can divide (3-dimensional) space.

2. 100 spiders are crawling on a table shaped like an equilateral triangle, 3 meters per side. Prove that somewhere on the table there are 12 spiders all within 1 meter of each other.

3. On a certain island live vampires. Usually they survive on the blood of bats and rabbits, but all of them dream of one day getting their hands on the ultimate vampire delicacy--a human. When a human gets attacked, he does not turn into a vampire; he simply dies. Because of the vampires' extravagant appetite, humans are quickly going extinct on the island. Today, there are only humans left; very soon, there will be none.

   The leader of the humans, determined to save her people, decides to seek the help of a powerful wizard. The wizard gathers all the vampires on the island, and decrees: from now on, any vampire who attacks a human will wake up the next morning to find that he has turned into a human himself! The vampires are taken aback: in principle, none of them minds becoming a human (they're kind of sick of their nocturnal existence), but of course survival comes first: whenever there's even a small chance of ending up as someone else's dinner, every one of them would rather stick to rabbits!

   Is the wizard's spell going to help the humans? What is going to happen now to the vampire and human populations of the island?

   (Assume that the vampires never cooperate and never share food, so a single human can only cause one vampire's transformation. Assume too that whenever a human gets attacked, all the vampires know about it immediately.)

4. Three witches are hovering over Berkeley, always keeping at the same height. At every instant, only one of them can move; she can go as far as she wants, but only in a direction parallel to the line connecting her two sisters. If the first witch starts out directly over Evans hall, the second 2 miles north, and the third 4 miles east, is it possible that after some time they will end up with the first witch again over Evans, the second one 3 miles northeast, and the third 3 miles southeast?

5. 10 married couples show up at a Hallowe'en party. Handshakes are exchanged as they greet each other--but of course, a husband and wife don't need to shake each other's hands. At the end of the party, one woman goes around asking everyone how many hands they shook that evening, and gets all different answers. How many hands did her husband shake?

6. Every day in November, a Math Circle student undertakes to solve at least one math problem. She hopes that sometimes she'll have time for more, but knows she couldn't possibly do more than 13 problems in 7 days. Prove that there is guaranteed to be a stretch of some number of consecutive days during which she solves exactly 20 problems.

7. As you probably know, a chess knight moves in an ``L'' shape: 1 square in one direction and then 2 squares in a perpendicular direction. What you probably don't know is that he is actually chasing an -dragon, a creature that moves 1 square in one direction and then in a perpendicular direction. On an infinite chessboard, which (if any) -dragons can go from any square to any other square, and which (if any) cannot?