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:
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:
No nosso caso, $ a = 4 $ e $ b = 7 $. Vamos verificar se eles são coprimos:
Como o
é 1, podemos aplicar a fórmula.
Passo 4
Aplicando a fórmula do número de Frobenius:
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.