Mostre que se um subconjunto com n+1 elementos é escolhido do conjunto \{1, 2,3, \ldots, 2 n\} então este subconjunto necessariamente contém um par de números primos entre si.
Solução:
Sabemos que dois inteiros consecutivos são primos entre si.

Passo 1

O enunciado considera o conjunto \{1,2,3,\dots,2n\} e afirma que, ao escolhermos qualquer subconjunto com n+1 elementos desse conjunto, sempre haverá dois números que são primos entre si. Para resolver isso, vamos usar o Princípio da Casa dos Pombos e a propriedade de que dois inteiros consecutivos são coprimos.

Passo 2

Particionamos os 2n inteiros em n pares de números consecutivos, cada um coprimo internamente:
(1,2),\;(3,4),\;\dots,\;(2n-1,2n).
Em cada par, os dois números são coprimos porque inteiros consecutivos não têm divisor comum além de 1.

Passo 3

Aplicamos o Princípio da Casa dos Pombos: temos n “caixas” (os pares) e escolhemos n+1 “pombos” (os elementos do subconjunto). Logo, ao distribuir n+1 elementos em n pares, pelo menos em um dos pares ambos os elementos escolhidos devem estar presentes.

Passo 4

Nesse par que contém os dois elementos, eles são consecutivos por construção e, portanto, coprimos (primos entre si). Assim mostramos que qualquer subconjunto de n+1 elementos contém um par de números primos entre si.

Resposta

Qualquer subconjunto com n+1 elementos de \{1,2,\dots,2n\} tem dois números consecutivos, logo primos entre si.