DonaldRauscher.com

A Blog About D4T4 & M47H

538 Riddler: Untangling the Tangled Wires

17 December ’16

The strategy for this week's Riddler is to continuously split the wires into halves until only pairs remain. Then, we form circuits between the pairs to pinpoint individual wires. Using this approach, we can determine the optimal number of trips when N is a power of 2. For , we need 2 trips. For , we need 3 trips. For , we need 4 trips. Etc.

Next, we need to figure out what happens in between these known power-of-2 points. Things get tricky when N is odd, or we can only form an odd number of pairs. With one trip, we can effectively split the problem into two smaller sub-problems. We can split the N=10 problem into a N=6 problem and a N=4 problem, each of which can be solved in 3 trips. So we need to round up in between powers-of-2. For , we need 3 trips. For , we need 4 trips. A general expression for the number of trips needed for N wires is therefore:

The following visual illustrates how to solve the N=3 through N=10 cases. Like colors represent wires that are tied together. Lines represent known delineations; we can know that a wire is part of a group but know exactly which wire down below it belongs to.

There are a couple tricky cases that are worth noting.

  • N=2: We actually can't figure out the simplest tangle of all! Well, we can't figure it out when playing by the current rules. One option would be to connect a new wire to one of the wires at the bottom, run it up to the top, and then use our circuit tester with the two wires; this effectively makes it a N=3 case where one wire is known.
  • N=6: By extension, the fact that N=2 is impossible makes the N=6 case tricky. Though we can still figure it out in 3 trips. We start by splitting into two halves, one with 4 wires and one with 2 wires. We then form a circuit between the two halves, which allows us to pinpoint 3 wires. Finally, we form 3 circuits between the 3 known wires and the 3 unknown wires.
  • N=10: This is why we split this into N=6 and N=4 cases rather than N=8 and N=2 cases!

538 Riddler: The CGold War

15 December ’16

This week's Riddler challenges us with some game theory. Each player has a hefty $1 trillion in gold and an army whose strength is uniformly distributed between 0 and 1. Each player knows their own army's strength but not their opponent's army's strength (obviously). Each player then simultaneously declares "Peace" or "War". If either player has declared "War", then war ensues, and the player with the most power army walks away with a cool $2 trillion (and the loser walks away with a big goose egg). If both players declare "Peace", then both parties retreat with their $1 trillion in tact.

Let's assume our opponent follows a simple strategy: if their strength is greater than Y, then go to war; if their strength is less than Y, then declare peace. And let's say we want to adopt a similar strategy but with a cutoff of X. What should our cutoff be?

Right away, we can discard any cutoffs X>Y. If our strength is [Y,X) and our opponent's strength is [0,Y), we should win $2 trillion, but, with this strategy, we settle for $1 trillion instead. We're not capitalizing on our higher strength as often as we should. We would always prefer a strategy with X=Y over a strategy with X>Y.

What about X<Y? First, let's draw out the state space:

We can define our expected winnings as follows:

Our optimal strategy is to be 50% more warmongering than our opponent, a strategy which nets us expected winnings greater than $1 trillion! Since this is effectively a zero-sum game, our gain comes at our opponent's expense. How will our opponent react? Eventually, after playing the game a few times, our opponent will realize that we have a lower war threshold, and they will undercut us. We will react in kind, and so forth and so forth. Eventually, we will both converge on the origin. This is the only Nash Equilibrium for the game; once at this point, it doesn't make sense for either party to deviate. This game bears resemblance to the popular Prisoner's dilemma. "Peace" is analagous to "cooperation", and "war" is analagous to "defection".

Additional question #1: What if a victory at war yields $5 trillion instead of $2 trillion? This doesn't change the dynamics of the game. In the above scenario, the optimal response strategy becomes . It doesn't change the Nash Equilibrium of the game. If anything, it drives us to converge on the N.E. after fewer iterations.

Additional question #2: what if the game is played sequentially? Interestingly, this makes the game completely trivial! Let's say we go second. There are no strategic decisions for us to make! After a few iterations of the game, we will deduce our opponent's war threshold X. If our opponent declares war, then we're going to war regardless. If they declare peace, this signals to us that their army's strength is X, and otherwise declare peace and pocket $1 trillion. What about the first player? What is the optimal value of X? We can show that player 1's expected winnings are $1 trillion for all values of X!

538 Riddler: Allison, Bob, and the Technicolor Dream Map

13 November ’16

9 8 7 6 5 4 3 2 1

Animate

This week's Riddler was very interesting! I'll start with my big ah-ha: any shape touching N shapes will "bury" at least N-2 shape(s). Take a simple example where we have 3 touching circles, 3 different colors. We can't draw a 4th circle whose area borders each of these 3 circles without fully concealing one of the 3 circles. Meaning we won't have 4 exposed circles when we're done and thus won't be able to get to a 5th color (Bob can use the color of the circle that we've concealed). It therefore follows that Allison will have to deliberately bury some shapes and therefore cannot win the game outright in 6 moves.

My best solution allows Allison to win in 9 moves. I started by drawing a cluster of 6 circles with 3 colors, each color used twice. Allison's 7th circle (4th color) buries 1 circle, Allison's 8th circle (5th color) buries 2 circles, and Allison's 9th circle (6th color) is simply a big circle encompassing the entire graph. So we need to draw 3 extra circles and 9 circles total to force Bob to use 6 different colors.