[obm-l] Re: [obm-l] Re:[obm-l] Olímpiada. Nível 2. Fase 3.

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

Sinceramente, eu nao consegui entender a sua solucao.
Acabei me perdendo (e perdendo o saco) com todos aqueles casos...

A solucao que mais me agradou foi a segunda proposta pelo Paulo Santa Rita.
Eh, na minha opiniao, a solucao do "Livro" pra esse problema.

Eu mencionei inducao porque, de fato, eh muito usada em teoria dos grafos - consulte qualquer livro introdutorio a respeito - e 
ilustra um uso mais interessante dessa tecnica do que provar que 1^2+2^2+...+n^2 = n(n+1)(2n+1)/6.


[]s,
Claudio.


---------- Cabeçalho original -----------

De: owner-obm-l@mat.puc-rio.br
Para: obm-l@mat.puc-rio.br
Cópia: 
Data: Mon, 14 May 2007 07:49:39 -0400
Assunto: Re: [obm-l] Re:[obm-l]  Olímpiada. Nível 2. Fase 3.

> 
>    Prezado Cláudio: 
> 
>    Obrigado pela dica, e, em realidade, pela aula. 
> 
>    Por gentileza, se possível, aquela solução que eu dei é então
>    particular e de pouca possibilidade de generalização para problemas
>    desse tipo? É isso?
> 
>    Fraternalmente, João.
> 
>    Uma idéia é usar teoria (elementar) dos grafos e demonstrar a
>    proposição por indução no número de vértices. Essa é uma técnica muito
>    utilizada (em teoria dos grafos) e, portanto, vale a pena tê-la em
>    mente na hora de uma prova (especialmente de olimpíada). Além disso, a
>    linguagem de grafos é muito útil na hora de visualizar o problema
>    (afinal, o que pode ser mais básico do que vértices e arestas, ou
>    seja, pontos e linhas?)
> 
>    Se existem n jogadores, você pode representar o torneio por um grafo
>    orientado com n vértices (numerados de 1 a n) e tal que, dados
>    quaisquer i <> j, se o jogador i venceu o jogador j então existe uma
>    seta (aresta orientada) indo do vértice i ao vértice j. A condição do
>    enunciado implica que o grafo não possui ciclos orientados, ou seja,
>    vértices distintos i_1, i_2, ..., i_k (k>=3) com setas indo de i_1
>    para i_2, i_2 para i_3, ..., i_(k-1) para i_k e i_k para i_1.
> 
>    O problema é provar que existe um vértice de onde partem n-1 setas
>    (uma fonte) e um vértice onde chegam n-1 setas (um dreno).
> 
>    Tomemos inicialmente n = 3.
>    Se não existir uma fonte, então cada vértice tem pelo menos uma seta
>    chegando. Se algum vértice tiver duas setas chegando, este será um
>    dreno.
>    Mas, nesse caso, a terceira seta do grafo, que liga os outros dois
>    vértices, irá (obviamente) partir de um deles. Este será a fonte. Por
>    outro lado, se cada vértice tiver uma seta partindo e uma chegando,
>    então teremos um ciclo, o que é proibido pelo enunciado. Logo, o caso
>    n = 3 está provado.
> 
>    Tomemos agora n >= 3 e suponhamos (hipótese de indução) que o
>    resultado seja verdadeiro para grafos com até n vértices.
> 
>    Considere um grafo com n+1 vértices.
>    Suponhamos que nenhum vértice seja uma fonte ou um dreno.
>    Retire temporariamente um vértice qualquer e as n setas que chegam a
>    ele ou partem dele, e considere o sub-grafo de n vértices resultante.
>    Pela hipótese de indução, este grafo possui uma fonte F e um dreno D.
> 
>    Recoloque agora o vértice V que você retirou.
>    Se ele recebe uma seta de F e manda uma seta para D, acabou: F e D são
>    a fonte e o dreno do grafo maior (com os n+1 vértices).
> 
>    Caso contrário, temos três alternativas a considerar:
>    1) V manda uma seta para F e recebe uma seta de D:
>    Nesse caso, como F manda uma seta para D, FDVF é um ciclo.
>    Mas isso contraria o enunciado. Logo, esse caso não ocorre;
> 
>    2) V manda setas para F e para D:
>    Nesse caso, D é o dreno do grafo maior.
>    Se V receber alguma seta de algum vértice W, então WVFW é um ciclo,
>    pois F é a fonte do subgrafo e, portanto, manda uma seta para W.
>    Esta contradição mostra que este caso também não ocorre.
> 
>    3) V recebe setas de F e de D:
>    Esse caso é análogo ao anterior. Basta inverter o sentido das setas.
> 
>    Assim, vemos que a única possibilidade é que a fonte e o dreno do
>    subgrafo sejam a fonte e o dreno do grafo maior.
> 
>    Logo, pelo princípio da indução, o resultado vale para qualquer grafo.
> 
>    Ou seja, num torneio onde todo mundo joga com todo mundo, se vale a
>    "lógica" (ou seja, se não existem ciclos - situações onde A vence B,
>    que vence C, que vence A), então tem um jogador que vence todo
>    mundo e outro que perde pra todo mundo.
> 
>    []s,
>    Claudio.
> 
>    De: owner-obm-l@mat.puc-rio.br
> 
>    Para: obm-l@mat.puc-rio.br
> 
>    Cópia:
> 
>    Data: Fri, 11 May 2007 08:08:26 -0400
> 
>    Assunto: [obm-l] Olímpiada. Nível 2. Fase 3.
> 
>    Solicito, por gentileza, correção da resolução (ou tentativa de
>    resolução) da questão que segue.
> 
>    PROBLEMA 6
>    Em um torneio de tênis de mesa (no qual nenhum jogo termina empatado),
>    cada um dos n participantes jogou uma única vez contra cada um dos
>    outros. Sabe-se que, para todo k > 2, não existem k jogadores J1, J2,
>    ?, Jk tais que J1 ganhou de J2, J2 ganhou de J3, J3 ganhou de J4, ?,
>    Jk ? 1 ganhou de Jk, Jk ganhou de J1. Prove que existe um jogador que
>    ganhou de todos os outros e existe um jogador que perdeu de todos os
>    outros.
> 
>    TENTATIVA DE RESOLUÇÃO
> 
>                As hipóteses:
>    1)     Não há empate.
>    2)     Cada jogador joga uma e só uma vez com cada um dos outros.
>    3)     Sabe-se que, para todo k > 2, não existem k jogadores J1, J2,
>    ?, Jk tais que J1 ganhou de J2, J2 ganhou de J3, J3 ganhou de J4, ?,
>    Jk ? 1 ganhou de Jk, Jk ganhou de J1.
>    A tese: Existe um jogador que ganhou de todos e um que perdeu de
>    todos.
>                Bem, com três jogadores: J1, J2, J3. É sabido que a única
>    hipótese que não existe é: J1>J2, J2>J3 e J3> J1. Logo, só pode
>    existir, sem perda de generalidade: J1>J2, J2>J3 e J3< J1, ou seja,
>    J1>J2>J3. Cabe explicar que o símbolo ?>? utilizado significa, por
>    exemplo: ?Jogador 1 ganhou do Jogador 2?.
>                Com quatro jogadores, não temos: J1>J2, J2>J3, J3> J4 e
>    J4>J1. Assim, podemos trocar um ou dois desses sinais de > para <.
>    Então, temos: (>, >, >, <) ou (>, >, <, <). Assim, no primeiro caso,
>    J4 será o que perdeu de todos; no segundo, será J3; e em ambos, J1
>    ganhou de todos.
>    Com n jogadores: É sabido que não temos: (>,>,>, ... , >). Entre esses
>    parêntesis, há n ?>?. Com n par, podemos trocar ?>? para ?<? k vezes,
>    k de n a n/2, se n é par (ordem decrescente). Assim, em todos esses
>    casos J1 será o que ganhou de todos e Jk será o que perdeu de todos.
>    Se n é ímpar, k varia (ordem decrescente também) de n até o primeiro
>    inteiro maior que n/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
>    ======================================================================
>    ==
> 


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