Design a 3-input 3-output logic circuit that negates the 3 signals. You have an infinite supply of AND and OR gates but only two NOT gates.

Heard from a fellow student at UC Berkeley in 1996.

The construction below is more insightful if we work with a general n, instead of n = 3. We will show that n NOT gates are sufficient to invert 2^n - 1 signals. But please keep Philip Martel's comment in mind:

Let the input signals be s0, s1, s2, s3, ... We define 3 functions:

Q(k) is simply the OR of all combinations of k signals AND-ed together. For example, with 3 input signals:

Q(0) = 1
Q(1) = s0 +s1 + s2
Q(2) = s0.s1 + s1.s2 + s2.s0
Q(3) = s0.s1.s2.

Thus, for k ∈ [0, 2^n - 1], Q(k) = 1 iff at least k input signals are 1.

R(k, i) is obtained by removing all terms containing the i-th signal from Q(k). For example, for 3 input signals: R(1, 0) = s1 + s2
R(1, 1) = s0 + s2
R(1, 2) = s0 + s1
R(2, 0) = s1.s2
R(2, 1) = s2.s0
R(2, 2) = s0.s1

Thus, for k ∈ [0, 2^n - 1), i ∈ [0, 2^n - 1), R(k, i) = 1 iff at least k input signals are 1, ignoring the i-th input signal.

Finally, let us define the third function: For k ∈ [0, 2^n - 1], P(k) = 1 iff exactly k input signals are 1. Assuming we manage to construct P's, the inversion of the i-th signal is the expression P(0) + P(1).R(1, i) + P(2).R(2, i) + P(3).R(3, i) + ...

Note that so far, we have not used any NOT gates.

Constructing P's from Q's is the heart of the puzzle — NOT gates are used for doing so. We explain the procedure with an example: we show how to invert seven signals with three NOT gates. Let us "visualize" the Q's by writing them in short-hand as bit-masks: the i-th bit from the left denotes that exactly i signals are on, and concatenation of bits denotes the OR operation.

Bitmask(7) = 00000001 (denotes Q(7))
Bitmask(6) = 00000011 (denotes Q(6))
Bitmask(5) = 00000111 (denotes Q(5))
Bitmask(4) = 00001111 (denotes Q(4))
Bitmask(3) = 00011111 (denotes Q(3))
Bitmask(2) = 00111111 (denotes Q(2))
Bitmask(1) = 01111111 (denotes Q(1))
Bitmask(0) = 11111111 (denotes Q(0))

Our goal is to produce the P's, whose bit-masks are:

00000001
00000010
00000100
00001000
00010000
00100000
01000000
10000000

Step 1: Complement Bitmask(4) to get 11110000. Then replace Bitmask(3), Bitmask(2), Bitmask(1) and Bitmask(0) by AND-ing them with 11110000 to get:

Bitmask(7) = 00000001
Bitmask(6) = 00000011
Bitmask(5) = 00000111
Bitmask(4) = 00001111
Bitmask(3) = 00010000
Bitmask(2) = 00110000
Bitmask(1) = 01110000
Bitmask(0) = 11110000

Step 2: Complement the expression Bitmask(2) OR Bitmask(6) to get 11001100. Then replace Bitmask(5), Bitmask(4), Bitmask(1) and Bitmask(0) by AND-ing them with 11001100 to get:

Bitmask(7) = 00000001
Bitmask(6) = 00000011
Bitmask(5) = 00000100
Bitmask(4) = 00001100
Bitmask(3) = 00010000
Bitmask(2) = 00110000
Bitmask(1) = 01000000
Bitmask(0) = 11000000

Step 3: Complement the expression Bitmask(1) OR Bitmask(3) OR Bitmask(5) OR Bitmask(7) to get 10101010. Then replace Bitmask(6), Bitmask(4), Bitmask(2) and Bitmask(0) by AND-ing them with 10101010 to get:

Bitmask(7) = 00000001
Bitmask(6) = 00000010
Bitmask(5) = 00000100
Bitmask(4) = 00001000
Bitmask(3) = 00010000
Bitmask(2) = 00100000
Bitmask(1) = 01000000
Bitmask(0) = 10000000

which are exactly the P's that we wanted! One NOT gate was used in each step. The procedure can be generalized for higher powers of two.

The problem was first studied in On Maximum Inversion with Minimum Inverters by S B Akers, IEEE Transactions on Computers, Vol 17, Issue 2, Feb 1968, pages 134-135. A modern writeup is here: An Intriguing Digital Logic Problem: How fundamental is an inverter? by Srinivasan Ramasubramanian, 2007.