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.