Re: [obm-l] Basquete Bizantino

["Domingos Jr." <dopikas@xxxxxxxxxx>]

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