My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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?
Snoopy is offline  
 
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!
MRWhy is offline  
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
gin palace is offline  
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.
Hoempa is offline  
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
gin palace is offline  
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.
Hoempa is offline  
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
gin palace is offline  
Reply

  My Math Forum > College Math Forum > Abstract Algebra

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 09:24 AM
Simple Mathematic yet hard maple_leaf Elementary Math 9 May 25th, 2013 07:41 AM
very simple for you, hard for me. lenfromkits Calculus 4 November 23rd, 2011 11:27 AM
Deal or no Deal winning strategy GoldMember Advanced Statistics 3 April 5th, 2010 06:59 PM
Two simple solutions for a hard geometry problem oswaldo Geometry 10 December 9th, 2009 09:54 PM





Copyright © 2019 My Math Forum. All rights reserved.