Re: [obm-l] Analise Combinatoria

["Paulo Santa Rita" <p_ssr@xxxxxxxxxxx>]

Ola Pessoal,

Em muitos problemas de Analise Combinatoria, como no caso abaixo, o 
enunciado faz algumas restricoes. Um caminho natural e que, quase sempre, 
conduz a uma solucao satisfatoria e considerar as restricoes
e conta-las separadamente ...

O total de comissoes com 3 alunos e : BINOM(N,3).

Desse total temos que retirar as restricoes. Vamos conta-las :

1) tres numeros consecutivos :
{1,2,3},{2,3,4}, ..., {N-2,N-1,N}
Evidentemente, N-2 casos
SUBTOTAL1 : (N-2) casos

2) dois numeros consecutivos :
{1,2) + Um escolhido entre {4,5,...,N} = N-3 casos
{N-1,N} + Um escolhido entre {1,2,...,N-3) = N-3 casos
SUBTOTAL2 : 2(N-3) casos

Pares : {2,3},{3,4},...,{N-2,N-1} -> (N-3) pares
Para cada um desses pares podemos escolher um terceiro numero de N-4 
maneiras. Logo : (N-3)(N-4) pares
SUBTOTAL3 : (N-3)(N-4)

CALCULO FINAL :

T=BINOM(N,3) - [ SUBTOTAL1 + SUBTOTAL2 + SUBTOTAL3 ]
T=BINOM(N,3) - [(N-2)^2]
T=[N(N-1)(N-2)/6] - [(N-2)^2]=((N-2)(N-3)(N-4))/6


UMA OUTRA FORMA DE FAZER :

Seja a equacao : X+Y+Z=N. Sem duvida que voce sabe calcular o numero de 
solucoes inteiras nao negativas desta equacao, pois este problema basico e 
abordado em todo livro de Analise Combinatoria.

Para obter as "solucoes positivas", faca :

X=X'+1 ; Y=Y'+1 e Z=Z'+1

E resolva : X'+Y'+Z'=N-3.  Se voce considerar que uma solucao de uma tal 
equacao e apenas uma forma de separa N-3 esferas por duas barras, a cada 
colucao inteira positiva corresponde uma forma de escolher duas pessoas nao 
consecutivas.

Exemplo ( vou considerar |=Barra, A=unidade e N-3=5 )

A solucao (1,2,2) correspode a A | AA | AA isto significaria escolher a 
segundo e o 5 aluno; AA|AA|A=(2,2,1) equivale a escolher o 3 e o 6 aluno; 
A|AAA|A=(1,3,1) equivale a escolher o 2 e o 6 aluno e assim sucessivamente. 
Ha, portanto, uma funcao entre as solucoes inteiras positivas da equacao e 
as escolhas que voce pode fazer. E so pensar com calma que a solucao sai por 
aqui facil. Os detalhes voce completa


UMA OUTRA SOLUCAO ? :

Procure se informar sobre os lemas de Kaplanski. No livro de Analise 
Combinatoria do Prof Morgado ha tudo isso e muito mais. Este livro, em minha 
opiniao, e o que ha de melhor no Brasil nesta area e vai te dar uma base 
para voce ser bem sucedido em qualquer vestibular que exija tal tema.

Um abraco
Paulo Santa Rita
2,1521,270502

>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 dois ou tres 
>alunosdesignados por numeros consecutivos ?


_________________________________________________________________
Envie e receba emails com o Hotmail no seu dispositivo móvel: 
http://mobile.msn.com

=========================================================================
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>
=========================================================================