Exercícios algébricos simples de Combinatória

1. Diga se existe algum número natural menor que 10 tal que:

^{n\!}C_{n-2}=2^{n-2}-1.

Justifique.

2. Prove que

 ^{n\!}C_{k}=\dfrac{n-k+1}{k}\times ^{n\!}C_{k-1}

3. Determine n de modo a que se tenha

 ^{n+3\!}C_{n}-^{n+2\!}C_{n-1}=15(n+1)

4. Determine n de modo a que se tenha

 ^{n\!}C_{2}=136

Resolução

A fórmula das combinações  ^{n\!}C_{k} é  ^{n\!}C_{k}=\dfrac{n!}{k!(n-k)!}

1. Neste caso tem-se

^{n\!}C_{n-2}=\dfrac{n!}{(n-2)!(n-(n-2))!}=\dfrac{n(n-1)}{2}

Então

  \dfrac{n(n-1)}{2}=2^{n-2}-1

é  equivalente a

 n(n-1)=2^{n-1}-2\Leftrightarrow n^{2}-n=2^{n-1}-2\Leftrightarrow n^{2}=2^{n-1}-2+n

Por tentativas chegamos à solução inteira n=6 (por sinal a  única). Os primeiros casos, começando em n=9 e continuando no sentido descendente são:

9^{2}=81 e 2^{9-1}-2+9=263

8^{2}=64 e 2^{8-1}-2+8=134

7^{2}=49 e 2^{7-1}-2+7=69

que são valores diferentes. Mas

6^{2}=36 e 2^{6-1}-2+6=36

6^{2}=2^{6-1}-2+6=36

 

Verificação:

^{n\!}C_{n-2}=2^{n-2}-1

^{6\!}C_{6-2}=\dfrac{6(6-1)}{2}=15

2^{6-2}-1=15

Os restantes, também diferentes, são

5^{2}=25 e 2^{5-1}-2+5=19

4^{2}=16 e 2^{4-1}-2+4=10

3^{2}=9 e 2^{3-1}-2+3=5

2^{2}=4 e 2^{2-1}-2+2=2

1^{2}=1 e 2^{1-1}-2+1=0

2. Como

 ^{n\!}C_{k}=\dfrac{n!}{k!(n-k)!}

 e

 ^{n\!}C_{k-1}=\dfrac{n!}{(k-1)!(n-(k-1)!}=\dfrac{n!}{(k-1)!(n-k+1)!}

vem

 \dfrac{^{n\!}C_{k}}{^{n\!}C_{k-1}}=\dfrac{\dfrac{n!}{k!(n-k)!}}{\dfrac{n!}{(k-1)!(n-k+1)!}}

=\dfrac{(k-1)!(n-k+1)(n-k)!}{k(k-1)!(n-k)!}=\dfrac{n-k+1}{k}

Logo

 ^{n\!}C_{k}=\dfrac{n-k+1}{k}\times ^{n\!}C_{k-1}

3. Como

 ^{n+3\!}C_{n}=\dfrac{(n+3)!}{n!(n+2-n)!}

=\dfrac{(n+3)(n+2)(n+1)}{2!}=\dfrac{(n+3)(n+2)(n+1)}{2}

e

^{n+2\!}C_{n-1}=\dfrac{(n+2)!}{(n-1)!(n+2-(n-1))!}=\dfrac{(n+2)(n+1)n}{6}

a igualdade indicada é  equivalente, sucessivamente, a

\dfrac{(n+3)(n+2)(n+1)}{2}-\dfrac{(n+2)(n+1)n}{6}=15(n+1)

3(n+3)(n+2)-(n+2)n=90

2n^{2}+13n-72=0

As duas soluções  são:

\dfrac{-13+\sqrt{745}}{4},\dfrac{-13-\sqrt{745}}{4}

Como nenhuma é  inteira, não  tem solução  nos naturais, pelo que não  há  nenhum valor de n que verifique a condição indicada.

4.  Como

^{n\!}C_{2}=\dfrac{n!}{2!(n-2)!}=\dfrac{n(n-1)(n-2)!}{2\times 1\times (n-2)!}=\dfrac{n(n-1)}{2}

e

 \dfrac{n(n-1)}{2}=136

\Leftrightarrow n(n-1)=2\times 136\Leftrightarrow n(n-1)=272\Leftrightarrow n^{2}-n-272=0

A solução  positiva é

n=\dfrac{1+\sqrt{1+4\times 272}}{2}=17

A negativa exclui-se por esse facto.

Verificação:

^{17\!}C_{2}=\dfrac{17\times 16}{2}=136.

Observação de 1-3-2009: comentário suprimido.

Nota de 15-3-2008: nesta entrada pode ver um problema de nível um pouco mais avançado que prolonga o exercício 1 a todos os naturais, aproveitando o 1º. comentário.

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Combinatória, Exercícios Matemáticos, Matemática, Matemática-Secundário, Problemas com as etiquetas , , , . ligação permanente.

3 respostas a Exercícios algébricos simples de Combinatória

  1. Problem 1: We can, in fact, extend the problem statement to find all n \in \mathbb{N} such that the given equation is satisfied. And, our answer would still be the same, i.e. n = 6 is the only solution. Here’s why.

    As you showed, the equation given in the problem is equivalent to the equation n^2 = 2^{n-1} + n - 2. Now, using a simple induction, it can be shown that 2^{n-1} > n^2 and n - 2 > 0 for all n \geq 7. (Well, the second one doesn’t really require an inductive proof!) So, the right hand side of the above equation is strictly greater than the left hand side for all n \geq 7! After that, it is only a matter of checking the individual cases from n=1 to n=6. And, as you verified, n = 6 is the only solution, and we are done!

    • Thanks for your proof of the generalization.

      I solved the original problem as was stated to me. All these problems were taken from previous exam(s) for candidates to a University, as far as I know.

      A translation into English of the title of this post can be, I think, “Easy algebraic exercises in Combinatorics”

  2. Daúdo diz:

    I just want to thank for the comments you use to publish for better understanding of the exercise given. Thanks, all of you. Keep doing that!

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s