[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Duas Questoes interessantes !
On Mon, 15 Jan 2001, Paulo Santa Rita wrote:
> Ola Iolanda e Amigos da Lista,
> Saudacoes !
>
> Neunhum dos dois problemas e simples e ambos ja apareceram nesta Lista. Para
> que voce possa ter uma ideia da dificuldade que eles encerram, saiba que o
> primeiro - sobre esferas -, em tempos idos, foi abordado por Newton , que
> nao o resolveu ; o segundo - sobre campeonatos - apareceu aqui em uma versao
> com oito clubes e nehuma solucao consistente foi apresentada ...
>
> E verdade que se encontrou o numero 16 como "solucao" do segundo problema,
> mas este numero nao foi justificado com rigor, sendo antes "encontrado" em
> virtude das facilidades de visualizacao e diagramacao que os pequenos
> numeros envolvidos ofereciam.
> >2)Num campeonato com 36 clubes, cada time joga uma unica vez com todos os
> >demais. A Vitoria vale 3 pontos, o empate um ponto e a derrota nao confere
> >pontos. Qual a quantidade minima de pontos que um clube precisara fazer
> >para
> >ter certeza que ficara entre os 12 primeiros ?
H� muito tempo atr�s, Luiz Lopes escreveu:
> Num octogonal, oito times disputam o acesso ao quadrangular final de um
> campeonato. Sabendo que:
>
> i) cada time joga com cada um dos outros uma �nica vez;
>
> ii) que se um time vencer um jogo, ganha TR�S pontos;
>
> iii) se empatar, ganha UM ponto;
>
> iv) se perder, n�o ganha nem perde ponto,
>
> qual � o n�mero m�nimo de pontos que um time deve alcan�ar para assegurar
> sua inclus�o dentre os quatro times que passar�o para o quadrangular final?
A mensagem est� arquivada em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200007/msg00119.html
Ou seja, o problema j� discutido tinha n�meros diferentes.
Ralph respondeu:
> ...e 15 tamb�m n�o � suficiente...
>
> A B C D E F G H
> A - 0 0 3 3 0 0 0
> B 3 - 3 0 0 0 0 0
> C 3 0 - 0 3 0 0 0
> D 0 3 3 - 0 0 0 0
> E 0 3 0 3 - 0 0 0
>
> F 3 3 3 3 3 - ? ?
> G 3 3 3 3 3 ? - ?
> H 3 3 3 3 3 ? ? -
> Total 15 15 15 15 15 <6 <6 <6
>
> Aqui, F, G e H s�o dos m�dulos arco-�ris, fraquinhos, e n�o ganham de
> ningu�m. Entre os outros cinco, h� exatamente 5x4/2=10 jogos, e d�
> direitinho para cada um ganhar dois jogos como assinalado acima. Todos
> t�m 15 pontos, algu�m vai rodar...
A mensagem do Ralph est� em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200007/msg00139.html
Est� bem claro que n�o podemos ter 5 times com 16 ou mais pontos cada.
Sejam A, B, C, D, E os times bons e F, G, H os times fracos.
Podemos supor sem perda de generalidade que F ganha de G que ganha de H
que ganha de F: isto n�o afeta o desempenho dos grandes e d� a cada um
pelo menos 3 pontos. Assim o total de pontos de todos os times seria
pelo menos 5*16 + 3*3 = 89. Mas s�o disputadas 28 partidas e em cada
partida os dois times ganham juntos no m�ximo 3 pontos. Assim o m�ximo
de pontos de todos os times juntos � 28*3 = 84. Absurdo.
O que ningu�m apresentou (acho que � disso que o PSR est� falando)
foi um m�todo geral que servisse para varia��es simples, mudando
por exemplo o n�mero de clubes no in�cio ou o n�mero de clubes classificados
para a fase seguinte.
Para o novo problema, 87 pontos n�o bastam mas 88 bastam.
Sejam A, B, ..., M os 13 times bons e N, ... os 23 times fracos.
Sempre que um time bom joga com um fraco o time bom vence.
A tabela entre os times bons foi assim:
A B C D E F G H I J K L M
A - 3 3 3 3 3 3 0 0 0 0 0 0
B 0 - 3 3 3 3 3 3 0 0 0 0 0
C 0 0 - 3 3 3 3 3 3 0 0 0 0
D 0 0 0 - 3 3 3 3 3 3 0 0 0
E 0 0 0 0 - 3 3 3 3 3 3 0 0
F 0 0 0 0 0 - 3 3 3 3 3 3 0
G 0 0 0 0 0 0 - 3 3 3 3 3 3
H 3 0 0 0 0 0 0 - 3 3 3 3 3
I 3 3 0 0 0 0 0 0 - 3 3 3 3
J 3 3 3 0 0 0 0 0 0 - 3 3 3
K 3 3 3 3 0 0 0 0 0 0 - 3 3
L 3 3 3 3 3 0 0 0 0 0 0 - 3
M 3 3 3 3 3 3 0 0 0 0 0 0 -
Portanto os 13 times bons tiveram 29 vit�rias e 6 derrotas cada,
87 pontos cada, e um deles deve ser desclassificado.
Por outro lado com 88 pontos o time garante a sua classifica��o.
Podemos montar uma tabela entre os 23 times fracos que garanta
11 vit�rias para cada um deles
(exerc�cio; dica: baseie-se na tabela acima)
e portanto pelo menos 33 pontos para cada time fraco.
Mas o total de pontos de todos os times agora seria pelo menos
88*13 + 33*23 = 1903.
Por outro lado temos 630 partidas; mesmo se nenhuma empatar
o total de pontos de todos os times seria 1890. Absurdo.
[]s, N.