# Making Three NOT Gates from Two

Here is an old and interesting logic puzzle.

### Background

Recall an AND gate takes in two inputs A and B, and has one output X. The truth table looks like

A AND B 0 1
0 0 0
1 0 1

Similarly, OR looks like

A OR B 0 1
0 0 1
1 1 1

And NOT simply inverts its input:

A NOT A
0 1
1 0

# How many prisoners?

This riddle comes from the XKCD forums, at http://forums.xkcd.com/viewtopic.php?f=3&t=70558 and is as follows:

You, together with a finite number n-1 of other ideal mathematicians, have been arrested on a whim by a generic evil dictator and are about to be locked up in a prison. The prison is circular, with n identical windowless cells arranged in a ring around a central court. There are some problems with the lighting system – the light switch in each cell controls the light in the next cell clockwise around the ring. Even worse, electric power is only provided to the lights for one tenth of a second each night, just after midnight.

# Pick a Number

Here is a logic puzzle I find interesting. Unfortunately I don’t recall the source.

Alice picks two distinct real numbers, and puts one in each of two envelopes. Bob wants to pick the envelope containing the larger of the two numbers. Bob picks an envelope, and look at the number inside it.

After seeing the number, Bob can elect to switch envelopes. If he switches he has to take the second. If he doesn’t switch, he has to keep the first.

Is there a strategy that allows Bob to select the larger value with greater than a 50% chance?