|
estou achando esse problema meio
estranho...
se for pra provar que dado qualquer escolha de
2^(2n - 1) + 1 �mpares entre (2^(2n), 3^(2n)) sempre h� dois �mpares a, b tais
que a� n�o divide b� e nem b� divide a�:
se a� | b�
<=> existe c inteiro tq. b� =
c.a�
<=> (b - raiz(c).a)(b +
raiz(c).a) = 0
<=> b = +/- raiz(c).a, como a e b s�o
inteiros c deve ser quadrado perfeito, c = d� pra um inteiro
<=> b = +/- d.a <=> a | b
considere qualquer conjunto ordenado de t = 2^(2n -
1) + 1 �mpares entre (2^(2n), 3^(2n))
{x1, x2, ..., x[t]}
queremos verificar que n�o h� jeito de manter a
propriedade x[i] | x[j] para todo 1 <= i <= j <= t, ou seja �
imposs�vel n�o haver dois elementos cujos quadrados n�o podem ser
m�ltiplo/divisor.
bom, temos que x2 = y1*x1 para algum y1 inteiro, y1
> 1, pois x2 != x1, al�m disso y1 != 2 pois x2 � �mpar, logo y1 >=
3.
da mesma forma x3 = y2*x2 = y2*y1*x2 e y2 >= 3
pelo mesmo racioc�nio... logo x3 >= 9x1, x4 >= 27x1...
x[t] >= 3^[2^(2n - 1)]x1, mas isso � bem maior
do que 3^(2n), e isso � o que me cheira estranho.... problemas desse tipo nunca
deixam uma margem t�o folgada assim... ser� que eu interpretei o problema de
forma errada ou o enunciado est� errado, ou ainda, h� um erro no meu racioc�nio
exposto nesta mensagem?
[ ]'s
|
- Re: [obm-l] olimp�adas ao redor do mundo..... DEOLIVEIRASOU
- [obm-l] Re: [obm-l] olimp�adas ao redor do mundo..... Domingos Jr.
- Re: [obm-l] olimp�adas ao redor do mundo..... Claudio Buffara
- Domingos Jr.
