1. Let A be a 101-element subset of the set S={1,2,3,...,1000000}. Prove
that
there exist numbers t_1, t_2, ..., t_{100} in S such that the sets
Aj = { x + tj | x is in A } for each j = 1, 2, ..., 100
are pairwise disjoint.
----
Eu tive uma id�ia pra esse aqui...
Seja A = {u1, ..., u100} onde u1 < u2 < ... < u100
as diferen�as dois a dois (positivas) s�o:
u2 - u1, u3 - u2, ..., u100 - u99
u3 - u1, u4 - u2, ..., u100 - u98
...
u[k] - u1, ..., u100 - u[101 - k]
num total de 99 + 98 + ... + 1 = 50*99 diferen�as
tome t1 = 0.
t2 n�o pode ser nenhuma das diferen�as acima, a id�ia que tive � que parece
plaus�vel acreditar que existe um valor m de tal forma que m, 2m, ... 99m
n�o s�o nenhuma dessas diferen�as.
Se isso for verdade, poder�amos definir A{j+1} = {u[i] + j*m / i = 1...100}.
de forma que, se k < i:
u[i] + j*m = u[k] + l*m <=> u[i] = u[k] + (l - j)*m <=> l - j > 0
mas se l - j > 0, l -j < 100 e, pela conjectura acima, (l-j)*m n�o pode ser
igual a nenhuma diferen�a entre os u'is!
A partir da� vemos que os conjuntos Aj s�o disjuntos.
Agora vou explicar porque eu acho plaus�vel assumir que existe um m dessa
forma:
Fiz um programinha que conta o n�mero de divisores de cada inteiro em S e
coloca num vetor, na i'�sima posi��o, o n�mero de inteiros que possuem
exatamente i divisores.
Depois dessa conta meio pesada (mas que n�o chega a levar 15 minutos no meu
PIII 700) eu conto de forma gulosa* o n�mero m�ximo de divisores distintos
que um subconjunto de S com 50*99 elementos pode ter, esse n�mero foi
estritamente menor que 10^6.
*a conta gulosa � feita assim: pegamos os elementos com o maior n�mero
poss�vel de divisores e consideramos que eles s�o todos distintos, varremos
o vetor de tr�s pra frente somando o produto n�mero de inteiros em S com N
divisores vezes N.
[ ]'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
=========================================================================
