IBM Research | Ponder This | August 2009 challenges

# Ponder This

## August 2009

<<July August September>>

Ponder This Challenge:

This month's challenge is a joint problem with UyHiP site and is about Boolean functions.

We use the following notation:

The input to the function is given in variables ("a", "b", etc).
Each Boolean gate gets two inputs and stores its output in the next consecutive letter.
We denote an AND gate by putting its inputs in lexicographical order; and an OR gate by reversing the order.
We assume that a capital letter represents the negation of its lower case.

For example "abAced" is an implementation of the multiplexer function:

mux(a,b,c) = b if a is true, c otherwise.

Explanation:

d <=- a AND b; it is an AND gate since a<b
e <=- (NOT a) AND c; A means (NOT a) and AND since a<c
f <=- d or e; it is an OR gate since e>d

We want to compute the negation of three variables, but, unfortunately, we have only two NOT gates.

The answer should be given as sequence of letters according to the notation above; "a" "b" and "c" contains the input and the last three pairs should compute NOT(a); NOT(b); and NOT(c).

Since we allow for only two inverters (NOT gates), only two different letters can appear as capital.

One can generalize this question by asking, for example, how many inverters are needed to implement n inversions; more follow-ups questions can be found at UyHiP (link resides outside of ibm.com).

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Challenge: 08/02/2009 @ 11:00 PM EST
Solution: 08/31/2009 @ 9:00 AM EST
List Updated: 09/01/2009 @11:00 AM EST

J. Kennedy (08/03/2009 05:26 PM EDT)
Adam Daire (08/03/2009 05:57 PM EDT)
Eli Biham (08/03/2009 06:29 PM EDT)
Andreas Eisele (08/03/2009 07:43 PM EDT)
Michael Quist (08/04/2009 05:16 PM EDT)
Andrew Holster (08/04/2009 11:06 PM EDT)
Mark Mixer (08/05/2009 08:21 AM EDT)
Daniel Chong Jyh Tar (08/05/2009 09:49 AM EDT)
Steffen Wolf (08/05/2009 10:46 AM EDT)
Lukasz Bolikowski (08/05/2009 10:50 AM EDT)
Daniel Bitin
(08/05/2009 11:58 AM EDT)
Matej Kollar (08/05/2009 04:45 PM EDT)
Chungmin Lee (08/05/2009 05:45 PM EDT)
Yuval Filmus (08/05/2009 07:49 PM EDT)
Nyles Heise
(08/06/2009 01:40 PM EDT)
Chuck Carroll (08/06/2009 04:39 PM EDT)
Sevag Papazian (08/07/2009 03:43 AM EDT)
Jonathan Campbell (08/07/2009 11:47 AM EDT)
Lachezar Christov (08/09/2009 05:14 AM EDT)
Hongcheng Zhu (08/09/2009 05:43 AM EDT)
Harold Gutch and Peter Gruber (08/09/2009 07:31 PM EDT)
Alan Murray (08/10/2009 11:44 PM EDT)
Andrei Laza (08/11/2009 02:19 AM EDT)
Subramanian C. A (08/11/2009 06:00 AM EDT)
Harald Boegeholz
(08/11/2009 05:52 PM EDT)
Dan Dima
(08/12/2009 09:40 AM EDT)
Michael Schaaf (08/12/2009 09:46 AM EDT)
John Ritson (08/13/2009 02:30 AM EDT)
John T. Robinson (08/13/2009 11:35 AM EDT)
Clive Tong (08/14/2009 03:21 PM EDT)
Corey Cerovsek (08/15/2009 10:12 AM EDT)
Christian Blatter (08/17/2009 07:39 AM EDT)
Ionel Santa (08/18/2009 03:42 AM EDT)
Albert Stadler (08/18/2009 01:15 PM EDT)
Steven Langerwerf
(08/19/2009 03:57 PM EDT)
Bobby Brennan (08/19/2009 09:47 PM EDT)
Mithil Ramteke & S. Ramakrishnan (08/20/2009 10:17 AM EDT)
Bojan Basic
(08/21/2009 03:39 PM EDT)
Joseph DeVincentis
(08/27/2009 12:03 PM EDT)
Jason L. (08/28/2009 11:43 AM EDT)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.