Re: Re:[obm-l] IME 96
- Original Message - From: rafaelc.l [EMAIL PROTECTED] To: [EMAIL PROTECTED] 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 é [EMAIL PROTECTED] = = 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 é [EMAIL PROTECTED] =
Re: Re:[obm-l] IME 96
Caro Rafael: Não apareceram as setas que você mencionou no primeiro problema. Abraço, Claudio. - Original Message - From: Cláudio (Prática) [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, January 09, 2003 12:15 PM Subject: Re: Re:[obm-l] IME 96 - Original Message - From: rafaelc.l [EMAIL PROTECTED] To: [EMAIL PROTECTED] 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 é [EMAIL PROTECTED] = = 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 é [EMAIL PROTECTED] =
Re: Re:[obm-l] IME 96
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 [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
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 é [EMAIL PROTECTED]
=
=
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 é [EMAIL PROTECTED]
=
Re: 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 ? 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. Eu não acho que seja para andar pelos vértices, e sim pelo centro do quadrado... andando para um quadrado adjacente ou na diagonal. Assim não tem ambiguidade. = 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 é [EMAIL PROTECTED] =
Re: Re:[obm-l] IME 96
Esse do IME e legal.Mas tente fazer isso:se voce sabe a formula dos casos anteriores,tente fazer a dos casos maiores obtendo uma recorrencia. "rafaelc.l" [EMAIL PROTECTED] wrote: Caro Rafael: Não apareceram as setas que você mencionou no primeiro problema. Este problema já apareceu aqui na lista. As setas são 3: para baixo, para a direita e diagonal pra direita.- Original Message - From: "rafaelc.l" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]>> 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 é <[EMAIL PROTECTED]> = = 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 é <[EMAIL PROTECTED]> = __E-mail Premium BOLAntiví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 emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.htmlO administrador desta lista é <[EMAIL PROTECTED]>=Busca Yahoo! O melhor lugar para encontrar tudo o que você procura na Internet
Re: Re:[obm-l] IME 96
Uma forma de proceder seria contar o número de caminhos que passam por um número específico de quadrados. Assim, o menor caminho passa por três quadrados (excluindo o superior esquerdo mas incluindo o inferior direito) - é o da diagonal e é o único caminho desse comprimento. Chamemos de N(k), o número de caminhos de comprimento k. Assim, N(1) = N(2) = 0 e N(3) = 1. Já o caminho mais comprido não usa nenhuma diagonal e mede 6. Além disso, N(6) = C(6,3) = 20. Justificativa: cada caminho de comprimento 6 pode ser representado por uma sequência do tipo L L B L B B (L = para o lado, B = para baixo, D = pela diagonal), onde existem 3 L's e 3 B's ( e nenhum D). O número de tais sequências é C(6,3). O número total de caminhos é, portanto, N = N(3) + N(4) + N(5) + N(6). Já conhecemos N(3) e N(6). N(5) é o número de caminhos que usa apenas uma diagonal. Exemplos: B B L D L, ou então L D B L B. Todos estes caminhos seriam compostos de 1 D, 2 L's e 2 B's == N(5) = 5 * C(4,2) = 5 * 6 = 30 N(4) é o número de caminhos que usa duas diagonais. Exemplos: L D D B; D L D B. Todos os caminhos têm 2 D's, 1 L e 1 B == N(4) = C(4,2) * 2 = 6 * 2 = 12. Assim, N = 1 + 12 + 30 + 20 = 63 caminhos distintos. Um abraço, Claudio. - Original Message - From: Juliana Freire [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, January 09, 2003 6:00 PM Subject: Re: 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 ? 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. Eu não acho que seja para andar pelos vértices, e sim pelo centro do quadrado... andando para um quadrado adjacente ou na diagonal. Assim não tem ambiguidade. = 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 é [EMAIL PROTECTED] = = 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 é [EMAIL PROTECTED] =
Re: [obm-l] IME 96
On Sun, Nov 24, 2002 at 08:59:34PM -0300, Eduardo Casagrande Stabel wrote: Olá, essa questão também caiu na Olimpíada Gaúcha de Matemática. Eu pensei na mesma solução da banca. Mas uma das alunas que fez a prova deu uma solução mais simples, e que eu achei até mais apropriada ao tamanho do tabuleiro. Ela começou escrevendo um 1 no canto superior esquerdo. Para cada quadrado seguinte ela preenchia ele com a soma dos números escritos nos quadrados da esq. da dir. e da diagonal superior esq. Assim ela foi preenchendo o tabuleiro e o número final obtido no inferior direito foi a quantidade de maneiras de se chegar até ele. Interessante, né? Também é interessante o fato de que esta tabela apareceu como matriz na OBM nível U de 2001. Os números que preenchem a tabela são chamados de números de Delonnay e aparecem em alguns problemas de combinatória. Na OBM pedia-se para calcular o determinante da matriz (em função de n, o tamanho da matriz). []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 é [EMAIL PROTECTED] =
Re: [obm-l] IME 96
Olá Wander , Esta questão fez parte do banco de questões da quinta Olimpíada Brasileira . A idéia é a seguinte : indique os movimentos horizontais por H , os verticais por V e em diagonais por D . Para D=0 , temos : 6! /3!3! = 20(VVHHVH) ; para D=1 : 5! /2!2!1! =30 ; para D=2 : 4! /2!1!1! = 12 e para D=3 : somente uma solução ; logo 63 possibilidades , ok ? . Esta foi a solução dada pela banca . []´s Carlos Victor At 13:08 24/11/2002 -0300, Wander Junior wrote: É dado um tabuleiro quadrado 4x4. Deseja-se atingir o quadrado inferior direito a partir do quadrado superior esquerdo. Os movimentos permitidos são representados pelas setas: De quantas maneiras isto é possível ?
Re: [obm-l] IME 96
Olá, essa questão também caiu na Olimpíada Gaúcha de Matemática. Eu pensei na mesma solução da banca. Mas uma das alunas que fez a prova deu uma solução mais simples, e que eu achei até mais apropriada ao tamanho do tabuleiro. Ela começou escrevendo um 1 no canto superior esquerdo. Para cada quadrado seguinte ela preenchia ele com a soma dos números escritos nos quadrados da esq. da dir. e da diagonal superior esq. Assim ela foi preenchendo o tabuleiro e o número final obtido no inferior direito foi a quantidade de maneiras de se chegar até ele. Interessante, né? Duda. - Original Message - From: Carlos Victor To: [EMAIL PROTECTED] ; OBL Sent: Sunday, November 24, 2002 7:48 PM Subject: Re: [obm-l] IME 96 Olá Wander ,Esta questão fez parte do banco de questões da quinta Olimpíada Brasileira . A idéia é a seguinte :indique os movimentos horizontais por H , os verticais por V e em diagonais por D . Para D=0 , temos : 6! /3!3! = 20(VVHHVH) ; para D=1 : 5! /2!2!1! =30 ; para D=2 : 4! /2!1!1! = 12 e para D=3 : somente uma solução ; logo 63 possibilidades , ok ? . Esta foi a solução dada pela banca .[]´s Carlos VictorAt 13:08 24/11/2002 -0300, Wander Junior wrote: É dado um tabuleiro quadrado 4x4. Deseja-se atingir o quadrado inferior direito a partir do quadrado superior esquerdo. Os movimentos permitidos são representados pelas setas:De quantas maneiras isto é possível ?
Re: [obm-l] IME 96
Essa é mais ou menos a idéia do queé conhecido em computação como "Programação Dinâmica" Muito interessante mesmo. Até mais Vinicius Fortuna - Original Message - From: Eduardo Casagrande Stabel To: [EMAIL PROTECTED] Sent: Sunday, November 24, 2002 9:59 PM Subject: Re: [obm-l] IME 96 Olá, essa questão também caiu na Olimpíada Gaúcha de Matemática. Eu pensei na mesma solução da banca. Mas uma das alunas que fez a prova deu uma solução mais simples, e que eu achei até mais apropriada ao tamanho do tabuleiro. Ela começou escrevendo um 1 no canto superior esquerdo. Para cada quadrado seguinte ela preenchia ele com a soma dos números escritos nos quadrados da esq. da dir. e da diagonal superior esq. Assim ela foi preenchendo o tabuleiro e o número final obtido no inferior direito foi a quantidade de maneiras de se chegar até ele. Interessante, né? Duda.
