Re: [obm-l] combinatoria

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Sat, Sep 21, 2002 at 02:28:22PM -0300, adr.scr.m wrote:
> estou com uma duvida nessa questao,porque eu 
> fiz usando o 1ºlema de Kaplansky,e meu 
> professor disse que nao pode:
> (IME-75/76) Considere uma turma com n 
> alunos,numerados de 1 a n.Deseja-se 
> organizar uma comissao de 3 alunos.De 
> quantas maneiras pode ser formada esta 
> comissao,de modo que nao facam parte da 
> mesma 2 ou 3 alunos designados por numeros 
> consecutivos ?
> []'s.
> Adriano.

Eu contaria todas as comissões, o que dá binomial(n,3) = n(n-1)(n-2)/6,
e depois excluiria as da forma j,k,k+1. Para contá-las, eu primeiro
escolho k (temos (n-1) valores possíveis) e depois j ((n-2) valores
possíveis), o que dá (n-1)(n-2); note entretanto que as n-2 comissões
da forma i,i+1,i+2 foram eliminadas duas vezes (j=i,k=i+1 e j=i+2,k=i)
e isso deve ser corrigido.

Assim, temos

n(n-1)(n-2)/6 - (n-1)(n-2) + (n-2) = (n-2)(n(n-1) - 6(n-2))/6

o que dá os valores certos para n=2,3,4 (0), n=5 (1) e n=6 (4).
Como a resposta obviamente é um polinômio de grau <= 3 estes 5 testes
são bem convincentes. :-)

[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================