Island Trees

There is a single “tree” of $N$ islands, bridged together so that there is exactly one non-doubling-back path between any two islands. Each island has a $p$ chance of being destroyed today, taking its bridges with it. How many separate island-trees are expected to result? [Solution]

Street Grid

You’ve just been hired to work in a juicy middle-management role at Riddler HQ — welcome aboard! We relocated you to a tastefully appointed apartment in Riddler City, five blocks west and 10 blocks south of the office. (The streets of Riddler City, of course, are laid out in a perfect grid.) You walk to work each morning and back home each evening. Restless and inquisitive mathematician that you are, you prefer to walk a different path along the streets each time. How long can you stay in that apartment before you are forced to walk the same path twice? (Assume you don’t take paths that are longer than required, and assume beaucoup bonus points for not using your computer.) Extra credit: What if you instead took a bigger but more distant apartment, M blocks west and N blocks south of the office? [Solution]

Map Colors

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]