Suponha que temos selos de 4 e 7 centavos. Prove que é possível ter qualquer valor de postagem de 18 centavos ou mais usando somente selos.

Passo 1

Beleza, vamos lá! A gente tem um problema onde só pode usar selos de 4 e 7 centavos para fazer qualquer valor de postagem a partir de 18 centavos. O conteúdo envolvido aqui é sobre combinações de números inteiros e como podemos combinar os selos para atingir esses valores. Vamos precisar entender um pouco sobre equações lineares e o conceito de maior número que não pode ser formado por essas combinações.

Passo 2

Primeiro, vamos pensar em como combinar os selos. Queremos encontrar números inteiros não negativos $ x $ e $ y $ que satisfaçam a equação:
x
Onde $ N $ é o valor de postagem que queremos alcançar, que deve ser 18 ou mais.

Passo 3

A gente precisa garantir que há sempre uma combinação de $ x $ e $ y $ para qualquer $ N \geq 18 $. Para isso, vamos usar o conceito de número de Frobenius. Quando temos dois números que são coprimos (ou seja, o maior divisor comum deles é 1), o maior valor que não pode ser formado pela combinação deles é dado por:
x
No nosso caso, $ a = 4 $ e $ b = 7 $. Vamos verificar se eles são coprimos:
y
Como o N >= 18 é 1, podemos aplicar a fórmula.

Passo 4

Aplicando a fórmula do número de Frobenius:
F = 4 times 7 - 4 - 7 = 28 - 11 = 17
Isso significa que 17 é o maior valor que não pode ser formado usando selos de 4 e 7 centavos. Portanto, qualquer valor a partir de 18 centavos pode ser formado usando esses selos.

Passo 5

Para garantir, vamos ver alguns exemplos:
  • 18 centavos: $ 4 \times 2 + 7 \times 2 = 8 + 14 = 22 $ — Ops, esse deu acima. Vamos tentar outra combinação:
    $ 4 \times 3 + 7 \times 1 = 12 + 7 = 19 $ — Ainda não 18. Vamos ajustar:
    $ 4 \times 1 + 7 \times 2 = 4 + 14 = 18 $ — Pronto!
  • 19 centavos: Já vimos que $ 4 \times 3 + 7 \times 1 = 19 $.
  • 20 centavos: $ 4 \times 5 + 7 \times 0 = 20 $.
E assim por diante, sempre dá para ajustar os números de selos para chegar no valor desejado.

Resposta

Então, fica comprovado que é possível formar qualquer valor de postagem a partir de 18 centavos usando apenas selos de 4 e 7 centavos.

Exercícios relacionados