Programa Olímpico de Treinamento

Curso de Combinatória – Nível 3 Aula 19

Prof. Carlos Shine

Teoria Aditiva dos Números

A teoria aditiva dos números se foca na operação de adição. Apesar de ser a operação mais
simples, ela não se mistura muito com o que muitos consideram a operação mais importante
da teoria dos números, que é a multiplicação.
Primeiro, um pouco de notação: sendo A e B conjuntos de números, definimos

A + B = {a + b; a ∈ A e b ∈ B}
A − B = {a − b; a ∈ A e b ∈ B}

Estimando |A + A|


Se A = {2i−1 , 1 ≤ i ≤ n}, pela unicidade da base 2, temos |A + A| = n2 + n, e isso é
o melhor que conseguimos. E quanto ao limitante inferior? De fato, temos 2|A| − 1 ≤
|A + A| ≤ |A|(|A|+1)
2 .

Teorema 1. Se |A| = n então |A+A| ≥ 2n−1, com igualdade se, e somente se, A consiste
em n termos consecutivos de uma progressão aritmética.

Demonstração: Sejam a1 < a2 < . . . < an os elementos de A. Note que

a1 + a1 < a1 + a2 < . . . < a1 + an < a2 + an < a3 + an < . . . < an + an ,

de modo que A + A tem pelo menos 2n − 1 elementos.

Para provar o caso de igualdade, note que, para 2 ≤ i ≤ n − 1,

a1 + a1 < a1 + a2 < . . . < a1 + ai < a2 + ai < . . . < an + ai < an + ai+1 < . . . < an + an

são 2n − 1 somas distintas, logo no caso de igualdade os termos devem coincidir. Em

particular,
a1 + ai+1 = a2 + ai ⇐⇒ ai+1 − ai = a2 − a1 ,
o que quer dizer que a diferença entre dois termos consecutivos do conjunto A é constante.
POT 2012 - Combinatória - Nı́vel 3 - Aula 19 - Prof. Carlos Shine

Conjuntos livres de somas

Dizemos que um conjunto A é livre de somas quando (A + A) ∩ A = ∅. Em outras palavras,
não existem x, y, z ∈ A tais que x + y = z. Por exemplo, o conjunto dos ı́mpares é livre
de somas, e o último teorema de Fermat nos diz que o conjunto das potências n-ésimas,
n ≥ 3, é livre de somas.
Se fixarmos o conjunto [n] = {1, 2, . . . , n}, com os ı́mpares conseguimos um subconjunto
livre de somas com ⌈n/2⌉ elementos. Será que conseguimos melhor? A resposta é: não.

Teorema 2. Todo subconjunto com mais de ⌈n/2⌉ elementos de [n] = {1, 2, . . . , n} não é
livre de somas.

Demonstração: Seja A um subconjunto de [n] com mais de ⌈n/2⌉. Como é difı́cil controlar
A + A, pois vários de seus elementos podem ser maiores do que n, considere no seu lugar
o conjunto X = (A − A) ∩ Z∗+ , de modo que queremos provar que X ∩ A 6= ∅. Sendo
A = {a1 , a2 , . . . , ak }, com a1 < a2 < . . . < ak , note que 0 < a2 −a1 < a3 −a1 < . . . < ak −a1 ,
de modo que |X| ≥ |A| − 1. Mas isso quer dizer que |A ∩ X| = |A| + |X| − |A ∪ X| ≥
2|A| − 1 − n > 0, e acabou.
A seguir, um resultado que já foi explorado, mas que vale a pena ser repetido.

Teorema 3. Todo conjunto finito B tem um subconjunto livre de somas com pelo menos
|B|/3 elementos.

Demonstração: A grande ideia é jogar algo sem muito estrutura (como nosso conjunto
B) para algo mais estruturado, no caso o conjunto Z/(p), p primo grande. Se p = 3k + 2,
o conjunto C = {k + 1, k + 2, . . . , 2k + 1} ⊂ Z∗ /(p) é livre de somas e tem k + 1 elementos,
k+1
uma fração 2k+1 > 31 .
Quando comparamos duas estruturas, a ideia que vem é tentar cruzá-las, com contagem
dupla, por exemplo. Z∗ /(p) tem boa estrutura, e a contagem ajuda a encontrar alguém,
mesmo que não haja estrutura em B. O que usamos? O “gira-gira”. Multiplique todos os
elementos de B por x, 1 ≤ x < p, e reduza módulo p. Nenhum b ∈ B é 0 módulo p, então
aparecem todos os resı́duos módulo p em bZ∗ /(p), ou seja, C aparece em todo bZ∗ /(p). Mas,
definindo Dx = xB (mod p), sendo |C| > 13 |Z∗ /(p)|, a probabilidade de algum elemendo
de D pertencer a C é maior do que 13 , e portanto o valor esperado de elementos de Dx em
C é maior do que |B|/3. Então existe um Dt com mais de |B|/3 elementos de C, e esse é
o subconjunto A que queremos. De fato, se a1 , a2 , a3 ∈ A são tais que a1 + a2 = a3 então
ta1 + ta2 ≡ ta3 (mod p), com ta1 , ta2 , ta3 ∈ C, absurdo. Logo A é livre de somas.

Teorema de Cauchy-Davenport
E quanto a Z/(p), o conjunto dos números tomados módulo p primo? O seguinte teorema
nos dá uma ideia:

Teorema 4 (Cauchy-Davenport). Sejam A e B dois subconjuntos não vazios de Z/(p).

Então
|A + B| ≥ min(|A| + |B| − 1, p).

2
POT 2012 - Combinatória - Nı́vel 3 - Aula 19 - Prof. Carlos Shine

Demonstração: Vamos cuidar da parte mais fácil primeiro: se |A|+|B|−1 ≥ p, |A|+|B| é

maior do que p, e pelo princı́pio da casa dos pombos, os conjuntos {x} − A (uma translação
de −A) e B se interceptam para todo x. Então existem a ∈ A e b ∈ B tais que x − a ≡ b
(mod p) ⇐⇒ x ≡ a + b (mod p), ou seja, A + B = Z/(p).
A partir de agora, vamos supor que |A|+|B|−1 < p. Suponha, por absurdo, que existem
conjuntos A e B tais que A + B 6= Z/(p) e |A + B| ≤ |A| + |B| − 2. Essa propriedade
continua verdadeira se trocamos B por B − {b}, b ∈ B (só subtraı́mos todas as somas em
b), de modo que podemos supor sem perda de generalidade que 0 ∈ B. Escolha A e B de
modo que |B| é minimal. Note que |B| ≥ 2, pois se |B| = 1, bom. . . B = {0}.
Agora, vamos definir a transformada de Davenport. Temos A+B ⊂ A+2B = (A+B)+
B, pois 0 ∈ B. Além disso, se A + B = A + 2B, A + 3B = (A + 2B) + B = (A + B) + B =
A+2B = A+B, e indutivamente A+nB = A+B. Mas se a ∈ A e 0 6= b ∈ B, a+nb ∈ A+B
para todo n; só que a + nb cobre todo Z/(p), e então A + B = Z/(p), o que não é verdade.
Logo A + B está propriamente contido em A + 2B, e o conjunto X = (A + 2B) \ (A + B)
não é vazio.
Sendo x ∈ X, seja

Bx∗ = {b ∈ B | x − b ∈ A + B}, Bx = B \ Bx∗ .

Note que Bx∗ são os caras de B que fazem com que x pertença a (A + 2B) \ (A + B), e
Bx são. . . os outros caras. O conjunto Bx é a transformada de Davenport.
Agora, veja que 0 ∈ / Bx∗ 6= ∅ e 0 ∈ Bx ⊂ B. Agora, é claro que A + Bx ⊂ A + B e
∗
{x} − Bx ⊂ A + B, de modo que

(A + Bx ) ∪ ({x} − Bx∗ ) ⊂ A + B.

Finalmente, note que se (A + Bx ) ∩ ({x} − Bx∗ ) 6= ∅, ocorre a + bx = x − b∗x ⇐⇒ a + b∗x =

x − bx ∈ A + B e bx ∈ Bx∗ , o que é absurdo pois Bx∗ ∩ Bx = ∅. Enfim,

|A + B| ≥ |A + Bx | + |{x} − Bx∗ | = |A + Bx | + |Bx∗ | = |A + Bx | + |B| − |Bx |

Assim, o problema acabou: de fato, se trocarmos A e B por A e Bx , temos 1 ≤ |Bx | <

|B|, |A + Bx | < |A + B| < p e

|A + Bx | ≤ |A + B| − |B| + |Bx | ≤ |A| + |B| − 2 − |B| + |Bx | = |A| + |Bx | − 2,

ou seja, conseguimos um exemplo com |Bx | < |B| menor ainda, o que é absurdo.
A igualdade ocorre em uma das seguintes situações:

• |A| + |B| > p;

• |A| = 1 ou |B| = 1;

• B = {c} − A para algum c ∈ Z/(p);

• A e B são progressões aritméticas com mesma razão.

A demonstração está em [2].

3
POT 2012 - Combinatória - Nı́vel 3 - Aula 19 - Prof. Carlos Shine

Problemas
1. (O problema de Waring) Seja k um inteiro positivo e
Ak = {nk , n ∈ Z+ }
as potências k-ésimas. Definindo
tAk = Ak + Ak + · · · + Ak ,
| {z }
t vezes

qual é o menor valor de t, se existir, para o qual tAk = Z+ ?

Foi provado na década de 1950 que
Teorema 5. Seja g(k) o menor t tal que tAk = Z+ . Então
j
k n
o j
k
k k k
• g(k) = 2k + 32 − 2 se 2k 23 + 23 ≤ 2k ;
j
k j
k n
o j
k j
kj
k
k k k k 4 k 3 k
• g(k) = 2k + 32 + 43 − 2 se 2k 23 + 32 > 2k e 3 2 +
j
k j
k
4 k k
3 + 32 = 2k ;
j
k j
k n
o j
k j
kj
k
k k k k 4 k 3 k
• g(k) = 2k + 32 + 43 − 3 se 2k 23 + 32 > 2k e 3 2 +
j
k j
k
4 k k
3 + 32 > 2k .
j
k n
o j
k
3 k 3 k 3 k
Prove que g(k) ≥ 2k + 2 −2. Na verdade, conjectura-se que 2k 2 + 2 ≤
2k para todo k, mas ainda não se provou isso!
2. Prove que, sendo A e B subconjuntos finitos de inteiros, |A + B| ≥ |A| + |B| − 1.
3. (Ibero) Encontrar o menor número natural n com a seguinte propriedade: entre
quaisquer n números distintos do conjunto {1, 2, . . . , 999} pode-se escolher quatro
números diferentes a, b, c, d tais que a + 2b + 3c = d.
4. (Banco RMM) Sejam U, V, W subconjuntos finitos e não vazios de Z. Prove que
|U + V | · |U + W |
|V − W | ≤
|U |

5. Sejam n+1 inteiros 0 = a0 < a1 < . . . < an = 2n−1. Encontre a menor cardinalidade
que o conjunto {ai + aj : 0 ≤ i ≤ j ≤ n} pode ter.
6. (OBM) Dizemos que um conjunto A ⊂ N satisfaz a propriedade P (n) se A tem n
elementos e A + A = {x + y tal que x ∈ A e y ∈ A} tem n(n+1) 2 elementos. Dado
A ⊂ N finito definimos diâmetro de A como sendo a diferença entre o maior e o menor
elemento de A. Seja f (n) o menor diâmetro que o conjunto A satisfazendo P (n) pode
2
ter. Mostre que n4 ≤ f (n) < n3 para todo n ≥ 2.
(Se o seu tempo de prova não estiver esgotado, tente melhorar esta estimativa. Por
exemplo, tente mostrar que f (p) < 2p2 , para todo número primo p.)

4
POT 2012 - Combinatória - Nı́vel 3 - Aula 19 - Prof. Carlos Shine

7. (Romênia TST) Sejam X e Y subconjuntos finitos de [0, 1) tais que 0 ∈ X ∩ Y e

x + y 6= 1 para todos x ∈ X e y ∈ Y . Prove que o conjunto {x + y − ⌊x + y⌋ : x ∈
X e y ∈ Y } tem pelo menos |X| + |Y | − 1 elementos.
8. Seja p > 3 primo. O conjunto {1, 2, 3, . . . , p − 1} é particionado em três subconjuntos
não vazios A, B, C. Prove que existem três números x, y, z, um de cada subconjunto,
tais que p divide x + y − z.
9. (IMO) Seja A um subconjunto do conjunto S = {1, 2, . . . , 1000000} com exatamente
101 elementos. Demonstre que existem números t1 , t2 , . . . , t100 em S tais que os
conjuntos
Aj = {x + tj | x ∈ A}, para j = 1, 2, . . . , 100
são disjuntos dois a dois.
10. (IMO) Sejam a1 , a2 , . . . , an inteiros positivos distintos e M um conjunto de n − 1
inteiros positivos que não contém o número s = a1 + a2 + · · · + an . Um gafanhoto
pretende saltar ao longo da reta real. Ele começa no ponto 0 e dá n saltos para a
direita de comprimentos a1 , a2 , . . . , an , em alguma ordem.
Prove que essa ordem pode ser escolhida de modo que o gafanhoto nunca caia num
ponto de M .
11. (Banco da IMO) Seja A um conjunto de n resı́duos módulo n2 . Prove que existe um
conjunto B de n resı́duos módulo n2 tal que pelo menos metade dos resı́duos módulo
n2 pode ser escrito como a + b com a ∈ A e b ∈ B.
12. (Miklos-Schweitzer) Prove que existem constantes c e n0 com a seguinte propriedade:
se A é um conjunto finito de inteiros, |A| = n > n0 , então
|A − A| − |A + A| ≤ n2 − cn8/5 .

Bibliografia
1. T. Tao, Lecture Notes 1 for 254A. Disponı́vel em
http://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/Tao.pdf
2. Ø. J. Rødseth, Sumsets mod p. Disponı́vel em
http://www.folk.uib.no/nmaoy/papers/sumsetsR.pdf
3. N. Alon, J. H. Spencer, P. Erdős, The Probabilistic Method, John Wiley & Sons 1992.
Respostas, Dicas e Soluções
j
k
3 k
1. É só considerar 2k 2 − 1, que é menor do que 3k : como as únicas potências
k-ésimas menores
j
k que 3k são 2k e 1, devemosj usar ka maiorjquantidade  possı́vel de
k 3 k k


3 k

k
3 k
2 s, que é 2 − 1, e cobrir o resto, que é 2 −1− − 1 2k = 2k − 1,
j 2
k 2
j
k
k k
com 1s. Com isso, precisamos de pelo menos 23 − 1 + 2k − 1 = 23 + 2k − 2
potências.

5
POT 2012 - Combinatória - Nı́vel 3 - Aula 19 - Prof. Carlos Shine

2. Translade A e B de modo que max A = min B = 0. Note que A só tem números não
positivos e B só tem números não negativos, e que A ∪ B ⊂ A + B, pois 0 ∈ A e
0 ∈ B. Logo |A + B| ≥ |A ∪ B| = |A| + |B| − 1.

3. A resposta é n = 835. Para ver isso, considere o exemplo com os 834 números de 166
a 999. O menor valor de a + 2b + 3c é 168 + 2 · 167 + 3 · 166 = 1000.
Agora, considere 835 números entre os mais de 834 escolhidos, e sejam eles m = a1 <
a2 < . . . < a835 = M . Temos M ≥ m + 834, de modo que −3m ≥ 3 · 834 − 3M , e
M − 3m ≥ 3 · 834 − 2M ≥ 3 · 834 − 3 · 999 = 504. A ideia é comparar M − 3m com
ai + 2aj , 1 < i, j < 835. Fixe k = M − 3m e considere a equação x + 2y = k. Há pelo
menos k/3 − 1 ≥ 167 soluções disjuntas para essa equação: (k − 2i, i), 1 ≤ i ≤ 167
(note que sempre temos x > y, então não há perigo de ocorrer repetições). Então
para que não ocorra a + 2b = M − 3m devemos ter b = m ou um dos números a, b não
está entre os escolhidos. Isso elimina pelo menos 167 − 1 = 166 números, sobrando
no máximo 999 − 166 = 833, e aı́ obtemos uma contradição, de modo que existem a, b
com a + 2b = M − 3m.

4. Reescreva a desigualdade como |V − W | · |U | ≤ |U + V | · |U + W | e considere o

produto cartesiano (U + V ) × (U + W ). Note que ele contém os pares (u + v, u + w),
u ∈ U , v ∈ V e w ∈ W . Note que (u1 + v1 , u1 + w1 ) = (u2 + v2 , u2 + w2 ) ⇐⇒
v1 − v2 = w1 − w2 = u2 − u1 =⇒ v1 − w1 = v2 − w2 . Assim, dado u ∈ U e
x ∈ V − W , conseguimos, escolhendo um par (v, w) adequado para cada x, pelo
menos um elemento (u + w + x, u + w) de (U + V ) × (U + W ), e não temos repetições
(só escolhemos um representante para cada u − v). Logo

|U + V | · |U + W | = |(U + V ) × (U + W )|
≥ |{(u + v, u + w) : u ∈ U, v ∈ V, w ∈ W }|
≥ |U | · |V − W |.

5. A resposta é 3n, obtida para ai = i para 0 ≤ i < n: as somas são 0, 1, . . . , 3n − 1.

Vamos provar que pelo menos 3n somas aparecem em qualquer situação. Primeiro,
seja A = {ai : 0 ≤ i ≤ n}; note que (A+{2n−1})∪(A+{0}) já tem 2(n+1)−1 = 2n+1
somas diferentes, pois todo elemento de A+{2n−1} é maior ou igual que os elementos
de A, com igualdade só para o 2n − 1. Faltam n − 1 elementos!
Agora, seja C o conjunto dos 2n − (n + 1) = n − 1 números entre 0 e 2n − 1 que não
foram escolhidos para compor A. Note que as somas podem ir de 0 a 2(2n − 1), então
consideremos também C + {2n − 1}. Provaremos que, para c ∈ C, pelo menos um
dos dois números c ou c + 2n − 1 está em A + A. Como |C| = n − 1, isso termina o
problema.
Para isso, seja t o inteiro tal que at−1 < c < at e pensemos em c + 2n − 1. Não há
chance para que ai +aj = c+2n−1 se um dos ı́ndices é menor do que t, então considere
os conjuntos X = {at , at+1 , . . . , an = 2n − 1, a1 + 2n − 1, a2 + 2n − 1, . . . , at−1 + 2n − 1}
e Y = {c + 2n − 1 − ai : 1 ≤ i ≤ n − 1}. Temos |X| = n e |Y | = n − 1 e todos

6
POT 2012 - Combinatória - Nı́vel 3 - Aula 19 - Prof. Carlos Shine

os elementos de X ∪ Y maiores do que c e menores do que c + 2n − 1, num total

de no máximo 2n − 2 números. Logo X ∩ Y 6= ∅. Assim, existem i e j tais que
ai = c + 2n − 1 − aj ⇐⇒ ai + aj = c + 2n − 1, ou seja, c + 2n − 1 ∈ A + A ou
ai + 2n − 1 = c + 2n − 1 − aj ⇐⇒ ai + aj = c, ou seja, c ∈ A + A, e o problema
acabou.

6. Dado um conjunto finito A ⊂ N, denotaremos por d(A) o diâmetro de A. Temos duas

desigualdades a provar:
2
(i) f (n) ≥ n4 , para todo n ≥ 2.
Considere um conjunto A = {a1 , a2 , . . . , an }, a1 < a2 < · · · < an , n ≥ 2 que
satisfaz P (n). Assim, A+A = {a1 +a1 , a1 +a2 , . . . , an +an } tem n(n+1)
2 elementos.
Como a1 + a1 < a1 + a2 < · · · < an + an , temos que (an + an ) − (a1 + a1 ) + 1 ≥
n(n+1) 2 n2 n2
2 =⇒ an − a1 ≥ n4 + n−2 4 ≥ 4 =⇒ d(A) ≥ 4 . Isto demonstra (i).
(ii) f (n) < n3 , para todo n ≥ 2.
Vamos fazer isso por indução. Como {0, 1} satisfaz P (2), temos que f (2) ≤
1 < 23 . Agora, vamos supor que f (n) < n3 para algum n ≥ 2. Seja An =
{a1 , a2 , . . . , an } ⊂ N tal que An satisfaz P (n) e d(An ) = f (n) < n3 . Sem perda
de generalidade, podemos supor que 0 = a1 < a2 < · · · < an = d(An ), bastando
para isto subtrair de cada elemento de An o menor de seus elementos.
Agora, queremos achar an+1 ∈ N−An tal que An+1 = {a1 , a2 , . . . , an+1 } satisfaça
P (n + 1) e d(An+1 ) < (n + 1)3 . Como An + An tem n(n+1) 2 elementos e An+1 +
An+1 = (An + An ) ∪ {ai + an+1 | 1 ≤ i ≤ n + 1}, temos que an+1 ∈ N \ An
e An+1 satisfaz P (n + 1) se, e somente se, an+1 + ak 6= ai + aj ∈ An + An ou
a +a
an+1 + an1 6= ai +naj ⇐⇒ an+1 6= io2 j , ou seja, an+1 ∈ / P = {ai + aj − ak |
ai +aj
1 ≤ i, j, k ≤ n} ∪ 2 | 1 ≤ i, j ≤ n . Como |P | ≤ n3 + n(n+1)
2 (no máximo
3 n

ai +aj
n escolhas para ai + aj − ak e no máximo 2 + n escolhas para 2 ), temos
que an+1 ≤ n3 + n(n+1)
2 , pois basta escolher an+1 como o menor natural que não
está em P . Assim, f (n + 1) ≤ d(An+1 ) < (n + 1)3 . Por indução finita em n,
temos que (ii) é verdade, o que completa nossa demonstração.
Vamos ainda, verificar que, para P primo, f (p) < 2p2 . Para isto, construı́mos o
conjunto A = {k + 2pg(k), 0 ≤ k ≤ p − 1}, onde g(k) = k 2 mod p é o resto da
divisão de k 2 por p. temos d(A) ≤ p − 1 + 2p(p − 1) = 2p2 − p − 1 < 2p2 e se
tivéssemos i + 2pg(i) + j + 2pg(j) = r + 2pg(r) + s + 2pg(s) ⇐⇒ i + j − (r + s) =
2p(g(i) + g(j) − (g(r) + g(s))), então como −2p < i + j − (r + s) < 2p é múltiplo
de 2p

i + j + 2p(g(i) + g(j)) = r + s + 2p(g(r) + g(s))

⇐⇒ i + j = r + s e g(i) + g(j) = g(r) + g(s).

Note que o 2p multiplicando g(k) não foi ao acaso. A ideia era exatamente se
aproveitar do fato de que −2p < i + j − (r + s) < 2p.

7
POT 2012 - Combinatória - Nı́vel 3 - Aula 19 - Prof. Carlos Shine

Assim, i − r = s − j e i2 + j 2 ≡ r2 + s2 (mod p), logo

(i − r)(i + r) ≡ (s − j)(s + j) (mod p)

⇐⇒ i − r ≡ s − j ≡ 0 (mod p) ou i + r ≡ s + j (mod p).

Portanto i = r e s = j ou i = s e r = j.
Novamente, k 2 mod p não foi escolhido ao acaso: usamos o fato de que i − r =
s − j e a fatoração da diferença de quadrados.

7. Imite a demonstração do teorema de Cauchy-Davenport. É praticamente igual! De-

fina X + Y módulo 1, e para provar que X + Y 6= X + 2Y , leve em consideração que
ny ∈ X + Y para todo n inteiro positivo e, portanto, ny nunca é inteiro; ou seja,
nY ⊂ X + Y é infinito, absurdo.

8. Suponha por absurdo que exista uma partição sem a propriedade do enunciado. Po-
demos supor, sem perda de generalidade, que A é um conjunto com menos elementos,
e também podemos supor que 1 ∈ A, pois basta multiplicar todos os números por
a−1 , para algum a ∈ A. Seja k o número tal que 1, 2, . . . , k ∈ A e k + 1 ∈ B. Seja
c ∈ C, i com 1 ≤ i ≤ k. Se c ± i ∈ B, (i, c ± i, c) ∈ A × B × C, então c ± i ∈/ B. Se
c + i ∈ C e c − (k + 1 − i) ∈ A, (c − k − 1 + i, k + 1, c + i) ∈ A × B × C também.
Seja c1 = min C. Então c1 − (k + 1 − i) ∈ A e, portanto, c1 + i ∈ A, ou seja, A
contém {1, 2, . . . , k} ∪ {c1 − 1, c1 − 2, . . . , c1 − k} ∪ {c1 + 1, c1 + 2, . . . , c1 + k}. Essa
ideia também vale se tomarmos o próximo elemento de C, e assim por diante. Logo
temos |A| > |C|, o que é uma contradição, e o problema acabou.

9. Vamos supor, sem perda de generalidade, 1 = t1 < t2 < . . . < t100 . Quando dois
conjuntos Ai e Aj têm interseção? Quando xi + ti = xj + tj ⇐⇒ tj = xi − xj + ti .
Ou seja, devemos nos preocupar com A − A.
Agora, vamos construir um exemplo indutivamente. Já escolhemos t1 = 1. Suponha
que
já escolhemos t1 , . . . , tk . Para escolher tk+1 , cada valor de ti , 1 ≤ i ≤ k, proı́be
101
2 = 101·100
2 números (as escolhas de xi > xj ) além, é claro, dos k valores anteriores.
Então há k · 101 · 50 + k ≤ 99 · (50 · 101 + 1) < 1000000 números proibidos, e sempre
sobra pelo menos um para escolher.

10. Indução sobre n. Não há o que se provar para n = 1 e o problema é imediato se
n = 2. Suponha então que n > 1, e seja an o maior dos números ai e m = max M .
Caso s − an ∈ M e m > s − an (ou seja, s − an não é o máximo), então para algum
i, 1 ≤ i ≤ n − 1, s − ai e s − ai − an estão ambos fora de M : são n − 1 pares
(s − ai , s − ai − an ), nenhum desses números é igual a s − an , que é um elemento de
M , e sobram n − 2 outros elementos em M . Aı́, aplicamos a hipótese de indução para
os n − 2 números tirando ai e an e os n − 3 elementos de M tirando m e s − an , que
são ambos maiores do que s − ai − an , e terminamos pulando em s − ai e s.
No outro caso, aplicamos a hipótese de indução para os ai ’s tirando an e M \ {m}.
Note que agora ou s − an ∈/ M ou s − an = m, então podemos fazer isso. Fazemos

8
POT 2012 - Combinatória - Nı́vel 3 - Aula 19 - Prof. Carlos Shine

então os n − 1 pulos pela hipótese de indução e colocamos m de volta. Se m não

está em nenhum dos pulos, basta dar o último pulo de tamanho an e terminamos; se
m está no k-ésimo pulo (note que m é o último lugar em que isso pode acontecer),
trocamos o k-ésimo pulo por an , ultrapassamos m e depois usamos os outros pulos.
Com isso, o passo de indução está completo.
11. Escolha um conjunto B com n elementos aleatórios de Z/(n2 ), com reposição. Calcu-
lemos a probabilidade de um resto fixado r não pertencer a A + B: basta que nenhum

n
dos números r − a, a ∈ A, pertença a B. Isso ocorre com probabilidade 1 − n1 (a
chance de não sortearmos um elemento da forma r − a é 1 − n1 ).

n
Como nn > 2(n − 1)n ⇐⇒ 1 − n1 < 21 para n ≥ 2, temos que a probabilidade de
r não pertencer a A + B é menor do que 21 , e o valor esperado de números que não
estão em A + B é menor do que n2 /2. Logo o valor esperado de números que estão
em A + B é maior do que n2 /2 e existe um B desejado. De
fato, para n grande existe
um conjunto B tal que A + B tem pelo menos n2 1 − 1e elementos!
12. Considere o seguinte lema:
Lema 1. Suponha que uma diferença c de A − A possa ser escrita de k maneiras
na forma ai − aj , ai , aj ∈ A. Então existe um conjunto V ⊂ A com pelo menos k/3
elementos tal que cada diferença vi −vj de V −V também apareça em (A\V )−(A\V ).

Para provar esse lema, note que as k diferenças formam várias progressões aritméticas
disjuntas; escolha para V os termos de ordem par das PAs (ou seja, se a PA é
a, a + r, a + 2r escolhemos a + r), e temos pelo menos k/3 elementos. Para ver por que
dá certo, basta deslocar um termo de cada termo da diferença na PA correspondente.
Aı́ temos
|A − A| − |A + A| ≤ |A − A| ≤ |(A \ V ) − (A \ V )| + |(A \ V ) − V | + |V − (A \ V )|
≤ 2|V |(n − |V |) + (n − |V |)2 = n2 − |V |2 ≤ n2 − (k/3)2 ,

o que resolve o problema se k ≥ C · n4/5 , ou seja, alguma diferença aparece mais do

que C · n4/5 vezes.
Caso contrário, seja s = |A + A| e t = |A − A|. Suponha que cada soma si , 1 ≤ i ≤ s,
seja escrita na forma ai + aj de xi maneiras e que cada diferença ti , 1 ≤ i ≤ t, seja
escrita na forma ai − aj de yi maneiras. Então, como há n2 pares (ai , aj ),
s
X t
X
xi = yi = n 2
i=1 i=1

Além disso, como ai + aj = ap + aq ⇐⇒ ai − ap = aq − aj , existem x2u quádruplas

(ai , aj , ap , aq ) com ai + aj = ap + aq = su e yv2 quádruplas (ai , aj , ap , aq ) com ai − ap =
aq + aj , temos também
X s Xt
2
xi = yi2 = S
i=1 i=1

9
POT 2012 - Combinatória - Nı́vel 3 - Aula 19 - Prof. Carlos Shine

Como 1 ≤ yi ≤ C · n4/5 , S é maximizado quando todos os yi ’s são 1 ou C · n4/5 .

Achando a quantidade de 1’s e C · n4/5 ’s, temos

n2 − t 4/5 2 n2 − t
S≤ 4/5
· (Cn ) + t − 4/5
= (n2 − t)(Cn4/5 + 1) + t
Cn − 1 Cn − 1

n4 n4
Por Cauchy-Schwartz, S · s ≥ n4 ⇐⇒ s ≥ S ≥ (n2 −t)(Cn4/5 +1)+t
.
Então, sendo x = n2 − t,

n4
|A − A| − |A + A| ≤ n2 − x −
xCn4/5 + n2

Se x ≥ C ′ n8/5 , o resultado segue imediatamente. Caso contrário, xCn4/5 + n2 <

n4
C ′ n12/5 + n2 < C ′′ n12/5 para n suficientemente grande e xCn4/5 +n2
> C ′′′ n8/5 , e o
problema termina de qualquer jeito.

10