Using your Head is Permitted

August 2009 riddle

This month's riddle is a special joint riddle, the product of cooperation between "Using your Head is Permitted" and IBM's "Ponder This". The riddle has three parts. Each part can be answered individually for credit. Separate solvers' lists will be kept for each part.

The first part of the riddle is described here, on the "Ponder This" web-site. Solutions for it should be sent there, and the solvers' list for it will be published there, as well.

Parts two and three are described below. Solutions to them should be sent to the puzzlemaster here, as usual.

The riddle deals with Boolean functions in n variables. There are exactly m=22n such different functions, all of which can be implemented by gate arrays that consist of nothing but AND, OR and NOT gates.

In this particular riddle, you can use as many AND and OR gates as you wish, but NOT gates are costly, so you want to keep their numbers down to the absolute minimum possible.

Part 1:

See the "Ponder This" web-site for details.

Part 2:

We are trying to build a single gate array that will compute all m functions together. This is a gate array with n inputs and m outputs. What is the minimal number of NOT gates needed to implement it?

Part 3:

We are trying to build m gate arrays, each with n inputs and a single output, to compute the m different functions. In each gate array we want to use the minimal number possible of NOT gates. What is the number of NOT gates needed to implement the gate array for the function that is the worst-case (i.e., for the function requiring the largest number of NOT gates)?

List of solvers:

Part 1:

See the "Ponder This" web-site.

Part 2:

Øyvind Grotmol (5 August 15:41)
Eli Biham (7 August 20:22)
Yuval Filmus (20 August 06:56)

Part 3:

Eli Biham (8 August 08:34)
Øyvind Grotmol (9 August 15:30)
Yuval Filmus (20 August 06:56)

Elegant solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!

To solution

Back to main page