April Fools Circuit

So, this is my take for April Fools in 2017.

What is the problem? Well, we see a logic circuit here. The outputs provide the circuit's own inputs, so it's likely that there are contradictions if the outputs are wrong. So let's try to figure out what the outputs should be.

Call the outputs $A, B, C, D, E$ in that order. Remember that $\cdot, +, \oplus$ are AND, OR, XOR respectively, and $\overline{A}$ is the negation of $A$ . For sake of convenience, we'll use $0, 1$ for false and true respectively.

The equations, if you know logic gates , are as follows:

• $A = B + C$
• $B = \overline{B \cdot C}$
• $C = \overline{A \oplus E}$
• $D = D \cdot E$
• $E = \overline{A + D}$

How do we solve it? The self-referential equations are particularly interesting. In fact, the second equation only has one solution. If $B = 0$ , then $B \cdot C = 0$ , but then $\overline{B \cdot C} = 1$ , contradiction. So $B = 1$ . And now that $B = 1$ , we have $\overline{B \cdot C} = 1$ , so $B \cdot C = 0$ . Since $B = 1$ , we need $C = 0$ .

Since we know $B, C$ , we can now deduce $A = B + C = 1$ . We can then deduce $E$ from the third equation: $0 = \overline{1 \oplus E}$ , so $1 = 1 \oplus E$ , so $E = 0$ . Finally, this allows us to deduce $D$ : since $E = 0$ , we have $D \cdot E = 0$ , so $D = 0$ .

Thus, in fact, we have a single solution! It's $(A, B, C, D, E) = (1, 1, 0, 0, 0)$ . So it is "an answer", even though we're still not sure what we're looking for. But it's worth a try; we have binary outputs, and it says to write the answer in decimal. So we can try reading these values as a binary number $11000_2$ , and interpret it to decimal, giving $\boxed{24}$ , which is indeed the answer to this problem. Hope you enjoyed it!

This problem is inspired from a more ridiculous, more unfair problem in CodeForces April Fools Contest 2017.

---

So, yes, this is an April Fools joke. This problem is written in the spirit of puzzlehunt puzzles ; unlike standard problems with clearly defined objective, this problem doesn't tell you what you need to do. (What is "the answer"?) On the other hand, such problems can be satisfying to solve, when you fiddle around with the data you're given and everything suddenly just clicks together. We puzzlehunters call it the a-ha! moment, because that's what you'll probably say when you get the breakthrough. How the problem doesn't need any additional information (because the circuit, the biggest thing that attracts your attention here, does have a unique solution), why there's "in decimal" (because you get a number that is not in decimal, so it serves as a check that you're trying to extract a number and also that number is not originally in decimal)...

Speaking of which, the reason I asked for the decimal number was two-fold: one, it gives you the clue that you'll be getting some number which is not in decimal, and two, this helps making sure that leading zeroes won't be a problem. (Had the answer been something like 00011, you'll see the accepted answer as "11" instead of "00011", which is unclear for people that fail to solve the problem. If it's converted to decimal, you won't care that "3" is missing a leading zero.)

I took an (abstract) algebraic approach with the finite (Galois) field $GF(2)$ (just $\{0,1,+,\cdot\}$ with mod 2 arithmetic). I haven’t seen this here yet, so I thought I’d share it. First, express the logical gate operators as algebraic expressions in operators, constants, and variables $x, y$ in $GF(2)$ . $\begin{aligned} &\text{NOT } x = 1 + x \;, \\ &x \text{ AND } y = xy \;, \\ &x \text{ XOR } y = x + y \;, \\ &x \text{ OR } y = x + y + xy \;. \\ \end{aligned}$ In the figure, label inputs $\{b_n\}_{n=0, …,4} \in GF(2)$ left to right as ${b_4, b_3, b_2, b_1, b_0}$ . As per the circuit diagram, equate the logical gate outputs to the input variables to produce the following system of equations: $\begin{aligned}(0) \; &b_0 = 1 + b_1 + b_4 + b_1 b_4 \;, \\ (1) \; &b_1 = b_1 b_0 \;, \\ (2) \; &b_2 = 1 + b_0 + b_4 \;, \\ (3) \; &b_3 = 1 + b_2 b_3 \;, \\ (4) \; &b_4 = b_2 + b_3 + b_2 b_3 \;.\\ \end{aligned}$ $$ Solve by using $GF(2)$ ’s multiplicative idempotency ( $x^2 = x$ ) and additive nilpotency ( $x + x = 0$ ) for simplification (along with its other props).

Sub (0) into (1): $b_1 = b_1 b_0 = b_1 (1 + b_1 + b_4 + b_1 b_4) = b_1 + b_1^2 + b_1 b_4 + b_1^2 b_4 = (b_1 + b_1) + (b_1 b_4 + b_1 b_4) = 0 + 0 = 0 \therefore b_1 = 0.$

Sub $b_1$ into (0): $\begin{aligned} (5) \; &b_0 = 1 + b_4 \;. \\ \end{aligned}$

Sub (5) into (2): $b_2 = 1 + b_0 + b_4 = 1 + (1 + b_4) + b_4 = (1 + 1) + (b_4 + b_4) = 0 + 0 = 0 \therefore b_2 = 0.$

Sub $b_2$ into (3): $b_3 = 1 + b_2 b_3 = 1 \therefore b_3 = 1.$

Sub $b_2$ and $b_3$ into (4): $b_4 = b_2 + b_3 + b_2 b_3 = 0 + 1 + 0 = 1 \therefore b_4 = 1.$

Sub $b_4$ into (5): $b_0 = 1 + b_4 = 1 + 1 = 0 \therefore b_0 = 0.$

Therefore, $b_4 b_3 b_2 b_1 b_0 = 11000_2 = \boxed{24_{10}} .$