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 X>Y.
> > Abra�o. Pedro.
>
>***********************************
>O enunciado do problema nao diz que X<>Y. 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)
>X>Y;
>(2) X=Y; e (3) X<Y. 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 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]>
>=========================================================================
_________________________________________________________________
Converse com seus amigos online, fa�a o download gr�tis do MSN Messenger:
http://messenger.msn.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]>
=========================================================================
