[obm-l] Re: [obm-l] Questão interessante.
JF, No braço deu para ver um caso. Na matriz 3 x 3. 9,2,4; 6,8,1; 3,5,7. X=7 Y=3 Ou seja, se fosse para chutar e sabendo que X é diferente de Y, chutaria X Y. SDS, Marcos Melo. -- Mensagem original --- De : [EMAIL PROTECTED] Para: obm-l [EMAIL PROTECTED] Cc : Data: Tue, 13 Aug 2002 15:42:25 -0300 Assunto : [obm-l] Questão interessante. Não estou conseguindo partir. Tentando resolver no braço - afinal de contas, para que existem computadores? - estou achando que o mais baixo entre os mais altos das suas colunas é também o mais alto entre os mais baixo s das suas linhas. Dá para fornecer uma um ponto de partida? JF -Mensagem Original- De: Augusto Cesar de Oliveira Morgado [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Enviada em: Quinta-feira, 8 de Agosto de 2002 11:06 Assunto: Re: [obm-l] Questão interessante. Na verdade, o problema é russo e de data anterior a 1966. Mas é mu ito bonito. Morgado Em Wed, 7 Aug 2002 22:13:01 -0300, Eduardo Casagrande Stabel [EMAIL PROTECTED] disse: Olá pessoal! Compartilho com vocês esta questão que, tenho certeza, todos vão adorar. (Inglaterra - 1966) Cem pessoas de diferentes alturas são acomodadas num grande tabuleiro 10 x 10. O indivíduo X, o mais baixo dentre as 10 pessoas mais altas em suas colunas, mede uma altura diferente do indivíd uo Y, o mais alto dentro as 10 pessoas mais baixas em suas linhas. Quem é mai s baixo: X ou Y? Eduardo. = 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] == === = 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] ???
Eder, 61 divide 5^n-4^n quando n é multiplo de 3 pois, nesse caso, n = 3k e 5^n - 4^n = 5^(3k) - 4^(3k) = (5^3)^k - (4^3)^k = 125^k - 64^k = = (125 - 64)(125^(k-1) + 125^(k-2).64 + 125^(k-3).64^2 + ... + 64^(k-1)) = 61 . ( ) Falta provar que se n não é múltiplo de 3 então 61 não divide 5^n - 4^n. Laurito From: Eder [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] ??? Date: Tue, 13 Aug 2002 21:09:40 -0300 Gostaria de ajuda neste problema: Determinar para que valores de n, inteiros e positivos ,tem-se 61|(5^n - 4^n). Obrigado. Eder _ Tenha você também um MSN Hotmail, o maior webmail do mundo: http://www.hotmail.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] =
Re: [obm-l] ???
Obs: == significa congruente Repare que: 5^3 == 3 (mod. 61) = 5^3k == 3^k (mod. 61) = 5^(3k + 1) == 5.3^k (mod. 61) = 5^(3k + 2) == 25.3^k (mod. 61) 4^3 == 3 (mod. 61) = 4^3k == 3^k (mod. 61) = 4^(3k + 1) == 4.3^k (mod. 61) = 4^(3k + 2) == 16.3^k (mod. 61) Subtraindo as respectivas congruências: 5^3k - 4^3k == 0 (mod. 61) 5^(3k + 1) - 4^(3k + 1) == 3^k (mod. 61) 5^(3k + 2) - 4^(3k + 2) == 3^(k + 2) (mod. 61) Como mdc (3, 61) = 1 então nunca teremos uma potência de 3 que é divisível por 61. Portanto, somente para n = 3k temos que 61 divide 5^n - 4^n. Falou, Marcelo Rufino From: Laurito Alves [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] ??? Date: Wed, 14 Aug 2002 13:17:27 + Eder, 61 divide 5^n-4^n quando n é multiplo de 3 pois, nesse caso, n = 3k e 5^n - 4^n = 5^(3k) - 4^(3k) = (5^3)^k - (4^3)^k = 125^k - 64^k = = (125 - 64)(125^(k-1) + 125^(k-2).64 + 125^(k-3).64^2 + ... + 64^(k-1)) = 61 . ( ) Falta provar que se n não é múltiplo de 3 então 61 não divide 5^n - 4^n. Laurito From: Eder [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] ??? Date: Tue, 13 Aug 2002 21:09:40 -0300 Gostaria de ajuda neste problema: Determinar para que valores de n, inteiros e positivos ,tem-se 61|(5^n - 4^n). Obrigado. Eder _ Tenha você também um MSN Hotmail, o maior webmail do mundo: http://www.hotmail.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] = _ Send and receive Hotmail on your mobile device: 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 é [EMAIL PROTECTED] =
[obm-l] Re: [obm-l] Re: [obm-l] Questão interessante.
Talvez essa seja uma solução mais rigorosa.
Para i,k no conjunto {1,2,...,10}
Seja a_ik a altura da pessoa na linha i e coluna k do tabuleiro.
Chame de X_k a altura da pessoa mais alta na coluna k.
Chame de Y_i a altura da pessoa mais baixa na linha i.
Agora observe que X_k = a_ik=Y_i para todo i,k em {1,2,...,10}
Logo X=min{X_k}=max{Y_i}=Y.
Como X é diferente de Y, então XY.
Abraço. Pedro.
- Original Message -
From: Marcos Melo [EMAIL PROTECTED]
To: obm-l [EMAIL PROTECTED]
Sent: Wednesday, August 14, 2002 9:01 AM
Subject: [obm-l] Re: [obm-l] Questão interessante.
JF,
No braço deu para ver um caso.
Na matriz 3 x 3.
9,2,4;
6,8,1;
3,5,7.
X=7 Y=3
Ou seja, se fosse para chutar e sabendo que X é diferente de Y,
chutaria X Y.
SDS,
Marcos Melo.
-- Mensagem original ---
De : [EMAIL PROTECTED]
Para: obm-l [EMAIL PROTECTED]
Cc :
Data: Tue, 13 Aug 2002 15:42:25 -0300
Assunto : [obm-l] Questão interessante.
Não estou conseguindo partir. Tentando resolver no braço -
afinal de contas,
para que existem computadores? -
estou achando que o mais baixo entre os
mais altos das suas colunas é também o mais alto entre os mais baixo
s das
suas linhas. Dá para fornecer uma um ponto de partida?
JF
-Mensagem Original-
De: Augusto Cesar de Oliveira Morgado [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: Quinta-feira, 8 de Agosto de 2002 11:06
Assunto: Re: [obm-l] Questão interessante.
Na verdade, o problema é russo e de data anterior a 1966. Mas é mu
ito
bonito.
Morgado
Em Wed, 7 Aug 2002 22:13:01 -0300, Eduardo Casagrande Stabel
[EMAIL PROTECTED] disse:
Olá pessoal!
Compartilho com vocês esta questão que, tenho certeza, todos vão
adorar.
(Inglaterra -
1966) Cem pessoas de diferentes alturas são acomodadas num
grande tabuleiro 10 x 10. O indivíduo X, o mais baixo dentre as
10
pessoas
mais altas em suas colunas, mede uma altura diferente do indivíd
uo Y, o
mais
alto dentro as 10 pessoas mais baixas em suas linhas. Quem é mai
s baixo:
X
ou Y?
Eduardo.
=
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]
==
===
=
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]
=
=
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]
=
[obm-l] Contagem difícil - ajuda
De quantas maneiras 24 pessoas podem subir numa roda gigante de 12 assentos, sabendo que cada assento comporta duas pessoas?
[obm-l] CRUEL
Num polígono convexo de n lados, quando se constrói todas as diagonais aparecem pontos de interseção entre as diagonais. Determinar o número de pontos de interseção?
Re: [obm-l] CRUEL
At 12:21 14/08/02 -0400, you wrote: Num polígono convexo de n lados, quando se constrói todas as diagonais aparecem pontos de interseção entre as diagonais. Determinar o número de pontos de interseção? Vamos supor que não há duas diagonais paralelas. Note que a cada ponto de intersecção podemos associar as duas diagonais ou o quadrilátero formado pelos extremos destas diagonais. Logo há uma bijeção entre o número de intersecções e o de quadriláteros com vértices contidos no conjunto de vértices do poligono...logo a resposta é binomial(n,4). Está certo? Bruno Leite http://www.ime.usp.br/~brleite = 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] Questão interessante.
Considere o cidadao na intersecao da linha do mais baixo dos altinhos com a coluna do mais alto dos baixinhos. Abracos, olavo. From: Jose Francisco Guimaraes Costa [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: obm-l [EMAIL PROTECTED] Subject: [obm-l] Questão interessante. Date: Tue, 13 Aug 2002 15:42:25 -0300 Não estou conseguindo partir. Tentando resolver no braço - afinal de contas, para que existem computadores? - estou achando que o mais baixo entre os mais altos das suas colunas é também o mais alto entre os mais baixos das suas linhas. Dá para fornecer uma um ponto de partida? JF -Mensagem Original- De: Augusto Cesar de Oliveira Morgado [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Enviada em: Quinta-feira, 8 de Agosto de 2002 11:06 Assunto: Re: [obm-l] Questão interessante. Na verdade, o problema é russo e de data anterior a 1966. Mas é muito bonito. Morgado Em Wed, 7 Aug 2002 22:13:01 -0300, Eduardo Casagrande Stabel [EMAIL PROTECTED] disse: Olá pessoal! Compartilho com vocês esta questão que, tenho certeza, todos vão adorar. (Inglaterra - 1966) Cem pessoas de diferentes alturas são acomodadas num grande tabuleiro 10 x 10. O indivíduo X, o mais baixo dentre as 10 pessoas mais altas em suas colunas, mede uma altura diferente do indivíduo Y, o mais alto dentro as 10 pessoas mais baixas em suas linhas. Quem é mais baixo: X ou Y? Eduardo. = 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] = = 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] = _ Send and receive Hotmail on your mobile device: 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 é [EMAIL PROTECTED] =
[obm-l] Questão interessante.
Temo estar dizendo tremendas bobagens. Se estiver, sejam discretos ao
apontar meus erros.
JF
PS: O que o Morgado, o Ainda Vivo, que deve conhecer o problema, já que
corrigiu a nacionalidade e idade dele, tem a dizer disso tudo?
-Mensagem Original-
De: Pedro Antonio Santoro Salomão [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: Quarta-feira, 14 de Agosto de 2002 11:53
Assunto: [obm-l] Re: [obm-l] Re: [obm-l] Questão interessante.
Talvez essa seja uma solução mais rigorosa.
Para i,k no conjunto {1,2,...,10}
Seja a_ik a altura da pessoa na linha i e coluna k do tabuleiro.
Chame de X_k a altura da pessoa mais alta na coluna k.
Chame de Y_i a altura da pessoa mais baixa na linha i.
Agora observe que X_k = a_ik=Y_i para todo i,k em {1,2,...,10}
Logo X=min{X_k}=max{Y_i}=Y.
Como X é diferente de Y, então XY.
Abraço. Pedro.
***
O enunciado do problema nao diz que XY. Ele diz que os indivíduos têm
alturas diferentes. Usando sua notação, não existem duas a_ik iguais.
Por exemplo, na matriz 2x2
5, 20
10, 15
X_k={10,20} logo X=min(X_k)=10
Y_i={5,10} logo Y=max(Y_i)=10
e temos X=Y (leia-se o indivíduo que é o mais baixo entre os mais altos das
colunas é também o mais alto entre os mais baixos das linhas)
***
- Original Message -
From: Marcos Melo [EMAIL PROTECTED]
To: obm-l [EMAIL PROTECTED]
Sent: Wednesday, August 14, 2002 9:01 AM
Subject: [obm-l] Re: [obm-l] Questão interessante.
JF,
No braço deu para ver um caso.
Na matriz 3 x 3.
9,2,4;
6,8,1;
3,5,7.
X=7 Y=3
Ou seja, se fosse para chutar e sabendo que X é diferente de Y,
chutaria X Y.
SDS,
Marcos Melo.
***
Mas se alterarmos um pouco sua matriz,
19, 2, 4
6, 8, 1
10, 9, 7
teremos X=min{19,9,7} e Y=max{2,1,7}
logo X=Y=7 (leia-se o indivíduo que é o mais baixo entre os mais altos...)
(é a mesma Síndrome do menor-dos-maiores=maior-dos-menores)
***
-Mensagem Original-
De: Paulo Santa Rita [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: Terça-feira, 13 de Agosto de 2002 18:00
Assunto: [obm-l] Re: [obm-l] Questão interessante.
Y é menor que X.
X é o mais baixo entre os 10 mais altos em suas colunas, isto é, em cada
coluna i nos encontramos Ci, o mais alto na coluna i. Isto fornece um
conjunto {C1, C2, ...,C10}. Daqui : X=min{ C1,C2, ...,C10 }
Y é o mais alto entre os 10 mais baixos em suas linhas, isto é, em cada
linha j nos encontramos Lj, o mais baixo na linha j. Isto fornece um
conjunto {L1,L2,...,L10}. Daqui : Y=max{ L1,L2,...,L10 }
Como, pelo enunciado, nao pode ser Y = X , então só há duas
possibilidades.
Vamos supor que :
TESE : Y X
Seja Y=Lj e X=Ci. Agora veja :
Lj Ci = O mais baixo da linha j (Lj) é mais alto que o mais alto da
coluna i = todos da linha j sao mais altos que o mais alto da coluna i =
Ci nao pode estar na linha j, pois entao ele seria o mais baixo, logo,
deveria ser igual a Lj (ABSURDO !) = na intersecao da linha j com a
coluna
i ha um cara mais alto que Ci = Ci nao é o mais alto em sua coluna ...
OUTRO ABSURDO !!
A nossa tese e portanto insustentavel e somos obrigados a admitir que
Y X
***
O enunciado NÃO diz que nao pode ser Y = X. Ele diz que indivíduos têm
alturas diferentes. Logo, há três e não apenas duas possibilidades: (1) XY;
(2) X=Y; e (3) XY. V provou que a (3) é absurda. Tente provar que a (2)
também é. V não vai conseguir. Se conseguir, existe algo errado com a sua
prova, como os contra exemplos acima mostram.
***
-- Mensagem original ---
De : [EMAIL PROTECTED]
Para: obm-l [EMAIL PROTECTED]
Cc :
Data: Tue, 13 Aug 2002 15:42:25 -0300
Assunto : [obm-l] Questão interessante.
Não estou conseguindo partir. Tentando resolver no braço -
afinal de contas,
para que existem computadores? -
estou achando que o mais baixo entre os
mais altos das suas colunas é também o mais alto entre os mais baixo
s das
suas linhas. Dá para fornecer uma um ponto de partida?
JF
-Mensagem Original-
De: Augusto Cesar de Oliveira Morgado [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: Quinta-feira, 8 de Agosto de 2002 11:06
Assunto: Re: [obm-l] Questão interessante.
Na verdade, o problema é russo e de data anterior a 1966. Mas é mu
ito
bonito.
Morgado
Em Wed, 7 Aug 2002 22:13:01 -0300, Eduardo Casagrande Stabel
[EMAIL PROTECTED] disse:
Olá pessoal!
Compartilho com vocês esta questão que, tenho certeza, todos vão
adorar.
(Inglaterra -
1966) Cem pessoas de diferentes alturas são acomodadas num
grande tabuleiro 10 x 10. O indivíduo X, o mais baixo dentre as
10
pessoas
mais altas em suas colunas, mede uma
[obm-l] Re: [obm-l] Questão interessante.
Ola Pessoal,
Eu esbocei uma solucao, que esta correta. Talvea eu tenha sido muito
sucinto. Vou, agora, ser mais prolixo :
1) Para cada coluna i, seja Y(i) a altura da pessoal mais alta que esta na
coluna i. Isto cria o conjunto : { Y(1),Y(2),...,Y(10) }
formado pelas pessoas mais altas em cada coluna.
Por Definiçao :
Y=MIN{ Y(1),Y(2),...,Y(10) }, isto é, Y e a altura do individuo mais baixo
entre os dez mais altos em cada coluna.
2) Igualmente, para cada linha j, seja X(j) a altura da pessoa mais baixa
que esta na linha j. Isto cria o conjunto :
{X(1),X(2),...,X(10)} formado pelas pessoas mais baixas em cada linha.
Por definição :
X=MAX{X(1),X(2),...,X(10)}, isto é, X e a altura do individuo mais alto
entre os dez mais baixos em cada linha.
O enunciado afirma que X é diferente de Y. Então so pode ser X Y
ou Y X. Vamos mostrar que X Y conduz a um absurdo :
3) Se X Y entao, sendo X o mais baixo em sua linha, segue necessariamente
que todos que estao na linha onde X esta sao mais altos que Y. E isto
implica que Y nao esta linha onde X esta. Por que ?
Porque se Y estivesse na linha onde X esta, Y seria o menor da linha, mas,
por definicao, o menor da linha onde X esta e o X, logo, deveriamos ter Y=X,
um absurdo, pois estamos supondo que X Y.
Vemos portanto que supor que Y esta linha que X esta conduz a um absurdo. So
resta uma possibilidade : Y esta em outra linha !
Bom, neste caso, a linha onde X esta tem, evidentemente, uma interseccao com
a coluna onde Y esta. Como, pelo que vimos em 3), todos os elementos da
linha onde X esta sao mais altos que o Y, segue a intersecao abriga uma
pessoa mais alta que Y, e isto entra em contradicao com o fato de Y ser o
mais alto de sua coluna, isto e, chegamos a um novo absurdo.
COMPUTO FINAL : Se supormos que X Y, estando Y na linha onde X esta ou
estando Y em outra linha, chegamos a um absurdo. Logo, a tese de que X Y é
insustentavel e somos obrigados a admitir que Y X.
sobre a solucao acima, o que o Prof Morgado pode dizer e que e uma solucao
correta.
Um abraco a todos
Paulo Santa Rita
4,1706,140802
From: Jose Francisco Guimaraes Costa [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: obm-l [EMAIL PROTECTED]
Subject: [obm-l] Questão interessante.
Date: Wed, 14 Aug 2002 15:51:12 -0300
Temo estar dizendo tremendas bobagens. Se estiver, sejam discretos ao
apontar meus erros.
JF
PS: O que o Morgado, o Ainda Vivo, que deve conhecer o problema, já que
corrigiu a nacionalidade e idade dele, tem a dizer disso tudo?
-Mensagem Original-
De: Pedro Antonio Santoro Salomão [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: Quarta-feira, 14 de Agosto de 2002 11:53
Assunto: [obm-l] Re: [obm-l] Re: [obm-l] Questão interessante.
Talvez essa seja uma solução mais rigorosa.
Para i,k no conjunto {1,2,...,10}
Seja a_ik a altura da pessoa na linha i e coluna k do tabuleiro.
Chame de X_k a altura da pessoa mais alta na coluna k.
Chame de Y_i a altura da pessoa mais baixa na linha i.
Agora observe que X_k = a_ik=Y_i para todo i,k em {1,2,...,10}
Logo X=min{X_k}=max{Y_i}=Y.
Como X é diferente de Y, então XY.
Abraço. Pedro.
***
O enunciado do problema nao diz que XY. Ele diz que os indivíduos têm
alturas diferentes. Usando sua notação, não existem duas a_ik iguais.
Por exemplo, na matriz 2x2
5, 20
10, 15
X_k={10,20} logo X=min(X_k)=10
Y_i={5,10} logo Y=max(Y_i)=10
e temos X=Y (leia-se o indivíduo que é o mais baixo entre os mais altos
das
colunas é também o mais alto entre os mais baixos das linhas)
***
- Original Message -
From: Marcos Melo [EMAIL PROTECTED]
To: obm-l [EMAIL PROTECTED]
Sent: Wednesday, August 14, 2002 9:01 AM
Subject: [obm-l] Re: [obm-l] Questão interessante.
JF,
No braço deu para ver um caso.
Na matriz 3 x 3.
9,2,4;
6,8,1;
3,5,7.
X=7 Y=3
Ou seja, se fosse para chutar e sabendo que X é diferente de Y,
chutaria X Y.
SDS,
Marcos Melo.
***
Mas se alterarmos um pouco sua matriz,
19, 2, 4
6, 8, 1
10, 9, 7
teremos X=min{19,9,7} e Y=max{2,1,7}
logo X=Y=7 (leia-se o indivíduo que é o mais baixo entre os mais
altos...)
(é a mesma Síndrome do menor-dos-maiores=maior-dos-menores)
***
-Mensagem Original-
De: Paulo Santa Rita [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: Terça-feira, 13 de Agosto de 2002 18:00
Assunto: [obm-l] Re: [obm-l] Questão interessante.
Y é menor que X.
X é o mais baixo entre os 10 mais altos em suas colunas, isto é, em cada
coluna i nos encontramos Ci, o mais alto na coluna i. Isto fornece um
conjunto {C1, C2, ...,C10}. Daqui : X=min{ C1,C2, ...,C10 }
Y é o mais alto entre os 10 mais baixos em suas linhas, isto é, em cada
linha j nos encontramos Lj, o mais baixo na linha j. Isto fornece um
conjunto {L1,L2,...,L10}. Daqui :
Re: [obm-l] CRUEL
From: Bruno F. C. Leite [EMAIL PROTECTED] At 12:21 14/08/02 -0400, you wrote: Num polígono convexo de n lados, quando se constrói todas as diagonais aparecem pontos de interseção entre as diagonais. Determinar o número de pontos de interseção? Vamos supor que não há duas diagonais paralelas. Note que a cada ponto de intersecção podemos associar as duas diagonais ou o quadrilátero formado pelos extremos destas diagonais. Logo há uma bijeção entre o número de intersecções e o de quadriláteros com vértices contidos no conjunto de vértices do poligono...logo a resposta é binomial(n,4). Está certo? Bruno Leite http://www.ime.usp.br/~brleite Mas e se dois quadriláteros distintos tiverem o mesmo ponto de interseção das suas diagonais? Ou isso nunca ocorre por que nenhuma das diagonais é paralelas, por hipótese sua? = 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] =
[obm-l] Re: [obm-l] Questão interessante.
O enunciado diz que X é diferente de Y, por isso a conclusão de que X Y.
Senão, realmente não tinha como concluir.
Talvez você argumente que o enunciado do problema possa apresentar algum
problema, ou seja, que tenhamos que provar que nem sempre X = Y. Mas para
isso, bastaria construir um exemplo de um tabuleiro 10 x 10 com a
propriedade X Y. E é simples fazer isso, ou seja, o enunciado está
correto.
Um abraço. Pedro.
- Original Message -
From: Jose Francisco Guimaraes Costa [EMAIL PROTECTED]
To: obm-l [EMAIL PROTECTED]
Sent: Wednesday, August 14, 2002 3:51 PM
Subject: [obm-l] Questão interessante.
Temo estar dizendo tremendas bobagens. Se estiver, sejam discretos ao
apontar meus erros.
JF
PS: O que o Morgado, o Ainda Vivo, que deve conhecer o problema, já que
corrigiu a nacionalidade e idade dele, tem a dizer disso tudo?
-Mensagem Original-
De: Pedro Antonio Santoro Salomão [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: Quarta-feira, 14 de Agosto de 2002 11:53
Assunto: [obm-l] Re: [obm-l] Re: [obm-l] Questão interessante.
Talvez essa seja uma solução mais rigorosa.
Para i,k no conjunto {1,2,...,10}
Seja a_ik a altura da pessoa na linha i e coluna k do tabuleiro.
Chame de X_k a altura da pessoa mais alta na coluna k.
Chame de Y_i a altura da pessoa mais baixa na linha i.
Agora observe que X_k = a_ik=Y_i para todo i,k em {1,2,...,10}
Logo X=min{X_k}=max{Y_i}=Y.
Como X é diferente de Y, então XY.
Abraço. Pedro.
***
O enunciado do problema nao diz que XY. Ele diz que os indivíduos têm
alturas diferentes. Usando sua notação, não existem duas a_ik iguais.
Por exemplo, na matriz 2x2
5, 20
10, 15
X_k={10,20} logo X=min(X_k)=10
Y_i={5,10} logo Y=max(Y_i)=10
e temos X=Y (leia-se o indivíduo que é o mais baixo entre os mais altos
das
colunas é também o mais alto entre os mais baixos das linhas)
***
- Original Message -
From: Marcos Melo [EMAIL PROTECTED]
To: obm-l [EMAIL PROTECTED]
Sent: Wednesday, August 14, 2002 9:01 AM
Subject: [obm-l] Re: [obm-l] Questão interessante.
JF,
No braço deu para ver um caso.
Na matriz 3 x 3.
9,2,4;
6,8,1;
3,5,7.
X=7 Y=3
Ou seja, se fosse para chutar e sabendo que X é diferente de Y,
chutaria X Y.
SDS,
Marcos Melo.
***
Mas se alterarmos um pouco sua matriz,
19, 2, 4
6, 8, 1
10, 9, 7
teremos X=min{19,9,7} e Y=max{2,1,7}
logo X=Y=7 (leia-se o indivíduo que é o mais baixo entre os mais
altos...)
(é a mesma Síndrome do menor-dos-maiores=maior-dos-menores)
***
-Mensagem Original-
De: Paulo Santa Rita [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: Terça-feira, 13 de Agosto de 2002 18:00
Assunto: [obm-l] Re: [obm-l] Questão interessante.
Y é menor que X.
X é o mais baixo entre os 10 mais altos em suas colunas, isto é, em cada
coluna i nos encontramos Ci, o mais alto na coluna i. Isto fornece um
conjunto {C1, C2, ...,C10}. Daqui : X=min{ C1,C2, ...,C10 }
Y é o mais alto entre os 10 mais baixos em suas linhas, isto é, em cada
linha j nos encontramos Lj, o mais baixo na linha j. Isto fornece um
conjunto {L1,L2,...,L10}. Daqui : Y=max{ L1,L2,...,L10 }
Como, pelo enunciado, nao pode ser Y = X , então só há duas
possibilidades.
Vamos supor que :
TESE : Y X
Seja Y=Lj e X=Ci. Agora veja :
Lj Ci = O mais baixo da linha j (Lj) é mais alto que o mais alto da
coluna i = todos da linha j sao mais altos que o mais alto da coluna i
=
Ci nao pode estar na linha j, pois entao ele seria o mais baixo, logo,
deveria ser igual a Lj (ABSURDO !) = na intersecao da linha j com a
coluna
i ha um cara mais alto que Ci = Ci nao é o mais alto em sua coluna ...
OUTRO ABSURDO !!
A nossa tese e portanto insustentavel e somos obrigados a admitir que
Y X
***
O enunciado NÃO diz que nao pode ser Y = X. Ele diz que indivíduos têm
alturas diferentes. Logo, há três e não apenas duas possibilidades: (1)
XY;
(2) X=Y; e (3) XY. V provou que a (3) é absurda. Tente provar que a (2)
também é. V não vai conseguir. Se conseguir, existe algo errado com a sua
prova, como os contra exemplos acima mostram.
***
-- Mensagem original ---
De : [EMAIL PROTECTED]
Para: obm-l [EMAIL PROTECTED]
Cc :
Data: Tue, 13 Aug 2002 15:42:25 -0300
Assunto : [obm-l] Questão interessante.
Não estou conseguindo partir. Tentando resolver no braço -
afinal de contas,
para que existem computadores? -
estou achando que o mais baixo entre os
mais altos das suas colunas é também o mais alto entre os mais baixo
s das
suas linhas. Dá para fornecer uma um ponto de partida?
JF
[obm-l] Tradução de Problema
Olá pessoal da lista, alguém sabe como eu devo interpretar o seguinte problema? Isabel tem dois baralhos, cada um com 50 cartas. Em cada um dos baralhos estão escritos os números de 1 a 100 (em cada carta estão escritos dois números, um em cada face da carta). Por um defeito de fabricação, a distribuição dos números nas cartas não é a mesma nos dois baralhos (por exemplo, em um dos baralhos o 1 aparece na mesma carta do 2; no outro, o 1 aparece com o 76). Mostre como Isabel deve fazer para que, ao colocar as 100 cartas sobre uma mesa, as faces voltadas para cima mostrem todos os números de 1 a 100. Eu não entendi o que precisa ser mostrado, para mim não está nada claro sob que condições ela pode colocar as cartas na mesa, alguém sabe? Valeu! Eduardo. Porto Alegre, RS. PS. caiu na obm de 2000, fase 3, níveis 1 e 2. = 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] =
[obm-l] Re: [obm-l] Tradução de Problema
Ola Duda e demais colegas desta lista ... OBM-L O que precisa ser mostrado é exatamente o que pede o enunciado do problema : as cem cartas sobre a mesa com os numeros de 1 a 100 visiveis, sem faltar nenhum deles ... Em que consiste o problema ? Nao e evidente que - INDEPENDENTE DA MANEIRA COMO OS NUMEROS FORAM GRAFADOS NOS DOIS BARALHOS - seja possivel exibir os 100 numeros, sem que haja omissao de algum numero. A parte matematica ( algoritmica )da questao consiste precisamente em mostrar que uma tal exibicao sempre é possivel. Uma parafrase do problema pode ser : Mostre como isabel pode escolher cada carta, determinando qual numero ficara por cima e qual ficara por baixo, de forma que no final da centesima escolha as faces visiveis exponham os 100 numeros naturais. Uma sintaxe adequada pode ser : Sejam A e B os baralhos. Ao escolher uma carta de um dos baralhos ( digamos, do baralho A ) teremos um par (V,I) em que V e o numero que ficara pra cima ( visicel ) e I o numero que ficara pra baixo ( invisivel ).O Mesmo vale para o baralho B. O inicio de um algoritmo pode ser : 1) Escolha a carta do baralho A onde esta o numero 1. Seja X o numero que acompanha 1 no baralho A. Colocamos a carta na forma (1,X). 2) Procure a carta do baralho B que tem o numero X. Seja Y o numero que acompanha o numero X no baralho B. Colocamos esta carta na forma (X,Y) 3) Y=1 ? Se nao, procure no baralho A ... E assim sucessivamente. Voce deve mostrar que o algoritmo descrito permite - INDEPENDENTE DA MANEIRA COMO OS NUMEROS FORAM GRAFADOS NOS DOIS BARALHOS - exibir as 100 cartas com os 100 numeros visiveis, sem que nenhum seja omitido. Eu nao parei para analisar se o algoritmo acima funciona. Estou apenas explicando o que e problematico e o que o problema requer. Muito provavelmente ha um algoritmo otimo para a questao, que e trivial. Um abraco a Todos Paulo Santa Rita 4,1958,140802 From: Eduardo Casagrande Stabel [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] Tradução de Problema Date: Wed, 14 Aug 2002 18:15:53 -0300 Olá pessoal da lista, alguém sabe como eu devo interpretar o seguinte problema? Isabel tem dois baralhos, cada um com 50 cartas. Em cada um dos baralhos estão escritos os números de 1 a 100 (em cada carta estão escritos dois números, um em cada face da carta). Por um defeito de fabricação, a distribuição dos números nas cartas não é a mesma nos dois baralhos (por exemplo, em um dos baralhos o 1 aparece na mesma carta do 2; no outro, o 1 aparece com o 76). Mostre como Isabel deve fazer para que, ao colocar as 100 cartas sobre uma mesa, as faces voltadas para cima mostrem todos os números de 1 a 100. Eu não entendi o que precisa ser mostrado, para mim não está nada claro sob que condições ela pode colocar as cartas na mesa, alguém sabe? Valeu! Eduardo. Porto Alegre, RS. PS. caiu na obm de 2000, fase 3, níveis 1 e 2. = 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] = _ Tenha você também um MSN Hotmail, o maior webmail do mundo: http://www.hotmail.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] =
[obm-l] Complexidades P e NP
Gostaria de saber se existe algum problema que pertença simultaneamente à classe de complexidade P e à classe de compleidade NP. Edilon Ribeiro. = 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] Complexidades P e NP
Sim, todos os problemas em P. Por definicao, P eh um subconjunto de NP. Ou seja, todos os problemas em P tambem estao NP. Abraco, Rodrigo Edilon Ribeiro da Silva wrote: Gostaria de saber se existe algum problema que pertença simultaneamente à classe de complexidade P e à classe de compleidade NP. Edilon Ribeiro. = 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] Complexidades P e NP
A seguinte proposição é verdadeira: Todo problema pertencente à classe de complexidade P pertence à classe de complexidade NP. A classe P significa que a solução pode ser verificada em tempo polinomial. A classe NP significa que a solução pode ser verificada não-deterministicamente em tempo polinomial. A proposição de que P está contido em NP vem justamente do fato de que tudo que é determinístico pode ser considerado como não-determinístico. A recíproca da proposição é um problema em aberto. Existe um subconjunto dos NP que são os NP-completos. Todo problema NP se reduz polinomialmente a um problema NP-completo. Isso quer dizer que sempre é possível transformar um problema NP em tempo polinomial em um caso particular de um NP-completo. Dessa forma, se um problema NP-completo puder ser resolvido em tempo polinomial, então, todos os NP também poderão e então teremos P=NP. Acredita-se que P é diferente de NP. Eu preferiria que fossem iguais, as coisas seriam bem mais fáceis. :-) Maiores informação pode-se encontrar em qualquer livro de complexidade de algoritmos Até mais Vinicius Fortuna Ciência da Computação - Unicamp - Original Message - From: Edilon Ribeiro da Silva [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Wednesday, August 14, 2002 8:34 PM Subject: [obm-l] Complexidades P e NP Gostaria de saber se existe algum problema que pertença simultaneamente à classe de complexidade P e à classe de compleidade NP. Edilon Ribeiro. = 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] Complexidades P e NP
Ola, Uma pequena correcao nas colocacoes do Vinicius... A classe P significa que a solução pode ser verificada em tempo polinomial. A classe NP significa que a solução pode ser verificada não-deterministicamente em tempo polinomial. A classe P eh a classe dos problemas que podem ser RESOLVIDOS por algoritmos deterministicos em tempo polinomial (e nao a classe dos problemas que tem sua resposta verificada em tempo polinomial). De forma semelhante, a classe NP eh a classe dos problemas que podem ser RESOLVIDOS por algoritmos nao-deterministicos em tempo polinomial no tamanho da entrada. Isto eh equivalente a dizer que uma resposta pode ser VERIFICADA deterministicamente em tempo polinomial. Abracos, Rodrigo = 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] =
[obm-l] Re: [obm-l] Re: [obm-l] Tradução de Problema
Podemos resolver esse problema usando Teoria dos Grafos.
Criamos um conjunto X de véritices que representam os números e um conjunto
Y de vértices que representam as cartas.
|X| = |Y| = 100.
Para cada vértice x em X, adicionamos uma aresta (x,y) para cada uma das
duas cartas y em que o número x aparece.
Dessa forma criamos um grafo bipartido, ou bigrafo-X,Y. Um bigrafo-X,Y
significa que não há arestas entre elementos do conjunto X ou entre
elementos do conjunto Y.
Assim queremos um casamento total entre os números em X com as cartas em Y.
Um número x casado com uma carta y significa que a carta y estará com o
número x voltado para cima.
Pelo Teorema de Hall, um bigrafo G tem um casamento que satura X se, e
somente se, |N(S)| = |S| para todo subconjunto S de X
Um casamento que satura X é que casa todos seus elementos. É o que
procuramos.
N(S) é a vizinhança dos vértices em S.
Sendo S um subconjunto de X, considere o subgrafo induzido por S união N(S).
O número de arestas E será 2.|S|, pois cada número em S se liga a duas
cartas em N(S)
Mas pelo Primeiro Teorema da Teoria dos Grafos temos
2.E = Soma{v em S U N(S)} d(v)
Onde d(v) é o número de arestas incidentes a v
Então, como S e N(S) são disjuntos:
4.|S| = [Soma{v em S} d(v)] + [Soma{v em N(S)}d(v)]
Como d(v) = 2 para todo v em S temos
4.|S| = 2.|S| + Soma{v em N(S)}d(v)
Soma{v em N(S)}d(v) = 2.|S|
Mas d(v) = 2 para todo v em N(S), pois cada carta se liga ao no máximo dois
números, então
Soma{v em N(S)} 2 = Soma{v em N(S)}d(v) = 2|S|
2.|N(S)| = 2.|S|
|N(S)| = |S|
Assim conseguimos a condição necessário no Teorema de Hall para provar que
existe um casamento que cubra todos os números em X.
Isso vale para qquer quantidade de números e dois baralhos, em particular
para 100 números, o que resolve o problema proposto.
Até mais
Vinicius Fortuna
- Original Message -
From: Paulo Santa Rita [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Sent: Wednesday, August 14, 2002 8:00 PM
Subject: [obm-l] Re: [obm-l] Tradução de Problema
Ola Duda e demais colegas
desta lista ... OBM-L
O que precisa ser mostrado é exatamente o que pede o enunciado do problema
:
as cem cartas sobre a mesa com os numeros de 1 a 100 visiveis, sem faltar
nenhum deles ...
Em que consiste o problema ?
Nao e evidente que - INDEPENDENTE DA MANEIRA COMO OS NUMEROS FORAM
GRAFADOS
NOS DOIS BARALHOS - seja possivel exibir os 100 numeros, sem que haja
omissao de algum numero. A parte matematica ( algoritmica )da questao
consiste precisamente em mostrar que uma tal exibicao sempre é possivel.
Uma parafrase do problema pode ser : Mostre como isabel pode escolher cada
carta, determinando qual numero ficara por cima e qual ficara por baixo,
de
forma que no final da centesima escolha as faces visiveis exponham os 100
numeros naturais.
Uma sintaxe adequada pode ser :
Sejam A e B os baralhos. Ao escolher uma carta de um dos baralhos (
digamos,
do baralho A ) teremos um par (V,I) em que V e o numero que ficara pra
cima
( visicel ) e I o numero que ficara pra baixo ( invisivel ).O Mesmo vale
para o baralho B.
O inicio de um algoritmo pode ser :
1) Escolha a carta do baralho A onde esta o numero 1. Seja X o numero que
acompanha 1 no baralho A. Colocamos a carta na forma (1,X).
2) Procure a carta do baralho B que tem o numero X. Seja Y o numero que
acompanha o numero X no baralho B. Colocamos esta carta na forma (X,Y)
3) Y=1 ?
Se nao, procure no baralho A ...
E assim sucessivamente. Voce deve mostrar que o algoritmo descrito
permite -
INDEPENDENTE DA MANEIRA COMO OS NUMEROS FORAM GRAFADOS NOS DOIS BARALHOS -
exibir as 100 cartas com os 100 numeros visiveis, sem que nenhum seja
omitido.
Eu nao parei para analisar se o algoritmo acima funciona. Estou apenas
explicando o que e problematico e o que o problema requer. Muito
provavelmente ha um algoritmo otimo para a questao, que e trivial.
Um abraco a Todos
Paulo Santa Rita
4,1958,140802
From: Eduardo Casagrande Stabel [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: [obm-l] Tradução de Problema
Date: Wed, 14 Aug 2002 18:15:53 -0300
Olá pessoal da lista,
alguém sabe como eu devo interpretar o seguinte problema?
Isabel tem dois baralhos, cada um com 50 cartas. Em cada um dos baralhos
estão escritos os números de 1 a 100 (em cada carta estão escritos dois
números, um em cada face da carta). Por um defeito de fabricação, a
distribuição dos números nas cartas não é a mesma nos dois baralhos (por
exemplo, em um dos baralhos o 1 aparece na mesma carta do 2; no outro, o
1
aparece com o 76). Mostre como Isabel deve fazer para que, ao colocar as
100
cartas sobre uma mesa, as faces voltadas para cima mostrem todos os
números
de 1 a 100.
Eu não entendi o que precisa ser mostrado, para mim não está nada claro
sob
que condições ela pode colocar as cartas na mesa, alguém sabe?
Valeu!
Eduardo.
Porto Alegre, RS.
PS. caiu na obm de 2000, fase 3, níveis 1 e 2.
Re: [obm-l] CRUEL
At 17:17 14/08/02 -0300, you wrote: From: Bruno F. C. Leite [EMAIL PROTECTED] At 12:21 14/08/02 -0400, you wrote: Num polígono convexo de n lados, quando se constrói todas as diagonais aparecem pontos de interseção entre as diagonais. Determinar o número de pontos de interseção? Vamos supor que não há duas diagonais paralelas. Note que a cada ponto de intersecção podemos associar as duas diagonais ou o quadrilátero formado pelos extremos destas diagonais. Logo há uma bijeção entre o número de intersecções e o de quadriláteros com vértices contidos no conjunto de vértices do poligono...logo a resposta é binomial(n,4). Está certo? Bruno Leite http://www.ime.usp.br/~brleite Mas e se dois quadriláteros distintos tiverem o mesmo ponto de interseção das suas diagonais? Ou isso nunca ocorre por que nenhuma das diagonais é paralelas, por hipótese sua? Bem, isto que vc disse nao segue da hipótese que eu coloquei (veja o octógono regular) mas é também uma hipotese necessária para que o problema não dependa da forma particular do poligono (dependa só de n) Bruno Leite http://www.ime.usp.br/~brleite = 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] =
[obm-l] Re:[obm-l] Contagem difícil - ajuda
A resposta não seria 24!/12? __ AcessoBOL, só R$ 9,90! O menor preço do mercado! Assine já! http://www.bol.com.br/acessobol De quantas maneiras 24 pessoas podem subir numa roda gigante de 12 assentos, sabendo que cada assento comporta duas pessoas?
[obm-l] Numeros Complexos e Inversao
Sera que alguem poderia me ajudar a compreender melhor a inversao em numeros complexos?! Nao estou conseguindo entender muito bem esta teoria, principalmente a parte de preservação de angulos e tudo o mais... Um abraço,Leonardo _ Tenha você também um MSN Hotmail, o maior webmail do mundo: http://www.hotmail.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] =
Re: [obm-l] CRUEL
A figura deveria ter sido a que está em anexo deste. fig.bmp Description: Windows bitmap
Re: [obm-l] CRUEL
From: Bruno F. C. Leite [EMAIL PROTECTED] At 17:17 14/08/02 -0300, you wrote: From: Bruno F. C. Leite [EMAIL PROTECTED] At 12:21 14/08/02 -0400, you wrote: Num polígono convexo de n lados, quando se constrói todas as diagonais aparecem pontos de interseção entre as diagonais. Determinar o número de pontos de interseção? Vamos supor que não há duas diagonais paralelas. Note que a cada ponto de intersecção podemos associar as duas diagonais ou o quadrilátero formado pelos extremos destas diagonais. Logo há uma bijeção entre o número de intersecções e o de quadriláteros com vértices contidos no conjunto de vértices do poligono...logo a resposta é binomial(n,4). Está certo? Bruno Leite http://www.ime.usp.br/~brleite Mas e se dois quadriláteros distintos tiverem o mesmo ponto de interseção das suas diagonais? Ou isso nunca ocorre por que nenhuma das diagonais é paralelas, por hipótese sua? Bem, isto que vc disse nao segue da hipótese que eu coloquei (veja o octógono regular) mas é também uma hipotese necessária para que o problema não dependa da forma particular do poligono (dependa só de n) Bruno, eu não compreendi toda a discussão. Então vou recomeçá-la. Num polígono de n lados, cujos pares de diagonais não são paralelos, existe uma bijeção entre o número de interseções e o de quadriláteros com vértices contidos no conjunto de vértices do poligono. A minha pergunta deveria ter sido a seguinte: por que, sob essas hipóteses (de o polígono ser convexo e nenhum par de diagonais ser paralelo), não existem dois quadriláteros distintos com vértices contidos no conjunto de vértices do polígono cujos pontos de interseção das diagonais são o mesmo ponto? Vai em anexo uma figura. Em FIG 1: AE, BF, CG e DH são diâmetros. O problema do polígono ABCDEFGH é que muitas das diagonais são paralelas. Eu ACHO que trazendo A, B, C e D um pentelhésimo (em FIG 2) para dentro do círculo, a gente pode fazer com que todas as diagonais deixem de ser paralelas. Daí teríamos o ponto central do círculo interseção das diagonais dos quadriláteros ACEG e BDFH, o que invalidaria a bijeção do Bruno. Mas essa é só uma impressão minha, não sei se de fato está certo esse meu achismo. Eduardo. fig.bmp Description: Windows bitmap
[obm-l] Re: [obm-l] Re: [obm-l] Tradução de Problema
Paulo, eu estava lendo o problema achando que ele iria pedir outra coisa, por isso minha dificuldade de interpretar o óbvio. Agora que consegui entender, agradeço pelas suas palavras. Encontrei um algoritmo muito simples, provavelmente o que a banca tinha em mente. Misture os dois baralhos, o que vamos ter são cartas (A|B) de forma que A é diferente de B e cada número aparece em exatamente duas cartas. Comece pela carta (1|X) aí encontre a carta (X|Y) e assim por diante até que se chegue a (Z|1). Formamos uma roda desses dominós, por exemplo: (1|5), (5|2), (2|91), (91|56), (56|1). Pegamos um dominó dos que não foram escolhidos e fazemos uma roda do mesmo jeito. No final vamos ter uma porção de rodas. Colocamos os dominós na mesa na ordem da roda: (1|5), (5|2), (2|91), (91|56), (56|1). Daí cada dois números iguais vão estar em posições opostas, portanto temos a construção pedida. Eduardo. From: Paulo Santa Rita [EMAIL PROTECTED] Ola Duda e demais colegas desta lista ... OBM-L O que precisa ser mostrado é exatamente o que pede o enunciado do problema : as cem cartas sobre a mesa com os numeros de 1 a 100 visiveis, sem faltar nenhum deles ... Em que consiste o problema ? Nao e evidente que - INDEPENDENTE DA MANEIRA COMO OS NUMEROS FORAM GRAFADOS NOS DOIS BARALHOS - seja possivel exibir os 100 numeros, sem que haja omissao de algum numero. A parte matematica ( algoritmica )da questao consiste precisamente em mostrar que uma tal exibicao sempre é possivel. Uma parafrase do problema pode ser : Mostre como isabel pode escolher cada carta, determinando qual numero ficara por cima e qual ficara por baixo, de forma que no final da centesima escolha as faces visiveis exponham os 100 numeros naturais. Uma sintaxe adequada pode ser : Sejam A e B os baralhos. Ao escolher uma carta de um dos baralhos ( digamos, do baralho A ) teremos um par (V,I) em que V e o numero que ficara pra cima ( visicel ) e I o numero que ficara pra baixo ( invisivel ).O Mesmo vale para o baralho B. O inicio de um algoritmo pode ser : 1) Escolha a carta do baralho A onde esta o numero 1. Seja X o numero que acompanha 1 no baralho A. Colocamos a carta na forma (1,X). 2) Procure a carta do baralho B que tem o numero X. Seja Y o numero que acompanha o numero X no baralho B. Colocamos esta carta na forma (X,Y) 3) Y=1 ? Se nao, procure no baralho A ... E assim sucessivamente. Voce deve mostrar que o algoritmo descrito permite - INDEPENDENTE DA MANEIRA COMO OS NUMEROS FORAM GRAFADOS NOS DOIS BARALHOS - exibir as 100 cartas com os 100 numeros visiveis, sem que nenhum seja omitido. Eu nao parei para analisar se o algoritmo acima funciona. Estou apenas explicando o que e problematico e o que o problema requer. Muito provavelmente ha um algoritmo otimo para a questao, que e trivial. Um abraco a Todos Paulo Santa Rita 4,1958,140802 From: Eduardo Casagrande Stabel [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] Tradução de Problema Date: Wed, 14 Aug 2002 18:15:53 -0300 Olá pessoal da lista, alguém sabe como eu devo interpretar o seguinte problema? Isabel tem dois baralhos, cada um com 50 cartas. Em cada um dos baralhos estão escritos os números de 1 a 100 (em cada carta estão escritos dois números, um em cada face da carta). Por um defeito de fabricação, a distribuição dos números nas cartas não é a mesma nos dois baralhos (por exemplo, em um dos baralhos o 1 aparece na mesma carta do 2; no outro, o 1 aparece com o 76). Mostre como Isabel deve fazer para que, ao colocar as 100 cartas sobre uma mesa, as faces voltadas para cima mostrem todos os números de 1 a 100. Eu não entendi o que precisa ser mostrado, para mim não está nada claro sob que condições ela pode colocar as cartas na mesa, alguém sabe? Valeu! Eduardo. Porto Alegre, RS. PS. caiu na obm de 2000, fase 3, níveis 1 e 2. = 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] = _ Tenha você também um MSN Hotmail, o maior webmail do mundo: http://www.hotmail.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]
