Re: [obm-l] Basquete Bizantino

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Oi, Domingos:

Rodar um programinha??? Essa ideia so podia vir um cientista da
computacao!!!

Mas tambem da pra fazer analiticamente e sem muito braco.

mdc(a,b) = 1 decorre do fato de haver apenas um numero finito de pontuacoes
impossiveis, ja que, por Bezout, todas as pontuacoes possiveis sao multiplas
de mdc(a,b). Assim, se este fosse > 1, haveria uma infinidade de pontuacoes
impossiveis.

Sugestao: voce ja quase provou que existe N, tal que para todo n > N, a
equacao aX + bY = n tem solucao inteira nao negativa mas aX + by = N nao tem
uma tal solucao. Este N pode ser expresso em funcao de a e b.

Depois, um pouco de exploracao numerica pode sugerir uma conjectura para o
numero de pontuacoes impossiveis em funcao de a e b. Esta conjectura pode
ser provada de varias maneiras, mas a demonstracao mais elegante que eu
conheco eh bijetiva.

Um abraco,
Claudio.

on 28.04.03 19:46, Domingos Jr. at dopikas@uol.com.br wrote:

>> O jogo de basquete bizantino é igual ao basquete normal, exceto que cestas
>> curtas valem "a" pontos ao invés de 2 pontos e cestas de longa distância
>> valem "b" pontos ao invés de 3 pontos. No basquete bizantino existem
>> exatamente 35 pontuações que nunca ocorrem numa partida. Uma delas é 58.
>> Quanto valem "a" e "b"?
> 
> 
> os pontos possíveis são { aX + bY, X, Y >= 0 inteiros }
> se 58 não é uma pontuação possível, temos necessariamente que nem a nem b
> dividem 58, ou seja:
> a, b != { 1, 2, 29, 58 }
> 
> se existe um número finito de pontuações que nunca são obtidas temos que
> existe um inteiro N tal que, para todo n > N, existem X, Y tal que n = aX +
> bY
> 
> seja n + 1 = aX' + bY'
> 1 = a(X'-X) + b(Y'-Y)
> 
> isso nos diz que mdc(a, b) = 1
> assuma a < b (sem perda de generalidade)
> 
> aX + bY = aX' + bY' <=>
> a(X - X') = b(Y'-Y)
> mas então b|(X - X') e a|(Y - Y')
> 
> a.X + b.Y tem então valores distintos para 0 <= X <= b-1, 0 <= Y <= a-1
> ou seja há exatamente a.b pontuações distintas entre { 0, 1, ..., 2ab - a -
> b }
> 2ab - a - b + 1 - ab <= 35
> ab - a - b <= 34
> 
> a >= 3 pois a != { 1, 2 }
> ab - a - b <= 34 =>
> b(a-1) <= 34 + a
> b <= (34 + a)/(a-1)
> 
> dá pra limitar o problema a:
> podemos ver que a = { 3, 4, 5, 6 }
> pois se a = 7, b <= (34 + 7)/6 = 41/6 < 7
> 
> existem 20 possíveis valores de (a, b) que satisfazem a desigualdade acima e
> mdc(a, b)= 1, talvez dê pra rodar um programinha e verificar qual dessas 20
> comb. tem a propriedade desejada.
> 
> [ ]'s
> 
> =========================================================================
> 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
=========================================================================