the eccentric billionaire and the banker

Another week, another riddler. Here is this week’s problem:

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 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 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. You explain to him that you will soon be winning $10 million, 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)?

Oh boy, okay so here is how I do it. First, we look at the map and number it:

riddler1.jpg

Next, you and the banker come up with a contiguous path through the regions that goes through all the boarders that a region has (repeating is okay):

riddler6.jpg

Now look at the order of regions this creates (starting/ending at the green arrow):

1, 2, 5, 3, 5, 2, 3, 4, 3, 6, 5, 1, 6, 1

Then the banker leaves. We rotate the order of the path however we like

original order:

1, 2, 5, 3, 5, 2, 3, 4, 3, 6, 5, 1, 6, 1

rotated one order:

2, 5, 3, 5, 2, 3, 4, 3, 6, 5, 1, 6, 1, 2

rotated two order:

5, 3, 5, 2, 3, 4, 3, 6, 5, 1, 6, 1, 2, 5

We then put tokens face down corresponding to each region’s color in the rotated order we picked. In our example solution:

riddler2.jpg

If we used the “original order” the tokens would be:

(mind you they are face down)

R, Y, G, R, G, Y, R, Y, R, Y, G, R, Y, R”

riddler7.jpg

The banker is then brought back in and allowed to flip over any two adjacent tokens. If the rules are satisfied then you will never flip two of the same color.

This process of rotating the path order, setting up the tokens and having the banker flip two can be repeated as many times as required.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s