Re: [obm-l] Problemas da IMO

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

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