(Carnegie Mellon Informatics and Mathematics - CMIMC - 2013 - modificada) O número de soluções inteiras e não negativas de x_{1}, x_{2}, x_{3}, \ldots, x_{12} que satisfaz a inequação x_{1}+x_{2}+x_{3}+\ldots+x_{12} \leq 17 pode ser escrito da forma \binom{a}{b}, onde a \geq 2 b. Sobre o valor de (a+b) podemos afirmar que é um número:
a) par
b) primo
c) divisível por 3
d) quadrado perfeito
e) menor do que 40

Passo 1

O enunciado dá que x_{1},x_{2},\dots,x_{12} são inteiros não negativos e pede o número de soluções da inequação
x_{1}+x_{2}+\cdots+x_{12}\leq 17.
Ele afirma ainda que esse número pode ser escrito na forma \binom{a}{b} com a\ge 2b, e pergunta qual das alternativas sobre o valor de (a+b) é verdadeira:
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 x_i é no máximo 17, posso introduzir uma variável não negativa extra s que representa a “folga” restante e escrever
x_{1}+x_{2}+\cdots+x_{12}+s=17,
com s\ge 0 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 13 variáveis não negativas (os doze x_i mais s) cuja soma é 17.

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
y_{1}+y_{2}+\cdots+y_{m}=n
é
\binom{n+m-1}{m-1}.
Intuição simples: imagine n estrelas alinhadas; para dividir em m caixas precisa colocar m-1 barras entre as estrelas ou nas extremidades. O número de maneiras de escolher as posições das m-1 barras entre as n+m-1 slots é \binom{n+m-1}{m-1}. (Exemplo pequeno: para m=3,n=2 as soluções de y_1+y_2+y_3=2 são 6 e a fórmula dá \binom{2+3-1}{3-1}=\binom{4}{2}=6.)
Aplicando aqui com m=13 e n=17 obtemos o número de soluções
\binom{17+13-1}{13-1}=\binom{29}{12}.

Passo 4

Verificação da condição a\ge 2b e escolha de a,b.
Pela expressão acima podemos tomar a=29 e b=12. Verifico a condição:
a\ge 2b \quad\Longleftrightarrow\quad 29\ge 2\cdot 12=24,
o que é verdade. (A outra escrita equivalente por simetria seria \binom{29}{17}, mas aí b=17 não satisfaz 29\ge 2\cdot 17.)
Então a+b=29+12=41.

Passo 5

Análise das alternativas sobre a+b=41.
  • Par? 41 é ímpar, logo a) é falsa.
  • Primo? Precisamos checar se 41 tem divisores inteiros além de 1 e 41. Testando divisores primos até \sqrt{41}<7: 2\nmid 41, 3\nmid 41 (resto 2), 5\nmid 41, 7\nmid 41. Não há divisores, logo 41 é primo — b) é verdadeira.
  • Divisível por 3? Não (resto 2), então c) falsa.
  • Quadrado perfeito? 6^2=36<41<49=7^2, logo não é quadrado — d) falsa.
  • Menor do que 40? 41 não é menor que 40 — e) falsa.

Resposta

(b)

Exercícios relacionados