wu :: forums
« wu :: forums - Sorting a Matrix »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 5:25am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Eigenray, ThudnBlunder, Icarus, william wu, towr, SMQ, Grimbal)
   Sorting a Matrix
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Sorting a Matrix  (Read 5409 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Sorting a Matrix  
« on: Apr 9th, 2013, 11:32pm »
Quote Quote Modify Modify

A matrix MxN contains a permutation of numbers 1, 2, ..., MN.
 
You are allowed to perform a sequence of the following transformations of the matrix: choose any 2x2 sub-matrix, and rotate the content of the cells clockwise by 90 degrees.
 
What are the necessary and sufficient conditions of the matrix in order to be able to transform it to a natural sorted row-major order (the first row contains numbers 1, ..., N; the second - N+1, ..., 2N; etc.)
 
 
Source: Inspired by Croatian On-line Olympiad in Informatics (past).
 
I don't know the answer.
« Last Edit: Apr 10th, 2013, 12:29am by Barukh » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Sorting a Matrix  
« Reply #1 on: Apr 10th, 2013, 6:43am »
Quote Quote Modify Modify

I would say

It is possible if
- M=0 or N=0
- M=1 or N=1 and the array is already sorted
- M=2 and N=2 and the array is a rotation of the sorted array
- all sizes larger than 2x2

 
PS: not sure about 2x3, though.
« Last Edit: Apr 10th, 2013, 6:50am by Grimbal » IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 2084
Re: Sorting a Matrix  
« Reply #2 on: Apr 11th, 2013, 8:16am »
Quote Quote Modify Modify

on Apr 10th, 2013, 6:43am, Grimbal wrote:
PS: not sure about 2x3, though.

2x3 is not possible; only 120 of the possible 720 permutations are solvable. I'm working on classifying them now. All larger sizes are indeed solvable.
 
--SMQ
IP Logged

--SMQ

Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Sorting a Matrix  
« Reply #3 on: Apr 11th, 2013, 8:34am »
Quote Quote Modify Modify

Yep.  In the meantime I did a computer search and found the same result.
 
But I haven't found a simple rule that tells whether a position is possible or not.
 
Now that I think of it, the 120 out of 720 would suggest a formula that must equal 0 (mod 6).
« Last Edit: Apr 11th, 2013, 8:34am by Grimbal » IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 2084
Re: Sorting a Matrix  
« Reply #4 on: Apr 11th, 2013, 9:07am »
Quote Quote Modify Modify

on Apr 11th, 2013, 8:34am, Grimbal wrote:
Now that I think of it, the 120 out of 720 would suggest a formula that must equal 0 (mod 6).

In fact, looking at just one of the rows (of three elements), all 120 possible arrangements of that row occur in the set of solvable permutations--each paired with a unique arrangement of the other row.
 
--SMQ
« Last Edit: Apr 11th, 2013, 9:08am by SMQ » IP Logged

--SMQ

Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Sorting a Matrix  
« Reply #5 on: Apr 12th, 2013, 4:14pm »
Quote Quote Modify Modify

Nice find.  I printed out the solutions in order, but I didn't notice that pattern.
 
Looking further into it, it seems you can choose the value of any 3 cells, it leaves exactly one valid possibility for the 3 remaining cells.
 
It is a set of permutations where 2 permutations differ by at least 4 values.
« Last Edit: Apr 13th, 2013, 12:55am by Grimbal » IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Sorting a Matrix  
« Reply #6 on: Apr 13th, 2013, 10:59am »
Quote Quote Modify Modify

on Apr 11th, 2013, 8:16am, SMQ wrote:

All larger sizes are indeed solvable.
 
--SMQ

Got a proof?
 
The 2x3 case suggests the following formulation in terms of group theory: Given a permutation group of 6 elements (formally: symmetric group S6), and 2 elements of the group a = (1 2 3 4), b = (3 4 5 6), what is the size and structure of the subgroup, generated by these 2 elements?
 
Note that for the 2x4 case we add another element c = (5 6 7 8), and then 3 elements a, b, c generate the whole group S8. What is the fundamental difference between these two cases? I am pretty sure that group theory methods have answers to these questions… Trying to figure out.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Sorting a Matrix  
« Reply #7 on: Apr 13th, 2013, 1:42pm »
Quote Quote Modify Modify

There is no fundamental difference, except that you have more freedom, now enough to build every permutation.
 
You have to think like with a Rubik's cube:
 
Let's see for the 2x4 matrix
  1 2 3 4
  5 6 7 8
and name the operations (numbers refer to cells, not value transformations):
  A = 1->2->6->5->1
  B = 2->3->7->6->2
  C = 3->4->8->7->3
and
  A' = A3 (=A-1)
  B' = B3
  C' = C3
 
You can see that the operations (apply from left to right)
C'BAB'CBA'BB
tansform the matrix to
  1 6 3 4
  5 2 7 8
 
You can see that 6 and 2 are switched.  By composition you can switch any 2 cells.  And from there you can build every permutation.
 
A similar construct works for the 9x9 matrix.
« Last Edit: Apr 14th, 2013, 4:42am by Grimbal » IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 2084
Re: Sorting a Matrix  
« Reply #8 on: Apr 13th, 2013, 2:14pm »
Quote Quote Modify Modify

on Apr 13th, 2013, 10:59am, Barukh wrote:
Got a proof?

I have a constructive "proof", even. ;)
 
For 2xN (N >= 4), given 2x4: work from one end to the other until only a 2x4 segment remains, then solve it. Since any 2x4 segment can be placed in any arbitrary configuration it is always possible to move the last two unsolved numbers into position.
 
For 3x3, given two diagonally overlapping 2x2 squares can be placed in any arbitrary configuration: first solve two opposite corners, then solve the remaining 7 cells using the given.
 
For MxN (M, N >= 3), given 3x3: work toward one corner, solving one edge of the unsolved rectangle until only a 3x3 region remains, then solve it. Since any 3x3 segment can be placed in any arbitrary configuration, it's always possible to move all the numbers along an edge of length >= 3 into position.
 
--SMQ
IP Logged

--SMQ

Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board