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 \gcd(7,11)=1, o maior inteiro que não se escreve como 7a+11b com a,b\ge0 é
7\cdot11 - 7 - 11 = 77 - 18 = 59.

Passo 3

Note que se um número N é representável, então
N = 7a + 11b \quad\Longrightarrow\quad N+7 = 7(a+1) + 11b,
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:
60 = 7\cdot7 + 11\cdot1,\quad 61 = 7\cdot4 + 11\cdot3,\quad 62 = 7\cdot1 + 11\cdot5
63 = 7\cdot9 + 11\cdot0,\quad 64 = 7\cdot6 + 11\cdot2,\quad 65 = 7\cdot3 + 11\cdot4,\quad 66 = 7\cdot0 + 11\cdot6.
Como 60,61,…,66 são representáveis e o conjunto é fechado sob “+7”, todo inteiro \ge60 também é representável.

Resposta

A maior quantidade de balas que não pode ser comprada é 59.

Exercícios relacionados