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.