# Solution to Long Division

The fundamental idea behind this puzzle is to perform a graphic XOR operation. That is, you take the rectangle that is given, which has a line dividing it exactly in half, and create a new rectangle the same size as one half of the original which is the two halves XORed together. So, if a line is present in a certain place in one half but not in exactly the same place in the other, it should appear in that place in the new rectangle. If a line appears in neither or both, it should not.

Performing this operation on the given rectangle produces another rectangle with a line dividing it exactly in half. Thus, you can XOR its two halves to produce another rectangle, and so forth.

It turns out that all of these rectangles also have the property that one of its halves has a line dividing it into two equal quarters (labelled B and C here):

```---------
|   | B |
| A |---|
|   | C |
---------
```

If these two quarters are XORed together to get a rectangle one quarter the size of the original, you get a letter drawn out. For the main rectangle, the letter is A. For the second rectangle, the letter is C. When the rectangle gets small, eventually it will not have one half divided into two quarters, so you just XOR the two halves, which gives the final letter in the chain. Putting all these letters together in the order they appear down the chain creates the word ACRONYM.

There are also smaller "hidden" rectangles inside the first four main rectangles. These are rectangles one quarter of the size of the current rectangle, but with the same half-and-two-quarters structure (in the first rectangle, for instance, the hidden rectangle is from coordinates (x,y from the upper left) 10,15 to 34,31). Pulling each of these hidden rectangles out and performing the same set of operations as you did on the main rectangle produces a word. Putting these words in the order they are found in the chain, including the word from the main chain, clues the answer.

Below is a graph of every rectangle that comes up in the puzzle. Recangles are represented by their dimensions, and a letter written inside it if there is one. The three operations that can be done to get one rectangle from another are represented as follows:

 | A vertical line represents the basic XOR operation, xoring one half with the other to get a rectangle half the size. \ A diagonal line represents taking the two quarters (e.g. B and C above) and xoring them with each other to get a rectangle one quarter the size which will have a letter written inside it. - A horizontal line represents finding a "hidden" rectangle one quarter the size of the current one and bringing it out.
```48x32-----------------------------------24x16
|   \                                   |   \
|  24x16(A)                             |  12x8(F)
|                                       |
24x32------------------------12x16      12x16
|   \                        |   \      |   \
|  12x16(C)                  |   6x8(H) |   6x8(O)
|                            |          |
24x16---------------12x8     12x8       12x8
|   \               |  \     |  \       |
|  12x8(R)          | 6x4(D) |  6x4(I)  |
|                   |        |          |
12x16------6x8      6x8      6x8        6x8(R)
|   \      | \      | \      | \
|   6x8(O) | 3x4(T) | 3x4(E) | 3x4(G)
|          |        |        |
12x8       6x4      6x4      6x4
|  \       |        |        |
|  6x4(N)  |        |        |
|          |        |        |
6x8        3x4(V)   3x4(F)   3x4(H)
| \
| 3x4(Y)
|
6x4
|
|
|
3x4(M)
```

Putting all these letters together gives ACRONYM FOR HIGH DEF TV, which is the answer HDTV.

2006 MIT Mystery Hunt