# 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?

-
$\{1,2,3,4\}$ has $16$ subsets, but you have only $15$ boxes; which subset are you omitting? Also, exactly what do you mean here by disjoint union; is it possible that you actually mean symmetric difference? –  Brian M. Scott Sep 13 '12 at 1:16
symmetric differenec, yes. I suppose I should specify non-empty subsets. –  Aria Fitzpatrick Sep 13 '12 at 1:21
Please clarify the question in the question itself, not just in a comment. The question should be self-contained and clear without recourse to the comments. –  joriki Sep 13 '12 at 7:38

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:

1. 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.
2. 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.
3. The subset $\{1\}$ can't lie on a dotted line, since it's the unique subset with the highest value $1$.
4. 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.

-

I wrote a backtracking algorithm and it found a solution:

0101 1101 1001 0001
0111 0110 1011 1111
0011 0100 1100 1110
0010 1010 1000


It turns out this solution is unique. I think one would be hard pressed to find this solution by hand.

Here a cell containing e.g. 0101 implies that its set is {3,1}, and e.g. 0001 has set {1}. My C source code is given below:

#include <stdio.h>

int z[15];

int solid_okay[16][16];
int dashed_okay[16][16];

const int nr_solid_edges=15;
int solid_edge_set_in[15]  = {1,2,3,4,5,6,7,8,9,10,11,11,13,14,14};
int solid_edge_set_out[15] = {0,1,2,0,4,2,6,4,5,9, 7, 10,12,10,13};

const int nr_dashed_edges=6;
int dashed_edge_set_in[6]  = {5,6,9,10,12,13};
int dashed_edge_set_out[6] = {0,1,4, 7, 8,10};

int used_symbols=0;

void print_in_binary_4_bits(int n) {
int a,b,c,d;
a=n&1;
b=n&2;
c=n&4;
d=n&8;
b=b>>1;
c=c>>2;
d=d>>3;
printf("%d%d%d%d ",d,c,b,a);
}

int check_solid_line(int x,int y)
{
if(x==y) return 0;
int t=x^y;
if(t==1 || t==2 || t==4 || t==8) return 1;
return 0;
}

int check_dashed_line(int x,int y)
{
if(x<0 || x>16 || x==y) return 0;

if((x&8)==8 && (y&8)==8) return 1;
if((x&8)!=(y&8)) return 0;
if((x&4)==4 && (y&4)==4) return 1;
if((x&4)!=(y&4)) return 0;
if((x&2)==2 && (y&2)==2) return 1;
if((x&2)!=(y&2)) return 0;
if((x&1)==1 && (y&1)==1) return 1;
if((x&1)!=(y&1)) return 0;
}

int find_z_value_backtracking_algorithm(int step)
{
if(step==15) {
for(int i=0;i<4;i++) {
for(int j=0;j<4;j++) {
print_in_binary_4_bits(z[4*i+j]);
}
printf("\n");
}
printf("\n");
}

for(int i=1;i<16;i++) {
int t=2<<i;
if(used_symbols & t) continue;

for(int e=0;e<nr_solid_edges;e++) {
if(step==solid_edge_set_in[e] && !solid_okay[z[solid_edge_set_out[e]]][i]) goto skip_this_symbol;
}
for(int e=0;e<nr_dashed_edges;e++) {
if(step==dashed_edge_set_in[e] && !dashed_okay[z[dashed_edge_set_out[e]]][i]) goto skip_this_symbol;
}

z[step]=i;
used_symbols |= t;
find_z_value_backtracking_algorithm(step+1);
used_symbols ^= t;
z[step]=0;

skip_this_symbol: ;
}
}

int main() {
for(int i=0;i<15;i++) { z[i]=0; }

for(int i=0;i<16;i++) {
for(int j=0;j<16;j++) {
solid_okay[i][j]=check_solid_line(i,j);
dashed_okay[i][j]=check_dashed_line(i,j);
}
}

printf("okay solid pairs:\n");
for(int i=1;i<=16;i++) {
for(int j=1;j<=16;j++) {
printf("%d ",solid_okay[i][j]);
}
printf("\n");
}
printf("\n");

printf("okay dashed pairs:\n");
for(int i=1;i<=16;i++) {
for(int j=1;j<=16;j++) {
printf("%d ",dashed_okay[i][j]);
}
printf("\n");
}
printf("\n");

find_z_value_backtracking_algorithm(0);
return 0;
}

-
You mean unique up to permutations of $\{1,2,3,4\}$? –  joriki Sep 13 '12 at 7:41
No, just plain old unique (we can't permute the elements because of the "largest terms are equal for dashed lines" property). –  Douglas S. Stones Sep 13 '12 at 7:45
Ah, sorry, I somehow missed that part. In any case, +1 for the effort you put into the answer. –  joriki Sep 13 '12 at 9:30

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!

-