February 24–March 2, 2009
Problem
Click here to see a pdf version of the problem.
This nifty problem was suggested by Tom Boothby. It arose while finding efficient algorithms to do arithmetic in finite fields for SAGE. A bit of background is necessary.
Define the four "inputs"
consisting of 3 x 3 arrays of 1's and 0's. We are allowed to combine these inputs together using the logical operations and, or, xor (exclusive or). Associating "true" with a 1, and "false" with a 0, the following table summarizes the operations.
| r | s | r and s | r or s | r xor s |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
We apply these operations to each of the cells in the 3 x 3 grids, so for example, we have
Suppose we wish to make the outputs V and W from combinations of A, a, B and b.
We can make V and W in four steps as follows:
- Let C = a and B
- Let D = b and A
- Let V = C or b
- Let W = D or a
But if we're clever, we can do it with only three steps, like this:
- Let E = a or b
- Let V = E and B
- Let W = E and A
Now we're ready for the puzzle: Starting from the four inputs A, a, B and b, make both outputs
The winner will be the one who accomplishes this using the fewest number of steps.
Solution
List of solvers
- 6 steps: Koopa Koo (UW Grad), Chang Hai Bin, Luan Nguyen, Lloyd Sakazaki.
- 7 steps: Dustin Moody (UW Grad), Wenhan Wang (UW Grad), Justin Shih (UCLA Grad), Patrick Tam (UC Berkeley), David Bander.
- 8 Steps: Gary Raymond (UW staff), Adam Welly, David Kaplan.
Luan Nguyen wins the prize!