Re: Duas Questoes interessantes !

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

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.