Mostre que em todo subconjunto de \{1,2, \ldots, 2 n\} \operatorname{com} n+1 elementos há um par de elementos primos entre si neste subconjunto. Dica:Não tente usar a dica do exercício anterior.

Passo 1

O enunciado pede para mostrar que qualquer subconjunto S\subset\{1,2,\dots,2n\} com \lvert S\rvert = n+1 sempre contém dois elementos coprimos. Vamos usar o princípio da casa dos pombos: se tivermos mais “pombos” (elementos de S) do que “casas” (grupos em que particionamos \{1,\dots,2n\}), alguma casa terá pelo menos dois pombos.

Passo 2

Particionamos \{1,2,\dots,2n\} em n pares
P_k = \{\,2k-1,\,2k\},\quad k=1,2,\dots,n.
Cada P_k é uma “casa” do princípio da casa dos pombos.

Passo 3

Como S tem n+1 elementos e há somente n pares P_1,\dots,P_n, pelo princípio da casa dos pombos S deve conter pelo menos dois elementos de um mesmo par P_k. Ou seja, existem k tais que
\{2k-1,\,2k\}\subset S.

Passo 4

Para qualquer k, temos
\gcd(2k-1,\,2k)=1,
já que números consecutivos são sempre coprimos. Logo, em S encontramos um par de elementos cujo máximo divisor comum é 1.

Resposta

Qualquer subconjunto de \{1,2,\dots,2n\} com n+1 elementos contém um par de elementos coprimos.

Exercícios relacionados