Ponder This Challenge - June 2009 - Value of expression regarding permutation

Ponder This Challenge:

Let π be a permutation on 14 elements. Define Ni as the minimal number of times the permutation π should be applied to get i back into its original place. What is the remainder, modulo 1299, of the sum over all possible 14! permutations of 4 to the power of the product of (2+the parity of Ni)? I.e, what is

As we will show in the solution, it can be computed almost on the back an envelope.

Update (06/01): Note that a fixed point (i -=> i) is considered odd (Ni=1, parity=1), and a transposition (i -=> j -=> i) is considered even (Ni=2, parity=0).

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  2+mod(Ni,2) is 2 for i in an even length cycle and 3 for i in an odd length cycle. Since 14 is even, there are an even number of elements in odd cycles and an even number of elements in even length cycles. So the product is:

  1. a multiple of 36 for permutations with mixed odd and even cycles;
  2. 214 for permutations with even-only cycles; and
  3. 314 for odd-only cycles.

  Since 1299 divides 436-1, the remainder modulo 1299 of 4x depends only on x modulo 36. So

  1. permutations with mixed odd-even cycles contribute 1;
  2. permutations with even-only cycles contribute 4**214 = 4**{mod (214,36)} (mod 1299) = 44 (mod 1299) = 256; and
  3. permutations with odd-only cycles contribute 4**314 = 4**{mod (314,36)} (mod 1299) = 49 (mod 1299) = 1045.

  Since the number of permutations with only odd cycles is the same as the number of permutations with only even cycles (Thanks to Vladeta Jovovic for suggesting this equality and to Eytan Sayag for the elegant proof) we have 256+1045 = 2 (mod 1299) from each pair so all together we get the sum of 14! (mod 1299) = 648.

  Proving the equivalence between permutation of odd-only cycles and even-only cycles can be shown by writing the first in canonical form (sorting each cycle to start with the biggest element and sorting the cycles by their first element in descending order); then pairing them (if n is even, the number of odd-cycles should be even) and moving the last value from the second cycle of each pair after the last value of the first cycle in the pair. It is easy to show that this transformation is one-to-one from permutation with odd-only cycles to permutation with even-only cycles.

Solvers

• Balakrishnan V. (05/29/2009 11:51 PM EDT)
• John T. Robinson (05/30/2009 05:12 PM EDT)
• Martin Thiim (05/31/2009 01:08 PM EDT)
• Hongcheng Zhu (06/01/2009 05:31 AM EDT)
• Daniel Chong Jyh Tar (06/01/2009 07:46 AM EDT)
• Vladimir Sedach (06/01/2009 08:53 AM EDT)
• Ionel Santa (06/01/2009 09:08 AM EDT)
• Christian Blatter (06/01/2009 09:41 AM EDT)
• Austin Shapiro (06/01/2009 02:14 PM EDT)
• Dan Dima (06/01/2009 04:30 PM EDT)
• Liubing Yu (06/01/2009 11:30 PM EDT)
• Sevag Papazian (06/02/2009 09:14 AM EDT)
• Michael Brand (06/02/2009 09:19 AM EDT)
• Nick Miller (06/02/2009 03:42 PM EDT)
• Amos Guler (06/02/2009 05:18 PM EDT)
• Pataki Gergely (06/02/2009 07:56 PM EDT)
• Joe DeVincentis (06/02/2009 08:52 PM EDT)
• Jochen Hoenicke (06/03/2009 10:20 AM EDT)
• Corey Cerovsek (06/03/2009 05:35 PM EDT)
• Albert Stadler (06/04/2009 08:57 AM EDT)
• Yu Zhangqiu (06/04/2009 12:12 PM EDT)
• Phil Muhm (06/04/2009 02:25 PM EDT)
• Rickard Björklund (06/04/2009 10:49 PM EDT)
• Eli Biham (06/05/2009 11:35 AM EDT)
• Andrew McFarland (06/06/2009 08:55 PM EDT)
• Alan Murray (06/08/2009 12:12 PM EDT)
• Clive Tong (06/09/2009 12:44 PM EDT)
• Jeff Steele (06/09/2009 09:06 PM EDT)
• Nicolas Laurent (06/10/2009 05:59 AM EDT)
• Ravi Shankar Ojha (06/10/2009 12:26 PM EDT)
• Adam Daire (06/10/2009 02:26 PM EDT)
• Daniel Bitin (06/11/2009 11:27 AM EDT)
• Edgardo Deza (06/14/2009 12:34 PM EDT)
• K (06/15/2009 12:50 PM EDT)
• arthik Tadinada (06/15/2009 12:50 PM EDT)
• Karl D'Souza (06/15/2009 04:49 PM EDT)
• John G. Fletcher (06/15/2009 10:14 PM EDT)
• Siva Dirisala (06/17/2009 11:56 AM EDT)
• Nyles Heise (06/18/2009 10:41 PM EDT)
• Boris Nikolaus (06/19/2009 01:53 PM EDT)
• Renato Fonseca (06/20/2009 02:58 PM EDT)
• Fabio Filatrella (06/21/2009 01:00 PM EDT)
• Adriana Clerici (06/23/2009 11:49 AM EDT)
• Bojan Basic (06/24/2009 11:33 PM EDT)
• Thomas Rohr (06/25/2009 11:19 AM EDT)
• John Ritson (06/26/2009 07:55 AM EDT)
• Jason L. (06/29/2009 10:22:20 AM EDT)
• Larry Rolen (06/30/2009 12:25 PM EDT)
• Alex Furger (07/01/2009 03:49 AM EDT)