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 6! = 6 times 5 times 4 times 3 times 2 times 1 = 720 . Então, vamos calcular log2(720) approx 9.49 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.

Exercícios relacionados