Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'd like to know whether the following simple problem has been studied before and if any solution is known.

Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said to be (locally) connected if their coordinates differ by at most one (i.e., if drawn as squares, they share at least one corner point).

Now, one can try to connect the crumbs (their set as a whole) by permutating the lines and the columns of the grid. In other words, the goal is to come up with a permutation of the lines and a permutation of the columns so that any two crumbs in the resulting grid are connected by a chain of (locally) connected crumbs.

Question: is there always a solution?

I don't quite know how to attack it. For lack of a better idea, I have written a raw program that looks for solutions by brute force (it generates the permutations at random and checks whether the resulting grid has its crumbs connected). The program has so far always found solutions on smallish (10x10 or 7x14) grids, and larger grids are clearly out of reach of its simplistic strategy (it would take too long to stumble at random across a solution).

Here is an example of a grid solved by the program:

Initial grid (crumbs are denoted by X's, empty cells by dots):

   0 1 2 3 4 5 6 7 8 9 
 0 X . X X . X . X X .
 1 X . . . . X . . . .
 2 . . X . . . . X . X
 3 . X . . X . X . . X
 4 . . . X . . . . . .
 5 X X . . . X X . X .
 6 . . . X . . . . X .
 7 X . X . . X . . . .
 8 X . . . X . . X X .

Solution:

   6 1 4 7 8 2 9 3 5 0
 1 . . . . . . . . X X
 4 . . . . . . . X . .
 5 X X . . X . . . X X
 8 . . X X X . . . . X
 7 . . . . . X . . X X
 0 . . . X X X . X X X
 3 X X X . . . X . . .
 6 . . . . X . . X . .
 2 . . . X . X X . . .

Naturally, the problem can readily be generalized to any dimension d > 2. I suppose other generalizations could be considered.

Thanks in advance,

Yann David

NB: I cross-posted the question on CS theory stack exchange at http://cstheory.stackexchange.com/questions/9015/connecting-cells-by-line-and-column-permutations-in-a-finite-grid, I'm not aware of any way to connect the two questions.

share|improve this question
    
As a guess, a large square grid with crumbs along the main diagonal and a single crumb in the top-right corner may have no solution. –  Austin Mohr Nov 18 '11 at 1:33
1  
@AustinMohr: Your example of "crumbs" may be connected by a common permutation of the rows and columns. Rotate the top row to the bottom of the matrix and then rotate the first column around to become the last column. The off-diagonal entry is then adjacent to the diagonal entries. –  hardmath Nov 18 '11 at 15:10
    
@hardmath It appears you are correct. Perhaps some kind of rotation argument like you used here can be generalized. That is, if one could show that, for any board, there is a move that results in strictly fewer connected components, then every board would indeed be solvable. –  Austin Mohr Nov 18 '11 at 19:29
1  
Simultaneous crosspost is discouraged. –  Tsuyoshi Ito Nov 18 '11 at 20:22
    
A counterexample has at least 4 rows: It's clear that there is none on 1 or 2 rows (just permute all empty columns to the right). On 3 rows, apply a row permutation such that there is a crumb in the middle row. Now apply a column permutation such that the columns are sorted with respect to their column type as in this pattern: $$\begin{pmatrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0\end{pmatrix}$$ The resulting grid is always connected. (Note that certain column types may not be present, but this doesn't violate conectedness.) –  azimut Aug 30 '13 at 9:29

1 Answer 1

The answer to the question is "no". For a nice (non-constructive) proof, see the answer of David Eppstein at the crosspost on cstheory.SE.

share|improve this answer
    
For reasons of link rot and general policy, it would be better to: 1. Link to that answer in your answer; 2. Include the answer verbatim (possibly after asking for David Eppstein's permission). As-is, this answer is effectively link-only, which is discouraged. –  Lord_Farin Aug 30 '13 at 8:30
    
@Lord_Farin: 1.: done. 2.: Since the answer is on the stackexchange network, I think the chances are quite low to lose the linked answer, but not this discussion. For that reason, I feel it is better to send readers to the original answer than to put a verbatim copy here. –  azimut Aug 30 '13 at 8:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.