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

=== 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

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.....

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!

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.

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.

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.

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/

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

boiei

eo nom entender...

:S