Re: Re:[obm-l] IME 96

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Caro Rafael:

Sobre o segundo problema, seja N(m,n) de funções estritamente crescentes
(f.e.c.'s) de Im em In, com m <= n.

Se F é uma tal função, então dados x e y em Im, com 1 <= x < y <= m, teremos
F(x) < F(y) ==> F é injetiva ==> F(Im) tem m elementos.

Pode-se tomar m elementos de In (que tem n elementos) de C(n,m) maneiras
distintas. Para cada um destes subconjuntos de m elementos de In, existe uma
única f.e.c. F cuja imagem é este subconjunto (vamos chamá-lo de X).

F é tal que:
F(1) = menor elemento de X;
F(2) = menor elemento de X - { F(1) };
F(3) = menor elemento de X - { F(1), F(2) }, etc.

Qualquer outra função G tal que G(Im) = X terá alguma transposição (isto é,
existirão x e y em Im, com 1 <= x < y <= m tais que G(x) > G(y) - caso
cont'rário, teríamos G = F ).

Assim, existe uma correspondência biunívoca entre f.e.c.'s de Im em In e
subconjuntos de In com m elementos.
Logo, N(m,n) = C(n,m) = n! / ( m! (n-m)! )

Um abraço,
Claudio.


----- Original Message -----
From: "rafaelc.l" <rafaelc.l@bol.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Thursday, January 09, 2003 4:32 AM
Subject: Re:[obm-l] IME 96


> É dado um tabuleiro quadrado 4x4. Deseja-
se atingir o quadrado inferior direito a partir do quadrad
o superior esquerdo. Os movimentos permitidos são represen
tados pelas setas:
>
>
> De quantas maneiras isto é possível ?


 Eu estava observando as mensagens anteriores e vi que
para esse problema deram uma solução considerando
inicialmente 6 caminhos(SEM CONTAR AS DIAGONAIS). O
enunciado está vago, pois diz que deve-se partir do
quadrado superior esquerdo e chegar ao quadrado inferior
direito. Mas isso, na minha opinião, pode ser feito
partindo-se de qualquer vértice do quadrado superior
esquerdo e chegar a qualquer vértice do quadrado inferior
direito, que pode ser feito tanto com 8 caminhos,com 7,
como com 6, como com 5 ou como com 4 caminhos
inicialmente. Esta é a minha dúvida a respeito da
questão.

  Aproveito para pedir como se resolve a seguinte questão:

 Sejam Im( 1,2,3,...,m) e In(1,2,...,n), com m menor= n.
 Quantas são as funções f:Im-In estritamente crescentes?




 Obrigado

        Rafael
>


__________________________________________________________________________
E-mail Premium BOL
Antivírus, anti-spam e até 100 MB de espaço. Assine já!
http://email.bol.com.br/


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

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