Uma loja vende balas em pacotes de 7 e 11 unidades. Com esses pacotes, algumas quantidades de balas não podem ser compradas. No entanto, a partir de uma certa quantidade, todas as quantidades seguintes passam a ser possíveis. Qual é a maior quantidade de balas que não pode ser comprada? Justifique por que, a partir da quantidade seguinte, todas as demais podem ser obtidas usando apenas esses pacotes.
Passo 1
O enunciado pede a maior quantidade de balas que não pode ser obtida como soma de pacotes de 7 e 11 unidades. O conteúdo envolve combinações lineares inteiras não-negativas e o chamado problema de Frobenius (ou Chicken McNugget Theorem).
Passo 2
Como
, o maior inteiro que não se escreve como
com
é
Passo 3
Note que se um número
é representável, então
ou seja, o conjunto dos representáveis é fechado sob adição de 7. Logo, bastam sete valores inteiros consecutivos representáveis para garantir que tudo acima deles também seja representável.
Passo 4
Exibimos as combinações para os sete números consecutivos começando em 60:
Como 60,61,…,66 são representáveis e o conjunto é fechado sob “+7”, todo inteiro
também é representável.
Resposta
A maior quantidade de balas que não pode ser comprada é
.