quarta-feira, 26 de dezembro de 2018

Permutações

Perguntava o Público na semana passada: se colocarmos por ordem alfabética todas as "palavras" de sete letras que se podem obter permutando as sete letras da palavra SETÚBAL, qual será a palavra que aparece na posição 2018ª?
O número total de permutações é 7! = 7x6! = 7x720 = 5040, e agora temos de imaginar como se colocam por ordem alfabética e qual surgirá na posição 2018.
Colocando as sete letras por ordem alfabética, obtemos ABELSTÚ, o que quer dizer que das 5040 palavras, as primeiras 720 começam por A, as 720 seguintes, nas posições 721 a 1440, começam por B, as seguintes, nas posições 1441 a 2160, começam por E, etc. 2018 fica neste grupo, logo a palavra procurada começa por E.
A seguir, podemos procurar a segunda letra, dividindo este grupo em 6 grupos de comprimento 120, uma vez que 6! = 6x5! = 6x120, depois o grupo em que 2018 recair em 5 grupos de comprimento 24, etc.
Deixando um bocadinho de mistério para o leitor, a figura seguinte esquematiza todo o raciocínio, e dá o resultado: ETÚABSL.


Evidentemente que um computador resolve isto à força e com uma perna às costas:


É só experimentar.
Mas a ideia geral é que perante cada problema cada um deve olhar para os recursos (de conhecimentos e de computação) de que dispõe e procurar uma forma de o resolver.
Ou esperar pelo Público da próxima semana...