Re: Duas Questoes interessantes !

[Ralph Costa Teixeira <ralph@xxxxxxxxxxxxxxx>]

	Oi, Iolanda.

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

	De fato, a gente já tinha discutido aqui na lista esse problema para
um octagonal onde apenas 4 times se classificam... Eu acho que agora
consegui generalizar a idéia que a gente tinha usado antes para
qualquer n par (n é o número de clubes que se classificam). Mas
primeiro, deixa eu dar a idéia usando o problema da Iolanda -- 36
times, 12 se classificam.

	Nota: a idéia principal do problema está nos itens (i) e (ii), o
resto são detalhes técnicos necessários para evitar surpresas.

	i) Primeiro eu vou mostrar que 87 pontos não são suficientes. De
fato, imagine a seguinte situação: há dois tipos de times, sendo 13
fortes e 23 fraquinhos, e os fraquinhos sempre perdem dos fortes.
Chame os "fortes" de T1, T2, ..., T13, e imagine que:

	T1 ganha de T2,T3,...,T7 mas perde de T8,T9,...,T12,T13
	T2 ganha de T3,T4,...,T8 mas perde de T9,T10,...,T13,T1
	T3 ganha de T4,T5,...,T9 mas perde de T10,T11,...,T1,T2
	...
	Ti ganha de T(i+1),...,T(i+6) mas perde de T(i+7),...,T(i+12)
	...
	T13 ganha de T1,T2,...,T6 mas perde de T7,T8,...,T12

onde os índices são calculados módulo 13. Uma maneira compacta de
escrever isto é

	Ti ganha de Tj se (i-j)mod13 = 1,2,3,4,5 ou 6

	É importante notar que as hipóteses acima são coerentes, isto é, se a
linha i diz que Ti ganha de Tj, então a linha j diz que Tj perde de Ti
(ainda bem -- a notação compacta ajuda a ver isto).

	Assim, esta é uma situação onde esses 13 times ganham 23+6=29
partidas e ainda assim um deles fica de fora das finais (no saldo de
gols ou no tapetão, sei lá)... Isso prova que 29x3=87 pontos não é
suficiente para GARANTIR um lugar nas finais.

	ii) Por outro lado, uma quantia de 88 ou mais pontos é suficiente. Se
você olhar para os 13 times melhor classificados, eles estão
envolvidos em 13x23+13x12/2=13x29 jogos (a primeira parcela
corresponde aos jogos contra os outros 23 e a segunda aos jogos que
esses 13 disputam entre si). Assim, esses 13 times disputam
13x29x3=13x87 pontos NO MÁXIMO. É impossível que esses 13 times tenham
88 ou mais pontos (13x88>13x87).... assim 88 (ou qualquer quantia
maior) garante a 12a colocação (ou melhor) e a sua presença nas
finais. De certa maneira, a situação em (i) é a situação "limite"...

	iii) Vale a pena notar que, só porque 87 não é suficiente, não quer
dizer que 86 não é (apesar de a intuição querer gritar isso)! Para
provar que 86 também não dá, comece da situação em (i) acima e
modifique-a ligeiramente colocando empates nos seguintes jogos:

	T1 vs. T2, T2 vs. T3 e T3 vs. T8

	O resto mantenha como antes. Assim, há 10 times fortes com os mesmos
87 pontos de antes, e esses 3 citados acima passam a 86 (cada um troca
uma vitória e uma derrota por dois empates). Um deles fica de fora...
então 86 não é suficiente.

	iv) Não é difícil ver que 85 ou menos definitivamente também não é
suficiente (basta modificar a situação de (i) onde o seu time perdeu
pontos contra os "fracos" e acabou com n<85 pontos, enquanto os
confrontos envolvendo os fortes são os mesmos... isso dá para fazer
com n entre 18 e 85 mantendo a tabela de confrontos entre os fortes;
se n<18, pô, aí não dá mesmo... precisamente, é fácil modificar também
os jogos contra os fortes e fazer você perder mais pontos ainda sem
piorar a vida dos "fortes").

	==//==

	Ufa! Isso fecha o problema. Note que o raciocínio acima pode ser
facilmente generalizado sempre que o número de classificados for par.
Em outras palavras, se m times disputam um campeonato, cada um jogando
com cada um apenas uma vez, e os n=2k primeiros se classificam (com
n<m), então 3(m-k)-2 é o menor número de pontos necessário para
GARANTIR a vaga... De fato:

	-- Um grupo qualquer de n+1 times disputa
(n+1)(m-n-1)+n(n+1)/2 = (n+1)(2m-n-2)/2 partidas, ou seja,
3(n+1)(2m-n-2)/2 pontos.

	-- Assim, o pior desses n+1 times terá no máximo
3(2m-n-2)/2 = 3(m-k-1) pontos; isto prova que
3(m-k-1) + 1 = 3m-3k-2 é suficiente para passar à fase final.

	-- PARA n PAR, é sempre possível criar uma tabela onde n+1 times
fortes ganham de todos os m-n-1 times fracos e ganham exatamente
metade (n/2) das partidas jogadas entre si (basta repetir o processo
acima, feito para n+1=13 times). Neste caso, cada time alcança
exatamente 3m-3k-3 pontos e, portanto, isto não é suficiente -- um
deles vai ficar de fora.

	iv) Enfim, a idéia de botar três dos times do grupo forte para
empatarem entre si funciona e mostra-se que 3m-3k-4 também não dá.
Para valores ainda menores, é fácil ver que você não garante
classificação.

	Só para conferir... No caso m=36 e n=12 (k=6), precisamos de 3(m-k)-2
= 3x30-2 = 88 pontos. Beleza, é isso aí! Na "querida" copa JH, m=25 e
n=12 indica 3(25-6)-2 = 55 pontos --- note como isso está BEM acima do
que foi realmente preciso para chegar às finais.

	Abraço,
		Ralph

P.S.: Fica aí pra galera o caso em que n=2k-1 é ímpar... O raciocínio
acima do tipo casa-dos-pombos mostra que 3(m-k)-1 é suficiente...
Quanto a 3(m-k)-2, eu acho que dá para pegar n+1=2k times fortes e os
outros m-2k times fracos e montar uma campanha onde os fortes sempre
vencem os fracos, mas entre si os fortes têm campanhas iguais do tipo
k-1 Vitórias, 1 Empate e k-1 Derrotas. Assim, cada um dos fortes teria
3(m-2k) + 3(k-1) + 1 = 3m-3k-2 pontos e um vai rodar, mostrando que
3(m-k)-2 não é suficiente... Falta montar a tal campanha com cuidado.