Um amigo lhe diz que é capaz de ordenar qualquer conjunto de 6 números com no máximo 8 comparações. O seu amigo está falando a verdade ou mentindo? Justifique.
Passo 1
Então, o exercício diz que um amigo afirma que consegue ordenar qualquer conjunto de 6 números usando no máximo 8 comparações. A gente vai usar conceitos de ordenação e teoria das comparações para descobrir se ele está falando a verdade ou se está mentindo.
Passo 2
Primeiro, vamos entender o que significa ordenar números com comparações. Em algoritmos de ordenação, como o famoso “bubble sort” ou “quick sort”, a gente compara pares de números para decidir qual vem antes. Mas tem um limite mínimo de comparações necessárias para garantir que qualquer conjunto de números seja ordenado.
Passo 3
Esse limite mínimo pode ser encontrado calculando o logaritmo de base 2 do fatorial do número de elementos a serem ordenados. Matemática básica nos diz que para ordenar
elementos, a gente precisa de pelo menos
comparações no pior caso.
Passo 4
No caso desse exercício, temos
. Então, vamos calcular
e depois
:
Isso significa que precisamos de, no mínimo, cerca de 9.49 comparações. Como não dá para fazer uma parte de comparação, arredondamos para cima, resultando em 10 comparações necessárias.
Passo 5
Como o amigo está dizendo que consegue ordenar com no máximo 8 comparações, e vimos que são necessárias pelo menos 10 comparações, isso mostra que a afirmação dele é impossível de acordo com a teoria das comparações em ordenação.
Resposta
O amigo está mentindo. É necessário, no mínimo, 10 comparações para ordenar qualquer conjunto de 6 números.