An eccentric billionaire has a published a devilish math problem that she wants to see solved. Her challenge is to three-color a specific map that she likes — that is, to color its regions with only three colors while ensuring that no bordering regions are the same color. Being an eccentric billionaire, she offers 10 million dollars to anyone who can present her with a solution.
You come up with a solution to this math problem! However, being a poor college student, you cannot come up with the 10,000 dollars needed to travel to the billionaire’s remote island lair. You go to your local bank and ask the manager to lend you the 10,000 dollars. You explain to him that you will soon be winning 10 million dollars, so you will easily be able to pay back the loan. But the manager is skeptical that you actually have a correct solution.
Of course, if you simply hand the manager your solution, there is nothing preventing him from throwing you out of his office and collecting the 10 million for himself. So, the question is: How do you prove to the manager that you have a solution to the problem without giving him the solution (or any part of the solution that makes it easy for him to reproduce it)?
[Solution]

## Common Grandfathers

A problem from the 1996 mathematical olympiad of the Republic of Moldova:
Twenty children attend a rural elementary school. Every two children have a grandfather in common. Prove that some grandfather has not less than 14 grandchildren in this school.
[Solution]

## Token Dollars

Ariel, Beatrice and Cassandra — three brilliant game theorists — were bored at a game theory conference (shocking, we know) and devised the following game to pass the time. They drew a number line and placed $1 on the 1, $2 on the 2, $3 on the 3 and so on to $10 on the 10.
Each player has a personalized token. They take turns — Ariel first, Beatrice second and Cassandra third — placing their tokens on one of the money stacks (only one token is allowed per space). Once the tokens are all placed, each player gets to take every stack that her token is on or is closest to. If a stack is midway between two tokens, the players split that cash.
How will this game play out? How much is it worth to go first?
A grab bag of extra credits: What if the game were played not on a number line but on a clock, with values of $1 to $12? What if Desdemona, Eleanor and so on joined the original game? What if the tokens could be placed anywhere on the number line, not just the stacks?
[Solution]

## Rug Rejection

A manufacturer, Riddler Rugs™, produces a random-pattern rug by sewing 1-inch-square pieces of fabric together. The final rugs are 100 inches by 100 inches, and the 1-inch pieces come in three colors: midnight green, silver, and white. The machine randomly picks a 1-inch fabric color for each piece of a rug. Because the manufacturer wants the rugs to look random, it rejects any rug that has a 4-by-4 block of squares that are all the same color. (Its customers don’t have a great sense of the law of large numbers, or of large rugs, for that matter.)
What percentage of rugs would we expect Riddler Rugs™ to reject? How many colors should it use in the rug if it wants to manufacture a million rugs without rejecting any of them?
[Solution]

## L Divided

Say you have an “L” shape formed by two rectangles touching each other. These two rectangles could have any dimensions and they don’t have to be equal to each other in any way.
Using only a straightedge and a pencil (no rulers, protractors or compasses), how can you draw a single straight line that cuts the L into exactly two pieces of exactly equal area, no matter what the dimensions of the L are? You can draw as many lines as you want to get to the solution, but the bisector itself can only be one single straight line.
[Solution]