Arruma Esta Prateleira

 

A arrumação ordenada dos livros na prateleira de uma biblioteca é uma tarefa enfadonha, daí que a bibliotecária se tenha sempre preocupado em fazê-lo da forma mais eficiente.

Ela descobriu que a melhor forma de conseguir a ordem desejada era através de um processo em que permutava dois livros de cada vez. Quer dizer, ela retirava dois livros da prateleira e voltava a  arrumá-los na ordem inversa.

Quantas permutas, teria ela de efectuar para colocar os volumes da enciclopédia representados na figura pela ordem 123456789?

Qual seria o processo mais eficaz se os livros estivessem colocados pela ordem 457681923?

 

 

 

Solução...?

Como a bibliotecária considerava a tarefa de arrumação dos livros enfadonha, ela encontrou uma forma de conseguir a ordem desejada dos livros, que consistia em permutar dois livros de cada vez .

Para facilitar a resolução deste problema, o melhor é escrever a ordem desejada dos livros por cima da ordem dada:

Ordem desejada        1  2  3  4  5  6  7  8  9

Ordem dada              6  5  7  1  8  9  3  2  4

Como é possível verificar em cima, os livros 3 e 7 estão na posição um do outro, vamos representar esta permutação por (3 7), e assim ao trocá-los estes ficam colocados correctamente.

Em relação aos outros livros, verificamos que não são tão fáceis de colocar correctamente, verificámos que:

· 6 está na posição do 1

· 1 está na posição do 4

· 4 está na posição do 9

· 9 está na posição do 6

Sendo assim são apenas os livros 1, 4, 6, 9 que precisam de ser trocados entre si. Os livros podem ser postos correctamente com 3 permutas, sendo estas (4 9), (1 4) e, por fim, (6 1).

De maneira análoga, se colocam os restantes livros correctamente, visto que:

· 5 está na posição do 2

· 2 está na posição do 8

· 8 está na posição do 5

Os livros podem ser colocados nas posições correctas através das permutações (2 8) e (5 2).

Assim os volumes das enciclopédias foram colocados nas posições correctas, fazendo as permutações:

(3 7)(4 9)(1 4)(6 1)(2 8)(5 2 ).

É importante salientar que esta forma não é única, mas o número mínimo de movimentos é 6.

Aplicando o mesmo procedimento à segunda disposição, temos:

Ordem desejada      1  2  3  4  5  6  7  8  9

Ordem dada            6  5  7  1  8  9  3  2  4

E a solução final vai ser : (1 6)(4 1)(2 8)(5 2)(3 9)(7 3), sendo mais uma vez o 6, o número mínimo de permutações.

publicado por recursosescolares às 17:24