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

Game Theory on a Number Line

Another week, another Riddler. Here is a fun problem:

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?

To solve this we have to assume each player is a perfect logician – then we work in reverse: say we know exactly where Ariel and Beatrice have placed their token. If this is the case we can find the optimal place for Cassandra to put her token to maximize her earnings. Using this we can back out the optimal place for Beatrice to put her token after each of Allice’s moves — it would be where Cassandra’s best move is the worst. Using this we can back out Allice’s best move — its where even if Beatrice and Cassandra use their best moves its the best for Ariel. Here’s an example:


#Of the form: 

# [[A's token place (0 indexed), B's token place, C's token place], [A's winnings, B's winnings, C's winnings]]

[[1, 5, 2], [1, 49, 5]]
[[1, 5, 4], [2.0, 47.0, 6.0]]
[[1, 5, 5], [3, 45, 7]]
[[1, 5, 6], [4.5, 10.5, 40]]
[[1, 5, 7], [4.5, 13.5, 37.0]]
[[1, 5, 8], [4.5, 16.5, 34]]
[[1, 5, 9], [4.5, 20.0, 30.5]]
[[1, 5, 10], [4.5, 23.5, 27]]

From this we can figure out if A places token on 1 and B places on 5 then C will always place on 6. Here is an example for B’s decision:


#Of the form:

# [[token places (1 indexed)], [winnings]]

[[1, 2, 3], [1, 2, 52]]
[[1, 3, 4], [2.0, 4.0, 49]]
[[1, 4, 5], [3, 7, 45]]
[[1, 5, 6], [4.5, 10.5, 40]]
[[1, 6, 7], [6, 15, 34]]
[[1, 7, 8], [8.0, 20.0, 27]]
[[1, 8, 7], [8.0, 27, 20.0]]
[[1, 9, 8], [10, 19, 26]]
[[1, 10, 9], [12.5, 10, 32.5]]

Here we determine that if A places on 1, then it is in B’s best interest to place on 8. We do this a final time and determine the players will play:

#Of the form:
# [[token places (1 indexed)], [winnings]]

[[5, 9, 8], [21, 19, 15]]

And this is the answer to our problem.

Matching Game

Another week, another riddler. I really liked this one, if a bit clear cut. The problem:

I have a matching game app for my 4-year-old daughter. There are 10 different pairs of cards, each pair depicting the same animal. That makes 20 cards total, all arrayed face down. The goal is to match all the pairs. When you flip two cards up, if they match, they stay up, decreasing the number of unmatched cards and rewarding you with the corresponding animal sound. If they don’t match, they both flip back down. (Essentially like Concentration.) However, my 1-year-old son also likes to play the game, exclusively for its animal sounds. He has no ability to match cards intentionally — it’s all random.

If he flips a pair of cards every second and it takes another second for them to either flip back over or to make the “matching” sound, how long should my daughter expect to have to wait before he finishes the game and it’s her turn again?

To solve this we can look at each “level” independently, where a level is the number of pairs of cards remaining. We start at level 10 and our goal is to get to level 0. To figure out the estimated amount of time on, for example, level 10 we use the equation:

t_{10} = \frac{1}{19}(2) + \frac{18}{19}(2+t_{10})

This says the first card selection doesn’t matter – but after selecting it we have to select the second card and there is only one pair. This equation shows that there is a 1/19 chance we correctly select the card and proceed, while costing two seconds. There is also a 18/19 chance we fail, which costs us two seconds plus the time to successfully complete the level. Solving this gives us:

t_{10} = 38

Extending this we can see that solving for a generalized level is:

t_{n} = \frac{1}{2n-1}(2) + \frac{2n-2}{2n-1}(2+t_{n})

Summing levels 1-10 gives us 200 seconds. This was confirmed by brute forcing it in python.

import random, math

def run_trial(card_pairs): 
  time = 0
card_set = [math.floor(i/2) for i in range(card_pairs*2)]
while len(card_set):
    selection_index = [i for i in range(len(card_set))]
    random.shuffle(selection_index)
    if card_set[selection_index[0]] == card_set[selection_index[1]]:
      value = card_set[selection_index[0]]
      card_set.remove(value)
card_set.remove(value)
time += 2
return time

sum_time = 0
trials = 10000
for i in range(trials): sum_time += run_trial(10)
print("Average time: " + str(sum_time/trials))

 

A Classic Construction Problem

Another week, another Riddler. The question:

Consider four towns arranged to form the corners of a square, where each side is 10 miles long. You own a road-building company. The state has offered you $28 million to construct a road system linking all four towns in some way, and it costs you $1 million to build one mile of road. Can you turn a profit if you take the job?

Extra credit: How does your business calculus change if there were five towns arranged as a pentagon? Six as a hexagon? Etc.?

After a few napkin drawings I landed on this shape:

shape.png

Then I set up this series of equations:

Untitled2.png

Plugging that into Python we get answer of 27.3205 miles of bridges with an x_1 distance of 2.887.

Figure_1.png

Pretty simple but fun!

 

Camel Up Cup 2k18

Get ready for the premier bot creation board game tournament of the year!

Here’s the plan: A bunch of people make a bot to play the board game Camel Up. Then in a battle of wits we get together and pit our bots against one another. The winner will get a trophy. This is somewhat similar to Halite except way less competitive and no one will get a job as a result

CamelUp.PNG

The game

The game itself:

– The game is called CamelUp. I own a copy and can lend it out to try. There is also a copy at Cafe Mox in Ballard and maybe one at RayGun in Cap Hill
How to play: this video does a pretty good job of explaining how to play the game. Its five minutes
– We will playing the game with four players (bots) in each round. Player ordering and stuff will be figured out later. Only points will be awarded to the winning player

Cropped.png

Rendering of trophies

The bot details:

– We are using Python 3.x
– Your bot will be a function that I will pass the player number and gamestate to. Using that you should return your action
– I may be patching the game leading up to the event. It should just be for bugs / things I’ve missed. Hopefully nothing crazy though. Let me know if you something

Please invite anyone! Teams are cool! Reach out with questions.

The API can be found here

 

boardstate.PNG

Example of a player action