On Wed, Jan 01, 2003 at 01:02:58PM -0800, artist google wrote: > Hi, > I have this puzzle. > Given N numbers, N>4, you have to sort the numbers. > The only operation permitted is you can rotate any > sequencial 4 numbers in reverse order. or you can > roate the entire list sequencially. > > How do u approach this??
I don't think this is possible. Define the number of 'inversions' of a sequence of numbers the number of pairs for which the larger preceeds the smaller (this is the number of pairs which have to swap to get to the final, sorted, configuration). Define the 'parity' of the sequence as the even- or oddness of the number of inversions. Consider the sequence: [A B C D E], for some number A, B, C, D and E. There are just three operations possible, giving the sequences [E D C B A], [D C B A E] and [A E D B C]. Note that none of the operations changes the parity of the sequence. Note that [2 1 3 4 5] has an odd parity, while the parity of [1 2 3 4 5] is even. But if no operation can change the parity, there's no way of going from [2 1 3 4 5] to [1 2 3 4 5]. Abigail
