Prova de que não existe o maior número primo.

Esta semana, continuamos nossa jornada pelas demonstrações matemáticas. Hoje, faremos uma demonstração comum: provar que não existe um maior número primo. Como sempre, meu objetivo é explicá-las usando uma linguagem o mais simples possível e evitar notações matemáticas complexas. No entanto, antes disso, apresento o nosso tradicional quebra-cabeça lógico semanal.

Quebra-cabeça lógico

Você está em um prédio de 106 andares. Os andares são numerados de 0 a 105 (como na maioria dos países fora dos EUA). Você quer testar qual o andar mais alto de onde pode soltar um ovo com segurança dentro de uma caixa grande de penas no chão. Você sabe que um ovo solto do telhado quebrará e um solto do térreo sobreviverá. Você tem dois ovos para o experimento. Qual o menor número de vezes que você precisaria soltar o ovo no pior cenário possível?

A resposta e a solução aparecem no final da coluna.

Prova de que não existe o maior número primo.

Vou provar por contradição que não existe um maior número primo. Em outras palavras, vou refutar o oposto – que existe um maior número primo.

Vamos chamar o maior número primo de p_{_n} , ou seja, é o n-ésimo número primo. Vamos então rotular todos os números primos em ordem da seguinte forma:

_p₁ = 2, _p₂ = 3, _p₃ = 5, _p₄ = 7, … _pₙ = ?

Considere o número N da seguinte forma:

N = p ₁ ×p ₂ × p ₃ × p ₄ × … ×p _n +1.

Se N é primo, então nenhum primo menor deve dividi-lo exatamente. No entanto, se dividirmos qualquer primo até p _n por N, obteremos um resto de 1.Isso só pode ser explicado de duas maneiras possíveis:

1. O próprio N é primo, que deve ser maior que p _n .
2. Existe algum número primo maior que p _n que divide N sem deixar resto.

De qualquer forma, mostramos que existe algum primo maior que p _n .

Vamos analisar um número primo pequeno, por exemplo. Vou ver o que acontece se assumirmos que 31 é o maior número primo. Nesse caso:

N = 2×3×5×7×11×13×17×19×23×29×31 + 1 = 1.805.044.411.171

Usando uma calculadora de fatores primos, encontramos 1.805.044.411.171 = 1.061.729 x 1.700.099. Portanto, encontramos dois números primos maiores que 31: 1.061.729 e 1.700.099.

Para dar outro exemplo, suponha que 7 seja o maior número primo. Então N = 2 × 3 × 5 × 7 + 1 = 2¹¹. Fazendo um teste de fatoração em primos em 2¹¹, descobrimos que 2¹¹ é primo. Portanto, encontramos um número primo maior que 7.

Independentemente de qual número primo consideremos o maior, este método encontrará um número primo ainda maior.

Resposta ao enigma lógico

14

Eis como descobrir o andar mais alto em segurança com no máximo 14 quedas.

1. Solte o primeiro ovo do 14º andar. Se ele quebrar, teste os andares de 1 a 13, um de cada vez. O número máximo de tentativas necessárias, caso o ovo quebre, é 14 (1 com o primeiro ovo e 13 com o segundo). Caso contrário, volte ao passo 2.
2. Suba 13 andares, soltando o primeiro ovo do 27º andar. Se ele quebrar, teste os andares 15 a 26, um de cada vez. O número máximo de ovos necessários, caso ele quebre, é 14 (2 com o primeiro ovo e até 12 com o segundo). Caso contrário, volte para o passo 3.
3. Suba 12 andares, soltando o primeiro ovo do 39º andar. Se ele quebrar, teste os andares 28 a 38, um de cada vez. O número máximo de ovos necessários, caso ele quebre, é 14 (3 com o primeiro ovo e até 11 com o segundo). Caso contrário, vá para o passo 4.
4. Suba 11 andares, soltando o primeiro ovo do 50º andar. Se ele quebrar, teste os andares 40 a 49, um de cada vez. O número máximo de ovos necessários, caso ele quebre, é 14 (4 com o primeiro ovo e até 10 com o segundo). Caso contrário, vá para o passo 5.
5. Suba 10 andares e solte o primeiro ovo do 60º andar. Se ele quebrar, teste os andares 51 a 59, um de cada vez.Número máximo de gotas necessárias se quebrar = 14 (5 com o primeiro ovo e até 9 com o segundo). Caso contrário, vá para o passo 6.
6. Suba 9 andares, soltando o primeiro ovo do 69º andar. Se ele quebrar, teste os andares 61 a 68 um de cada vez. O número máximo de ovos necessários, caso ele quebre, é 14 (6 com o primeiro ovo e até 8 com o segundo). Caso contrário, vá para o passo 7.
7. Suba 8 andares, soltando o primeiro ovo do 77º andar. Se ele quebrar, teste os andares 70 a 76 um de cada vez. O número máximo de ovos necessários se ele quebrar é 14 (7 com o primeiro ovo e até 7 com o segundo). Caso contrário, vá para o passo 8.
8. Suba 7 andares, soltando o primeiro ovo do 84º andar. Se ele quebrar, teste os andares 78 a 83 um de cada vez. O número máximo de ovos necessários, caso ele quebre, é 14 (8 com o primeiro ovo e até 6 com o segundo). Caso contrário, vá para o passo 9.
9. Suba 6 andares, soltando o primeiro ovo do 90º andar. Se ele quebrar, teste os andares 85 a 89, um de cada vez. O número máximo de ovos necessários, caso ele quebre, é 14 (9 com o primeiro ovo e até 5 com o segundo). Caso contrário, vá para o passo 10.
10. Suba 5 andares, soltando o primeiro ovo do 95º andar. Se ele quebrar, teste os andares 91 a 94 um de cada vez. O número máximo de ovos necessários se ele quebrar é 14 (10 com o primeiro ovo e até 4 com o segundo). Caso contrário, vá para o passo 11.
11. Suba 4 andares, soltando o primeiro ovo do 99º andar. Se ele quebrar, teste os andares 96 a 98 um de cada vez. O número máximo de ovos necessários se ele quebrar é 14 (11 com o primeiro ovo e até 3 com o segundo). Caso contrário, vá para o passo 12.
12. Suba 3 andares, soltando o primeiro ovo do 102º andar. Se ele quebrar, teste os andares 100 e 101, um de cada vez. O número máximo de ovos necessários se ele quebrar é 14 (12 com o primeiro ovo e até 2 com o segundo). Caso contrário, vá para o passo 13.
13. Suba 2 andares, soltando o primeiro ovo do 104º andar. Se ele quebrar, teste no 103º andar. O número máximo de ovos necessários para quebrar é 14 (13 com o primeiro ovo e 1 com o segundo). Caso contrário, vá para o passo 14.
14. Suba um andar e solte o primeiro ovo do 105º andar. Se ele quebrar, o andar seguro mais alto é o 104º. Se ele sobreviver, o andar seguro mais alto é o 105º.

A estratégia geral para um prédio de n andares é encontrar o andar ideal para fazer a primeira entrega. Se o primeiro teste for bem-sucedido, você sobe a partir daí o mesmo número de andares menos um. Se o segundo teste for bem-sucedido, você sobe novamente um andar a menos do que subiu da última vez. Continue repetindo esse processo, subindo um andar a menos do que o incremento anterior entre os testes. Se um teste com o primeiro ovo falhar, use o segundo ovo para testar sistematicamente todos os andares entre os dois últimos testes, começando pelo andar mais baixo desse intervalo.

Observe que o aumento no número de andares segue a ordem n, n-1, n-2, ... 1. A soma de todos esses saltos é n(n+1)/2. O segredo é encontrar o menor valor inteiro possível de n onde a soma da série seja igual ou maior que o número de andares do prédio.

Por exemplo, vamos analisar um prédio de 500 andares (sem contar o térreo seguro) e calcular:

n(n+1)/2 = 500

n(n+1) = 1000

^n² + n - 1000 = 0

6; font-family: 'Open Sans', sans-serif; color: #313131 !important; ">Usando a fórmula de Pitágoras:

n = (-1 +/- √4001 )/2 =~ 31,13

No entanto, os andares têm valores inteiros. Portanto, arredondamos para n=32. Assim, no caso de um prédio de 500 andares (ou 501, se contarmos o térreo seguro), fazemos o primeiro teste a partir do 32º andar.