Monthly Archives: September 2013

Inverting the universe with two inverters

Recently I came across an interesting puzzle from MIT Tech Review March/April 2013:

Howard Cohen has plenty of AND and OR gates but just two inverters. How can he invert three signals a, b, and c?

More generally, he wonders if the ratio I/S can ever be less than 2/3, where I is the number of inverters and S is the number of signals to invert (once again, unlimited AND and OR gates are available).

I couldn’t quickly solve the first part of the puzzle with a pen and paper, so I decided to write a brute force solver. And to make it a bit more fun I did it in Haskell (any suggestions for improving the code are welcome, by the way!).

Continue reading Inverting the universe with two inverters