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.

Exercícios relacionados

Faça um código em para gerar 10 números aleatórios (entre 1 e 50 ) e armazenar em um vetor. Apresente os números gerados na tela e depois organize o vetor com o método de ordenação BubbleSort. Ao final, apresente o vetor ordenado.
Faça um código para gerar 25 números aleatórios (entre 10 e 40 ) e armazenar em um vetor. Apresente os números gerados na tela e depois organize o vetor com o método de ordenação InsertionSort. Ao final, apresente o vetor ordenado.
Faça um programa em C para gerar apostas na Mega Sena com N dezenas (informada pelo usuário). Armazene os números gerados aleatórios no intervalo de 1 a 60 em um vetor. Lembre se que os N números precisam ser diferentes entre si, não podendo repetir o número adicionado no vetor.