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: [EMAIL PROTECTED] Para: [email protected] 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: [EMAIL PROTECTED] > > Para: [email protected] > > 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 =========================================================================
