S3E40. How CS and Group Theory found a diamond

In this episode we solve a beautiful computer science puzzle that is originally wrapped into an everyday spoken tongue that is free from any professional jargon. However, we quickly discover that behind the innocent sounding formulation of this problem there sits a pretty deep, and elegant, mathematics. The mathematics of the restorative power of the XOR operator and of the finite commutative group formed by the set of all binary strings of fixed length n and the said XOR operator. That is. First, we define the XOR operator in a group-theoretic friendly way. Then, we show that that operator is commutative and associative. Then, we demonstrate the closure of the binary strings under XOR, the existence of the unique double-sided identity element and the fact that every element of that group has the oder two or is self-inverse. The order of that group, B_n, is a perfect power of two: 2^n. Then we show that like a mythical bird Phoenix that rises from its own ashes, the XOR operator can restore the value of one of its operands, provided that the result of an operation and the remaining operand are known. Next, we describe a solution of this puzzle in theory and then we demonstrate how that theory can be applied in practice. A small obfuscation based on the fact that 8 is a perfect cube is followed by a clever observation that once the mathematical essence of a problem has been uncovered, it can be dressed up into any, fancy, costume. Lastly, do realize that this type of puzzles only works when the number of working items, such as "boxes", is a perfect power of 2, which is precisely the order of the earlier mentioned binary strings group B_n.