RE: [obm-l] teoria combinatoria dos numeros(?) [Era: probleminhas]

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Oi, gente,

Não tenho certeza se esse fato está relacionado com o
problema que vocês estão discutindo, mas é verdade
que, sendo a e b inteiros primos entre si, o maior
inteiro que não pode ser escrito da forma ax + by,
sendo x e y inteiros não negativos, é ab - a - b.

Primeiro, provemos que ax + by = ab - a - b não pode
ter solução (x,y) com x e y ambos não negativos. vendo
a equação mód b, obtemos ax = -a (mód b), ou seja, x =
-1 (mód b). Logo se x >= 0 então na verdade x >= b-1.
Analogamente, se y >= 0 então y >= a-1. Portanto se x
>= 0 e y >= 0, então ax + by >= a(b-1) + b(a-1) = 2ab
- a - b > ab - a - b, absurdo.

Se você não sabe ou não quer usar congruências, pode
pensar assim: ax + by = ab - a - b é equivalente à
equação a(x - b + 1) = b(-y - 1). Logo, sendo a e b
primos entre si, b divide x - b + 1, ou seja, x - b +
1 = bt ou x = bt + b - 1. Como x >= 0, t >= 0 e,
portanto, x >= b - 1.

Agora, provemos que todo inteiro c maior ou igual a
ab-a-b+1 pode ser escrito da forma ax + by, com x >= 0
e y >= 0. Como a e b são primos entre si, existem
(x_0,y_0) tais que ax_0 + by_0 = c (isso decorre do
teorema de Bezóut, que diz que, dados a,b inteiros, o
menor inteiro positivo que pode ser escrito da forma
ax + by, x,y inteiros, é mdc(a,b); no nosso caso, esse
mdc é 1, então é possível encontrarmos x e y tais que
ax + by = 1; para obter o que queremos, é só
multiplicar x e y por c). Observe que se (x_0, y_0) é
solução, então (x_0 - bt, y_0 + at) também é solução,
sendo t inteiro. Tome então t tal que 0 <= y_0 + at <=
a-1 (esse t existe sim! tente entender por quê
desenhando uma reta real). Resolvendo a inequação
obtemos -y_0/a <= t <= (a-1-y_0)/a. Agora, veja que
x_0 - bt >= x_0 - b(a-1-y_0/a) = (ax_0+by_0-ab+b)/a =
(c-ab+b)/a >= (ab-a-b+1-ab+b)/a = -1 + 1/a > -1. Que
azar, a nossa nova solução x_0-bt é maior que um
negativo, e isso não prova nada! Calma lá! Esse número
é inteiro e maior que -1, logo é maior ou igual a
zero, e acabou! Temos (x_0-bt,y_0+at) como solução com
x_0-bt >=0 e y_0+at >= 0.

Espero ter ajudado.

[]'s
Shine

--- Qwert Smith <lord_qwert@hotmail.com> wrote:

> 
> Uma coisa interessante de notar (ou nao) e que xy -
> x - y e quase xy - x - y 
> + 1
> 
> logo x.y - (x+y) = (x-1)(y-1) - 1
> 
> Re-escrevendo isso... Se temos moedas p e q podemos
> fazer todo tipo de troco 
> de (p-1)(q-1) pra cima desde que o numero de moedas
> a disposicao seja 
> infinito.  Pra quem ja viu crioptografia rsa percebe
> n=pq e m=(p-1)(q-1).  
> Nao sei se e pura coincidencia ou nao.  Talvez
> aquele colega que jura ter 
> quebrado o RSA pode elucidar alguma coisa.  Eu de
> minha parte prefiro 
> abandonar o problema por aqui pra nao ser abduzido
> por seres extraterrestres 
> ou agentes da cia.
> 
> 
> 
> >From: Luís Lopes <qed_texte@hotmail.com>
> >Reply-To: obm-l@mat.puc-rio.br
> >To: obm-l@mat.puc-rio.br
> >Subject: [obm-l] teoria combinatoria dos numeros(?)
> [Era: probleminhas]
> >Date: Wed, 08 Mar 2006 20:38:08 +0000
> >
> >Sauda,c~oes,
> >
> >Discuto esse problema (ou melhor, a fórmula)
> >
> >>número maximo = X . Y - ( X + Y )
> >
> >na solução do problema 15 do livro É divertido
> resolver problemas.
> >Ver o link
> >
> >http://www.escolademestres.com/qedtexte/sol1.pdf
> >
> >>alguem sabe provar isso???
> >Ou refutar??
> >
> >Também não sei.
> >
> >[]'s
> >Luís
> >
> >
> >>From: "Felipe Avelino" <felipeavelino@gmail.com>
> >>Reply-To: obm-l@mat.puc-rio.br
> >>To: obm-l@mat.puc-rio.br
> >>Subject: Re: [obm-l] probleminhas
> >>Date: Wed, 8 Mar 2006 16:05:59 -0300
> >>
> >>isso se torna muito cansativo no caso de um numero
> muito grande...
> >>
> >>existe uma forma que se eu me recordo eh...no caso
> de dois numeros X e Y
> >>primos entre si.. que eh
> >>
> >>número maximo = X . Y - ( X + Y )
> >>
> >>alguem sabe provar isso???
> >>deve envolver teoria combinatoria dos numeros ..
> não sei ..
> >>
> >>Em 08/03/06, João Gilberto Ponciano Pereira
> <jopereira@vesper.com.br>
> >>escreveu:
> >> >
> >> > Cheguei em 23...
> >> >
> >> > A lógica que usei é a seguinte.... Temos que
> conseguir o menor número 
> >>das
> >> > unidades. Após isso, basta somar 2 vezes a cota
> de 2 bombons de 5.
> >> >
> >> > Temos então que achar a combinação de bombons
> tal que o total seja o
> >> > mínimo, para cada uma das unidades. Temos
> então:
> >> >
> >> > 0 ==> 0  = 0x5 + 0x7
> >> > 1 ==> 21 = 0x5 + 3x7
> >> > 2 ==> 12 = 1x5 + 1x7
> >> > 3 ==> 33 = 1x5 + 4x7
> >> > 4 ==> 14 = 0x5 + 2x7
> >> > 5 ==> 05 = 1x5 + 0x7
> >> > 6 ==> 26 = 1x5 + 3x7
> >> > 7 ==> 07 = 0x5 + 1x7
> >> > 8 ==> 28 = 0x5 + 4x7
> >> > 9 ==> 19 = 1x5 + 2x7
> >> >
> >> > logo.. como o maior desta lista é o 33, se
> subtrairmos 10, temos que o
> >> > maior número de bombons que não se pode vender
> com a combinação de 5 e 
> >>7
> >> > bombons é 23.
> >> >
> >> >
> >> > -----Original Message-----
> >> > From: owner-obm-l@mat.puc-rio.br
> [mailto:owner-obm-l@mat.puc-rio.br]On
> >> > Behalf Of Henrique Ren
> >> > Sent: Wednesday, March 08, 2006 1:28 PM
> >> > To: obm-l@mat.puc-rio.br
> >> > Subject: [obm-l] probleminhas
> >> >
> >> >
> >> > Encontrei esse probleminha e gostaria que
> alguém me ajudasse a 
> >>resolvê-lo:
> >> >
> >> > uma doceria venda caixas com 05 e 07 bombons
> dentro. qual o número 
> >>máximo
> >> > de
> >> > bombons que a doceria não consegue vender?
> >> > por exemplo: consegue-se vender 17 bombons
> porém não 11 bombons?
> >> >
> >> > []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
>
=========================================================================
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 
=========================================================================
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
=========================================================================