Solution to "The Permutation Puzzles"

​

All the claims are true.

​

The complicated transformation which produces the result has a number of unnecessary features.

 

We don't have to start with permutations, and we don't have to subtract N/2.

 

The two key factors are a simple fact about the vectors P1 and P2, and the rotation by 45 degrees.

 

To see what is going on, let us write our steps as follows:

​

        p1 = random permutation of 1 to n
        p2 = random permutation of 1 to n

        q1 = p1 - n / 2
        q2 = p2 - n / 2
        
        NOTE: the L2 norms of q1 and q2 are equal (the vectors have
        the same entries, though in different orders).

        r1 = c * q1 - s * q2
        r2 = s * q1 + c * q2

        dot = r1' * r2 
            = ( c * q1 - s * q2 )' * ( s * q1 + c * q2 )
            =   c * s * q1' * q1 + c * c * q1' * q2 
              - s * s * q2' * q1 - s * c * q2' * q2

        NOTE: angle = 45 degrees, so c = s, therefore...

            = c * c * ( q1'*q1 + q1'*q2 - q2'*q1 - q2'*q2 )

        NOTE: q1'*q2 = q2'*q1, by symmetry of dot products, therefore...

            = c * c * ( q1'*q1                   - q2'*q2 )

        NOTE: q1'*q1 is the square of the L2 norm of q1, and similarly for q2.

            = c * c * ( 0 )

            = 0
      
Thus, the crucial steps are that the translated vectors q1 and q2 have the same norm, which can easily be guaranteed if they have the same entries, though in different order; and that the sine and cosine of the rotation be equal (although this would also work for -45 degrees, for which c = -s, as well as 135 and 225 degrees.)

​

​

Last revised on 11 September 2009.