A Planar Circuit 

    --------    
A --|      |-- B
    | ckt? |    
B --|      |-- A
    --------
You have available the three basic logic gates: AND, OR, and NOT gates. The goal is to build a circuit that allows two signals to cross. The constraint is that the circuit has to be "planar", that is you can't cross signals (otherwise it would be trivial).

What is the minimum number of gates needed?

Source: Original extension of a problem from John Guilford (Agilent Technologies) as quoted in Macalester Problem of the Week #919.

Solution
Mail to Ken