Connected subsets in a grid 
Moderator Note: This question is from a contest which ended on 22 Oct 2012.


Consider the above badly drawn diagram. Consider all subsets of $\left\{{1,2,3,4}\right\}$ if we were to place them in the below boxes. If two such subsets $M$ and $N$ are placed in boxes connected by a bold line, the symmetric difference of $M$ and $N$ should only contain $1$ number. If two subsets of $\left\{{1,2,3,4}\right\}$ are placed in boxes connected by a dashed line then the largest terms in each should be equal. Is such an arrangement possible for this grid? If so, is it unique, and what is the logic behind creating it? 
 A: There is a unique solution, and it can be found by logic alone (i.e., human-level logic that doesn't require backtracking of more than a few steps).  A few things to note that help with the process of elimination:


*

*Any two boxes connected to each other by a solid line contain subsets differing in size by exactly one; and so any two boxes connected to each other by a solid path with an even (odd) length contain subsets differing in size by an even (odd) number.

*All pairs of boxes joined by a dotted line are separated by an even-length solid path, and hence differ in size by an even number of elements, except the pair in the lower left.

*The subset $\{1\}$ can't lie on a dotted line, since it's the unique subset with the highest value $1$.

*The subsets $\{1,2\}$ and $\{2\}$ have the property that if either of them is on a dotted line, it's connected to the other by that line, since they're the unique subsets with the highest value $2$.  By fact 2., since they differ in size by an odd number of elements, they either both go in the pair of boxes on the lower left, or neither is on a dotted line.


By fact 1., the subset $\{1\}$ needs to go in one of the four boxes not on any dotted line.  Three of those boxes are part of solid-solid-dotted triangles: the subset $\{1\}$ can't go at the solid-solid vertex of any of those, either, because its neighbors would have to be of the form $\{1,a\}$ and $\{1,b\}$, with $a=b$ (because of the dotted line) and $a\neq b$ (because they are different boxes): a contradiction.  That leaves the upper right-hand corner as the unique location for $\{1\}$.
By fact 4., $\{2\}$ and $\{1,2\}$ either (a) both go in the pair of boxes on the lower left, or (b) neither touches a dotted line.  If it's (b), then there are three places left that they can go: the two boxes on the lower right, and the box next to $\{1\}$ in the upper right.  They can't both go in the two boxes on the lower right (even-solid-distance), so one must go next to $\{1\}$... that would have to be $\{1,2\}$ because of the solid connection to $\{1\}$.  But $\{1,2\}$'s other solid-line neighbors would have to be $\{1,3\}$ and $\{1,4\}$, which don't have the same highest element, and so (b) is a contradiction.  Therefore one of $\{2\}$ and $\{1,2\}$ goes on the extreme lower left: that's an even-solid-distance from the upper right, which contains $\{1\}$, so $\{2\}$ must be on the lower left.  And $\{1,2\}$ is just above it.
All the remaining boxes and dotted lines are in solid-solid-dotted triangles (some are in more than one).  If $\{1,3\}$ or $\{2,3\}$ are on a dotted line, they must be connected to the other by it (only two even-size subsets with the highest value $3$), and the remaining vertex in the solid-solid-dotted triangle must be $\{1,2,3\}$ or $\{3\}$.  They also can't go in the boxes on the lower right (even-solid-distance from the upper right), leaving only one box not on a dotted line, so they must be on a dotted line.  It can't be the long dotted line (no other highest-number-$3$ and even-size partner), or either of the two short dotted lines an even-solid-distance from the upper right.  That leaves the upper left corner and the box to its southeast for $\{1,3\}$ and $\{2,3\}$, and forces $\{1,2,3\}$ into the box above $\{1,2\}$ (since the other choice, $\{3\}$, can't be joined by a solid line to $\{1,2\}$).  Now $\{3\}$ must be to its southeast, since it's the only highest-number-$3$ partner left.
The upper left can't be $\{2,3\}$, because the only ways to get from $\{1\}$ to $\{2,3\}$ with three solid lines use $\{1,2\}$ or $\{1,3\}$, which aren't available; so it must be $\{1,3\}$, and the other boxes in the top row must then be $\{1,4,3\}$ and $\{1,4\}$ (left to right).
The rest can now be filled in rapidly.  $\{2,4\}$ to the right of $\{2\}$.  $\{3,4\}$ to the right of $\{3\}$.  $\{1,2,3,4\}$ to the northeast of $\{3,4\}$ (only even-sized subset left).  $\{2,3,4\}$ connecting $\{3,4\}$ to $\{1,2,3,4\}$ by solid lines.  $\{4\}$ connecting $\{2,4\}$ and $\{3,4\}$ by solid lines.  And $\{1,2,4\}$ connecting $\{1,4\}$ and $\{1,2,3,4\}$ by solid lines.  And done.
A: I actually managed to find the solution by hand. Let $C_{ij}$ be the cell in row $i$ (from the top), column $j$. Two cells are twins if they’re connected by a dotted line. A limited cell is one that’s connected by solid lines to a pair of twins. It’s not hard to see that the maximum element in a limited cell must be $3$ or $4$ and must also be the maximum element of the associated twins. The only cells that are neither limited nor twins associated with a limited cell are $C_{14},C_{31}$, and $C_{41}$, so these must contain the sets $\{1\},\{2\}$, and $\{1,2\}$ in some order. $C_{31}$ and $C_{41}$ are twins, so they must contain $\{2\}$ and $\{1,2\}$, and $\{1\}$ must be in $C_{14}$.
There are four sets with $3$ as maximum element and eight with $4$ as maximum element. Among these $12$ sets we must find five pairs of twins, so there must be at least one pair of twins with maximum element $3$. It can’t be $C_{24}$ and $C_{33}$ or $C_{33}$ and $C_{42}$, because that would force all five of the cells $C_{24},C_{33},C_{42},C_{34}$, and $C_{43}$ to have $3$ as maximum element. It can’t be $C_{12}$ and $C_{23}$: that would force $C_{13}$ to contain $\{1,3\}$, putting $\{3\}$ and $\{1,2,3\}$ in $C_{12}$ and $C_{23}$ in one order or the other, and leaving no place for $\{2,3\}$, since every remaining cell is either limited or an associated twin and will therefore have to have $4$ as maximum element. Thus, it must be either $C_{11}$ and $C_{22}$ or $C_{21}$ and $C_{32}$, and one quickly sees that either forces the four sets with maximum element $3$ to occupy the cells $C_{11},C_{21},C_{22}$, and $C_{32}$.
This clearly puts $\{1,4\}$ in $C_{13}$, and since $C_{11}$ will definitely contain a $3$, $C_{12}$ must contain $\{1,3,4\}$. This puts $\{1,3\}$ in $C_{11}$ and either $\{3\}$ or $\{1,2,3\}$ in $C_{21}$. We know that $C_{31}$ contains a $2$ and no $3$, so $C_{21}$ must contain $\{1,2,3\}$, and we can now assign $\{2,3\}$ to $C_{22}$, $\{3\}$ to $C_{32}$, $\{1,2\}$ to $C_{31}$, $\{2\}$ to $C_{41}$, and then $\{2,4\}$ to $C_{42}$. We can also assign $\{1,3,4\}$ to $C_{12}$ and $\{1,4\}$ to $C_{13}$.
$C_{23}$ must contain either $\{4\}$ or $\{1,2,4\}$. If it contains $\{4\}$, $C_{24}$ must contain $\{3,4\}$, $C_{34}$ must contain $\{2,3,4\}$, and $C_{33}$ is impossible to fill. Thus, $C_{23}$ contains $\{1,2,4\}$, forcing $C_{24}$ to contain $\{1,2,3,4\}$, $C_{34}$ to contain $\{2,3,4\}$, $C_{33}$ to contain $\{3,4\}$, and $C_{43}$ to contain $\{4\}$, completing the solution.
Added: And I see that mjqxxxx beat me to it. Oh, well!
