
Abstract Algebra Abstract Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 23rd, 2011, 01:59 PM  #1 
Member Joined: Aug 2010 Posts: 32 Thanks: 0  simple question, hard to deal with!
The question seems rather simple! Starting with 1,2,3,...,n we need to get the reversal order n,n1,...,3,2,1 BY ONLY following these rules: 1 Only one transposition is allowed at each step; that is, for example, starting from 1,2,3 the next step towards the reversal can be 2,1,3 or 1,3,2 or 3,2,1. 2 No permutation can be repeated in between; that is, for example, if do these moves 1,2,3 > 2,1,3 > 2,3,1>1,3,2 , then my next move can not be 1,2,3 since we had this permutation before. Meet each permutation only ONCE! 3 Try to meet as many permutation as possible until we reach the reversal. At each step we get a permutation and we need to find a way that generates as many permutations as possible until we get the reversal. For example for n=3 one can meet all the 6 permutations and end up with the reversal. For n=4, my calculations show that we can find a way that uses all but one permutations once; so it gives us 23 permutation with the reversal at the end. What's the maximum number for n=5 and higher than that? Is there any algorithm to find such a path? One can change this problem into a graph theory problem. Consider all the permutations as the vertices and define any two vertices to be adjacent iff they differ in only one transposition. In this way we get a regular graph with each vertex of degree n(n1)/2 as there are n(n1)/2 different transpositions. Now the aforementioned problem is equivalent to finding a path of maximum length from the vertex 1,2,3,...,n to n,...,3,2,1. A simple parity argument shows us that such a path can not be Hamiltonian always. We have n! vertices which is an even number; therefore a Hamiltonian path from a vertex to its reversal needs doing n!1 number of transpositions, which is an odd number. Hence if there is a Hamiltonian path, the reversal must be an odd permutation. On the other hand we know that n,...,3,2,1 is odd iff [n/2] is an odd number iff n mod 4 = 2 or 3. Thus the existence of Hamiltonian path (or equivalently: being able to meet all the permutation once and ending up with the reversal) requires n mod 4 to be either 2 or 3. Is the converse true? For example 4 mod 4 = 0, and thus there is no way to meet all the permutations and reach 4,3,2,1; this shows that the path which meets 23 permutations is the longest one for n=4. Again since 5 mod 4 = 1, we don NOT expect a way that meets all the permutations once and ends up with 5,4,3,2,1; but there is a longest path, what is it? What is the maximum number of permutations one can meet until reaches 5,4,3,2,1? What's the answer in general case? 
May 24th, 2011, 01:40 AM  #2 
Newbie Joined: May 2011 Posts: 23 Thanks: 0  Re: simple question, hard to deal with!
I have an even simpler question Suppose we begin at 12345 and reach 54321 in 64 steps (as I have done by hand) my question is "Is that path unique?" This is a simpler question than "Is it the longest" It seems it can't be as there are zillions of paths 64 steps long (so who cares if 99.9999% of them do not get us to 54321) But my computer seems to think it is  as it canna find it by RANDOM pathseeking: too many wrong turnings at EACH step! 
May 30th, 2011, 07:59 AM  #3  
Member Joined: May 2011 Posts: 90 Thanks: 1  Re: simple question, hard to deal with! Quote:
There are 119 perms The missing one is 53421 But knowing the list is FAR FAR easier than finding an equation or iterative procedure that produces it  
June 22nd, 2011, 09:22 AM  #4 
Math Team Joined: Apr 2010 Posts: 2,780 Thanks: 361  Re: simple question, hard to deal with!
Bit of a bump, I have been trying to work on this too, though only for the 3 and 4 digit numbers. To me, there seems to be a bit of a pattern in the exchanged numbers. I'll try to show it in 3 examples: the underlined numbers are exchanged and produce the number below. Consider the examples as rings. I displayed the examples larger for the reading. The numbers in brackets next to example 1 is the "rank" of lowest possible permutation numbers of 123. I find it hard to describe in English. Example 1 (3 digits): 123 (1) 123 (1) 213 (3) 132 (2) 312 (5) 213 (3) 132 (2) 231 (4) 231 (4) 312 (5) 321 (6) 321 (6) Example 2 (3 digits): 123 132 231 213 312 321 Example 3 (4 digits): 1234 1243 1342 2341 2314 2413 3412 3421 3124 4123 4132 4231 (exception; middle 2 numbers exchanged) 4321 4312 4213 3214 3241 3142 2143 2134 2431 1432 1423 1324 (exception; middle 2 numbers exchanged) The exceptions could predict for for example N=5, when there is an exception. I don't think, solutions will be unique. I like the problem. There are some more patterns to spot. For example, if you would label the numbers in example 3 with the "ranks" like done in example 1. The ranks of number m and m+12 add up to 25 (m integer). Example: The ranks of number 1 and 13 add up to 25. Maybe, this all helps to find an algorithm to solve for 5 or more digits. 
June 28th, 2011, 08:49 AM  #5 
Member Joined: May 2011 Posts: 90 Thanks: 1  Re: simple question, hard to deal with!
Hello Hoempa Very glad you are finding this question FUN and INTERESTING! Here are some fascinating facts for you to explain: We have FIVE bellringers As usual they stand in a CIRCLE, each with their own bellrope to pull Their goal is to sound EVERY permutation of the 5 bells once only and end with the REVERSE bellsequence (perm) to the one they started with. (1)This is IMPOSSIBLE unless they, at times, switch the order of MORE THAN ONE pair of bells each change. If they switch ONLY ONE pair then there is ALWAYS AT LEAST ONE perm missing from the list when they reach the reverse of the perm they started with. (2) If they swap ONLY neighbourbells then not even 119 perms can be sounded. SEVERAL nonneighbour swaps are REQUIRED. (3) There are THOUSANDS of ways to do that  swap bells and get 119 perms EVERY ONE of them REQUIRES we swap NONNEIGHBOUR bells more than once (4) ANY of the perms can be the ONE that MUST be missing: all EXCEPT the one we start with! (5) And even if we pin daown the start to 5 NAMED bells in a GIVEN order there are hundreds of ways to get to to its reversal with max possible perms= 119 
June 28th, 2011, 11:03 AM  #6  
Math Team Joined: Apr 2010 Posts: 2,780 Thanks: 361  Re: simple question, hard to deal with! Quote:
Quote:
Quote:
 
July 1st, 2011, 10:43 AM  #7 
Member Joined: May 2011 Posts: 90 Thanks: 1  Re: simple question, hard to deal with!
We now have the solution for 6 bells


Tags 
deal, hard, question, simple 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
The better deal  shunya  Elementary Math  2  March 12th, 2014 08:24 AM 
Simple Mathematic yet hard  maple_leaf  Elementary Math  9  May 25th, 2013 06:41 AM 
very simple for you, hard for me.  lenfromkits  Calculus  4  November 23rd, 2011 10:27 AM 
Deal or no Deal winning strategy  GoldMember  Advanced Statistics  3  April 5th, 2010 05:59 PM 
Two simple solutions for a hard geometry problem  oswaldo  Geometry  10  December 9th, 2009 08:54 PM 