Exercícios algébricos simples de Combinatória

Posted on Fevereiro 28, 2009 por

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.

About these ads

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 tags , , , . ligação permanente.

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

  1. Vishal Lama diz:
    Março 8, 2009 às 4:07 pm

    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!

    Responder
    • Américo Tavares diz:
      Março 8, 2009 às 4:24 pm

      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:
    Março 10, 2013 às 3:36 pm

    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!

    Responder

Deixar uma resposta

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

Gravatar
WordPress.com Logo

Está a comentar usando a sua conta WordPress.com ( Log Out / Modificar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter ( Log Out / Modificar )

Facebook photo

Está a comentar usando a sua conta Facebook ( Log Out / Modificar )

Cancelar

Connecting to %s