Re: [obm-l] Analise Combinatoria (Ops ... Cochilo)

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

Ola Pessoal,

Corrigindo um cochilo. Na segunda solucao e necessario considerar uma 
equacao a quatro variaveis e nao a duas :

X+Y+Z+W=N-3

Em geral, pensa-se em N-3 como o numero de unidades que devem ser separadas 
por tres barras. Exemplo :

X+Y+Z+W=12

UUU|UUU|UUUU|UU    ->    solucao : (3,3,4,2)
U|UUUUU|U|UUUUU    ->    solucao : (1,5,1,5)

E assim sucessivamente ... O que eu estou propondo e que se olhe as barras 
como alunos escolhidos :

UUU|UUU|UUUU|UU    ->    alunos escolhidos : {4,8,13}
U|UUUUU|U|UUUUU    ->    alunos escolhidos : {2,8,10}

Olhando as coisas assim ( eu sei que e um olhar estranho e nao convencional, 
mas entenda que funciona ) a toda solucao da equacao "sem zero" corresponde 
uma escolha valida dos alunos.

Basta agora considerar separadamente as solucoes da forma :

IUU..., UUU..U| e IUU...UU|

Um abraco
Paulo Santa Rita
2,1544,270502






>From: "Paulo Santa Rita" <p_ssr@hotmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Re: [obm-l] Analise Combinatoria
>Date: Mon, 27 May 2002 18:26:37 +0000
>
>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>
>=========================================================================




_________________________________________________________________
Converse com amigos on-line, conheça o MSN Messenger: 
http://messenger.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>
=========================================================================