Teste sua Lógica: ordene 1,3,4,6,8,2,10,5,7,9?

Question

Preciso dessa sequencia ordenada em no máximo 5 trocas de posições dos números. Favor descrever cada troca, por exemplo:
sequencia original: 1,3,4,6,8,2,10,5,7,9
1a troca : 1,3,4,6,5,2,10,8,7,9 . . .

Quero agradecer à todos pela ajuda, se alguém souber se é possível resolver esse problema em 5 trocas vai ganhar 10 pontos!!!

Answer 1

=== Resposta Simples ===
Em cada linha estão marcados com colchetes os números que estarão com suas posições trocadas na linha seguinte.

Original:
1, 3, 4, 6, [8], 2, 10, [5], 7, 9

1ª troca:
1, 3, 4, 6, 5, 2, 10, 8, [7], [9]

2ª troca:
1, 3, 4, 6, 5, 2, [10], 8, 9, [7]

3ª troca:
1, 3, [4], [6], 5, 2, 7, 8, 9, 10

4ª troca:
1, [3], [6], 4, 5, 2, 7, 8, 9, 10

5ª troca:
1, [6], 3, 4, 5, [2], 7, 8, 9, 10

Final:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

=== Resposta Completa ===
(Respondendo à questão nos detalhes adicionais )

NÃO é possivel resolver com menos de 6 movimentos.
Veja por quê:
- Há um elemento na posição (1)
- Os demais formam três grupos circulares:
Grupo um: 8 e 5 (dois elementos)
Grupo dois: 10, 9 e 7 (três elementos)
Grupo três: 3, 4, 6, e 2 (quatro elementos)

Cada grupo de N elementos precisa de N - 1 trocas para ser ordenado. É fácil mostrar por quê:
- Para um grupo de 2 elementos isto é óbvio;
- Um grupo de três elementos, após uma troca, se torna um grupo de dois elementos e um na posição;
- Um grupo de N elementos, após uma troca, se torna um grupo de N - 1 elementos e um na posição.

Grupos de 4 elementos ou mais podem seguir um caminho diferente (mais elegante): ser separados em grupos menores. Exemplo: na sua seqüencia, trocando o 3 e o 6, o grupo (3, 4, 6, 2) se torna os grupos (6, 2) e (4,3). Note que transformar um grupo grande em dois menores não reduz o número necessário de trocas.

Portanto, a sua seqüencia precisará de:
(2 - 1) + (3 - 1) + (4 - 1) = 1 + 2 + 3 = 6 trocas!


== Veja esta solução, muito elegante ==

Seqüencia inicial:
1, 3, 4, 6, 8, 2, 10, 5, 7, 9

Reduzindo o grupo de 4 a dois grupos de 2:
1, 6, 4, 3, 8, 2, 10, 5, 7, 9

Reduzindo o grupo de 3 a um grupo de 2 e um na posição:
1, 6, 4, 3, 8, 2, 7, 5, 10, 9

Resolvendo os 4 grupos de 2 restantes:
1, 6, 4, 3, 8, 2, 7, 5, 9, 10
1, 6, 4, 3, 5, 2, 7, 8, 9, 10
1, 2, 4, 3, 5, 6, 7, 8, 9, 10
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Answer 2

depois de queimar a mufa um tempo, tenho quase certeza q só é possível resolver o problema em seis trocas........
mas decidi fazer uma conta: se alguem quiser resolver por tentativas e erro......... quantas possibilidades de trocas existem?

para uma troca:
escolhe-se um número depois o outro... mas dah no mesmo se escolher o outro depois o um...
10x9/2 = 45 possibilidades

para 5 trocas:
ninguem vai desfazer a troca q acabou de fazer, então são...
45x44x44x44x44 = 168.664.320 possibilidades!!

conclusão: se só houver uma solução, é 3 vezes mais fácil acertar na mega-sena q resolver por tentativas.....

Answer 3

Note que não podemos fazer isso em 5 trocas. No entanto em seis sim, veja como:
Esta é a seqüencia original:
0: 1,3,4,6,8,2,10,5,7,9
Agora faremos as trocas:
O 8 pelo 5:
1: 1,3,4,6,5,2,10,8,7,9
O 3 pelo 4:
2: 1,4,3,6,5,2,10,8,7,9
O 4 pelo 6:
3: 1,6,3,4,5,2,10,8,7,9
O 6 pelo 2:
4: 1,2,3,4,5,6,10,8,7,9
O 10 pelo 7:
5: 1,2,3,4,5,6,7,8,10,9
E por ultimo, o 10 pelo 9:
6: 1,2,3,4,5,6,7,8,9,10

Esse problema remete para a teoria de permutações utilizada por Galói (Galoá em francês) para resolver equações polinomiais, ou justificar a não solução delas.
Usando a teoria de Galói poderemos proceder da seguinte forma:
X=(1,3,4,6,8,2,10,5,7,9) , este é o elemento que pretendemos permutar.
E estes:
a=(2 6 4 3)
b=(5 8)
c=(7 9 10)
Ou melhor a é o seguinte : o que ta no 2 vai pro 6, o do 6 vai pro 4, o do 4 vai pro 3 e o do 3 pro 2.
O b e o c são semelhantes.
Agora sendo:
a^(-1) = (2 3 4 6)
b^(-1) = (5 8)
c^(-1) = (7 10 9)
note que os números que aparecem em um não esta nos outros(!).
pronto agora basta fazer isto:
( ( a^(-1) ) ° ( b^(-1) ) ° ( c^(-1) ) ) ( X )
Onde " ° " é o que os matemáticos chamam de bola, o símbolo de composição de funções.

Isto realmente é difícil, mas muito interessante!

Answer 4

Primeira troca:
o dez pelo nove
1,3,4,6,8,2,9,5,7,10
Segunda troca:
o sete pelo nove
1,3,4,6,8,2,7,5,9,10
Terceira troca:
o cinco pelo oito
1,3,4,6,5,2,7,8,9,10
Quarta troca:
o três pelo quatro
1,4,3,6,5,2,7,8,9,10
Quinta troca:
o dois no lugar do quatro
1,2,3,6,5,4,7,8,9,10
Sexta troca:
seis pelo quatro
1,2,3,4,5,6,7,8,9,10

Em seis já está bom, né? Se eu conseguir em cinco vezes depois te falo.

Answer 5

Ordenar em ordem crescente:
Original: 1,3,4,6,8,2,10,5,7,9
1ª troca: 1,2,3,4,6,8,10,5,7,9
2ª troca: 1,2,3,4,5,6,8,10,7,9
3ª troca: 1,2,3,4,5,6,7,8,10,9
4ª troca: 1,2,3,4,5,6,7,8,9,10.

Em ordem decrescente não é possível.

Answer 6

Achei muito interessante a pergunta e os comentário que foram feitos mais acho que mereço os créditos pelo que vou demonstrar abaixo:
Sequência original:1,3,4,6,8,2,10,5,7,9
1º Mud: 1,3,4,6,8,2,5,7,9,10
2º Mud 1,3,4,6,2,5,7,8,9,10
3ºMud 1,3,4,2,5,6,7,8,9,10
4ºMud 1,2,3,4,5,6,7,8,9,10


EM APENAS QUATRO!!!ACHO QUE MEREÇO OS CRÉDITOS.

PARABÉNS PELA PERGUNTA.

Answer 7

Tô meio sem tempo porque meu expediente terminou..

Consegui com as seguintes alterações ( Os colchetes são os números que movi):


Original: 1,3,4,6,8,2,10,5,7,9

1º) 1,[2],4,6,8,3,10,5,7,9
2º) 1,2,4,6,8,3,[9],5,7,10
3º) 1,2,3,6,8,[4],9,5,7,10
4º) 1,2,3,6,8,4,7,5,[9],10
5º) 1,2,3,4,8,[6],7,5,9,10
Final) 1,2,3,4,[5],6,7,8,9,10

Perceba que a última movimentação que fiz foi na 5º vez!E fui o primeiro a
resolver corretamente...
Se puder me, me dê um crédito por isso!

Att:

Marcio
http://www.marciozim.palcomp3.com.br

Answer 8

1,2,3,4,5,6,7,8,9,10
1,3,2,4,5,6,7,8,9,10
1,4,2,3,5,6,7,8,9,10
1,5,2,3,4,6,7,8,9,10
1,6,2,3,4,5,7,8,9,10

Answer 9

boiei

Answer 10

eo nom entender...
:S