(Carnegie Mellon Informatics and Mathematics - CMIMC - 2013 - modificada) O número de soluções inteiras e não negativas de
que satisfaz a inequação
pode ser escrito da forma
, onde
. Sobre o valor de
podemos afirmar que é um número:
a) par
b) primo
c) divisível por 3
d) quadrado perfeito
e) menor do que 40
a) par
b) primo
c) divisível por 3
d) quadrado perfeito
e) menor do que 40
Passo 1
O enunciado dá que
são inteiros não negativos e pede o número de soluções da inequação
Ele afirma ainda que esse número pode ser escrito na forma
com
, e pergunta qual das alternativas sobre o valor de
é verdadeira:
a) par
b) primo
c) divisível por 3
d) quadrado perfeito
e) menor do que 40
a) par
b) primo
c) divisível por 3
d) quadrado perfeito
e) menor do que 40
Passo 2
Transformação da inequação em equação usando uma variável folga.
Se a soma dos doze é no máximo
, posso introduzir uma variável não negativa extra
que representa a “folga” restante e escrever
Se a soma dos doze
com
inteiro. Assim cada solução da inequação corresponde a uma solução não negativa da equação acima (e vice-versa). Agora temos
variáveis não negativas (os doze
mais
) cuja soma é
.
Passo 3
Contagem por “estrelas e barras” (explicação didática).
Fórmula básica: o número de soluções inteiras não negativas da equação
Fórmula básica: o número de soluções inteiras não negativas da equação
é
Intuição simples: imagine
estrelas alinhadas; para dividir em
caixas precisa colocar
barras entre as estrelas ou nas extremidades. O número de maneiras de escolher as posições das
barras entre as
slots é
. (Exemplo pequeno: para
as soluções de
são 6 e a fórmula dá
.)
Aplicando aqui com
e
obtemos o número de soluções
Passo 4
Verificação da condição
e escolha de
.
Pela expressão acima podemos tomar e
. Verifico a condição:
Pela expressão acima podemos tomar
o que é verdade. (A outra escrita equivalente por simetria seria
, mas aí
não satisfaz
.)
Então
.
Passo 5
Análise das alternativas sobre
.
- Par?
é ímpar, logo a) é falsa. - Primo? Precisamos checar se
tem divisores inteiros além de e . Testando divisores primos até : , (resto ), , . Não há divisores, logo é primo — b) é verdadeira. - Divisível por
? Não (resto ), então c) falsa. - Quadrado perfeito?
, logo não é quadrado — d) falsa. - Menor do que
? não é menor que — e) falsa.
Resposta
(b)