It can be shown that N inverters can invert 2^N-1 independent inputs, given an unlimited supply of AND and OR gates. The classic version of this puzzle is to invert 3 independent inputs using AND gates, OR gates, and only 2 inverters.

- This is solved by
n1 = not(i1 and i2 or i1 and i3 or i2 and i3); n2 = not((i1 or i2 or i3) and n1 or i1 and i2 and i3); o1 = (i2 or i3 or n2) and n1 or i2 and i3 and n2; o2 = (i1 or i3 or n2) and n1 or i1 and i3 and n2; o3 = (i1 or i2 or n2) and n1 or i1 and i2 and n2;

i1, i2, and i3 are the inputs, n1 and n2 are the inverted signals, and o1, o2, and o3 are the outputs. "and" has higher precedence than "or".

So, start with N inverters. Replace 3 of them with 2. Keep doing that until you're down to 2 inverters.

I was skeptical at first, because such a design requires so much feedback that I was sure the system would oscillate when switching between two particular states. But after writing a program to test every possible state change (32^2), it appears that this system settles after a maximum of 3 feedback logic iterations. I did not include gate delays in the simulation, however, which could increase the number of iterations before the system settles.

In any case, it appears that the world needs only 2 inverters! :-)