Abstract Algebra Abstract Algebra Math Forum

 May 23rd, 2011, 02: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,n-1,...,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(n-1)/2 as there are n(n-1)/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, 02: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 path-seeking: too many wrong turnings at EACH step! May 30th, 2011, 08:59 AM   #3
Member

Joined: May 2011

Posts: 90
Thanks: 1

Re: simple question, hard to deal with!

Quote:
 Originally Posted by Snoopy The question seems rather simple! Starting with 1,2,3,...,n we need to get the reversal order n,n-1,...,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. Wwe do 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?
I have the list for N=5.
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, 10: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, 09: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 bell-sequence (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 neighbour-bells then not even 119 perms can be sounded. SEVERAL non-neighbour 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 NON-NEIGHBOUR 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, 12:03 PM   #6
Math Team

Joined: Apr 2010

Posts: 2,780
Thanks: 361

Re: simple question, hard to deal with!

Quote:
 Originally Posted by gin palace Very glad you are finding this question FUN and INTERESTING!
That is a very enthusiastic interpretation of
Quote:
 Originally Posted by I I like the problem.
I suppose.

Quote:
 Originally Posted by You (2) If they swap ONLY neighbour-bells then not even 119 perms can be sounded. SEVERAL non-neighbour 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 NON-NEIGHBOUR 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
Why should I explain? Regardless if all this is true, what do you want me to conclude? Non-neighbour swaps don't interfere with the given problem. July 1st, 2011, 11: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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post shunya Elementary Math 2 March 12th, 2014 09:24 AM maple_leaf Elementary Math 9 May 25th, 2013 07:41 AM lenfromkits Calculus 4 November 23rd, 2011 11:27 AM GoldMember Advanced Statistics 3 April 5th, 2010 06:59 PM oswaldo Geometry 10 December 9th, 2009 09:54 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      