Q2 - Sejam as letras A, E, I, M, O, T, U. Consideram-se todas as palavras de 7 letras que podem ser formadas usando cada uma dessas letras exatamente uma vez (ou seja, todas as permutações das sete letras). Ordene essas palavras em ordem alfabética crescente. Qual é a 2117.
palavra dessa lista? Justifique sua resposta mostrando o método ou os cálculos utilizados.
Passo 1
O enunciado dá as letras
e pede: considerar todas as palavras de
letras formadas usando cada letra exatamente uma vez (todas as permutações das sete letras), ordenar essas palavras em ordem alfabética crescente e achar qual é a
palavra dessa lista. Informações relevantes: todas as permutações têm comprimento
; a ordem alfabética usada é a usual entre as letras dadas:
. O problema exige que mostremos o método e os cálculos utilizados.
Passo 2
Entender o número total de permutações e como se organiza a lista em blocos. Se temos
letras distintas, o número de permutações é
Aqui
, então o total é
Quando ordenamos lexicograficamente (alfabeticamente) todas as permutações, as palavras que começam por uma mesma letra aparecem em um bloco contíguo. O tamanho desse bloco, quando fixamos a primeira letra, é o número de permutações das
letras restantes:
Portanto, na lista ordenada, há
palavras começando por
, depois
começando por
, e assim por diante.
Passo 3
Estratégia geral (explicação didática do método): para encontrar a
palavra (aqui
), procedemos posição a posição (primeira letra, segunda letra, …) decidindo qual letra ocupa cada posição. Para decidir a letra da posição
, dividimos
em blocos de tamanho
; o quociente indica qual letra (na ordem alfabética entre as ainda disponíveis) ocupa a posição. Depois atualizamos
subtraindo os blocos anteriores e repetimos com o número de permutações das letras restantes. Formalmente, se sobraram
letras para preencher e queremos a posição local
(rank entre
e
), cada escolha fixa um bloco de tamanho
.
Vou aplicar isso passo a passo com
. Sempre que eu usar ‘índice’ abaixo, é no sentido zero-based: índice
é a primeira letra disponível em ordem alfabética, índice
é a segunda, etc. E sempre que eu calcular um quociente eu usarei a fórmula
e depois atualizo
.
Passo 4
Decidindo a primeira letra. Temos
letras disponíveis e bloco por letra de tamanho
. Calculo o índice:
As letras disponíveis em ordem são
. O índice
(zero-based) corresponde à letra
. Portanto a primeira letra é
.
Atualizo o rank dentro do bloco das palavras que começam por
:
Agora procuramos a
palavra entre as que começam por
.
Passo 5
Decidindo a segunda letra. Sobram as letras
(em ordem) — repare que tirei o
. Aqui
e cada escolha de segunda letra gera
permutações das restantes. Calculo:
Na lista
o índice
corresponde à letra
. Então a segunda letra é
.
Atualizo
:
Agora procuramos a
palavra entre as que começam por
.
Passo 6
Decidindo a terceira letra. Sobram
. Aqui
e cada escolha de terceira letra gera
permutações das restantes. Calculo:
Na lista
o índice
corresponde à letra
. Logo a terceira letra é
.
Atualizo
:
Agora procuramos a
palavra entre as que começam por
.
Passo 7
Decidindo a quarta letra. Sobram
. Aqui
e cada escolha gera
permutações das restantes. Calculo:
Índice
corresponde à primeira letra disponível, que é
. Então a quarta letra é
.
Atualizo
:
Agora procuramos a
palavra entre as que começam por
.
Passo 8
Decidindo a quinta letra. Sobram
. Aqui
e cada escolha gera
permutações das restantes. Calculo:
Na lista
o índice
corresponde à letra
. Então a quinta letra é
.
Atualizo
:
Agora procuramos a
palavra entre as que começam por
(ou seja, a primeira entre essas).
Passo 9
Decidindo a sexta e sétima letras. Sobram
e
. Para a sexta letra cada escolha gera
permutação da última posição. Calculo:
índice
corresponde à letra
. Então a sexta letra é
. A última letra será a que sobra,
.
Montando tudo: primeira
, segunda
, terceira
, quarta
, quinta
, sexta
, sétima
. A palavra é
.
Resposta
IUOATEM