.Problema para ajudar na escola: Números primos em um conjunto

Link do problema para dispositivos da Apple.

Problema
(A partir do 8º ano do E. F. – Nível de dificuldade: Médio)


Seja [tex]A=\{1, \, 2, \, 3, \, 4, \, 5, \, 6, \, 7, \, 8, \, 9, \, 10, \, 11, \, 12, \, 13, \, 14, \, 15 \} \, .[/tex]
Determinar o menor inteiro positivo [tex]m[/tex] tal que qualquer subconjunto de [tex]A[/tex] com [tex]m[/tex] elementos tenha, pelo menos, um número primo.

Solução


Observe que no conjunto [tex]A[/tex] temos números primos e números não primos:

  • primos:[tex] \, 2, \, 3, \, 5, \, 7, \, 11, \, 13 \, [/tex],
  • não primos:[tex] \, 1, \, 4, \, 6, \, 8, \, 9, \, 10, \, 12, \, 14, \, 15 \, [/tex].

(O número [tex]1[/tex] não é primo nem composto, por isso é que separamos os números do conjunto [tex]A[/tex] em primos e não primos e não em primos e compostos.)
Observe, agora, que o maior subconjunto de [tex]A[/tex] com números não primos é exatamente
[tex]\qquad \qquad B=\{1, \, 4, \, 6, \, 8, \, 9, \, 10, \, 12, \, 14, \, 15\} \, [/tex];
assim, podemos concluir que

  • " Se considerarmos conjuntos com mais de nove elementos, então necessariamente esses conjuntos terão, pelo menos um número primo ".

Não conseguiu se convencer da veracidade da afirmação?
Então, pensemos juntos.

  • Vamos tentar definir um subconjunto [tex]S[/tex] de [tex]A[/tex] com dez elementos, formado apenas de números não primos:
  • [tex]S=\{ \, \, \underline{\quad } \, , \, \underline{\quad } \, , \, \underline{\quad } \, , \, \underline{\quad } \, , \, \underline{\quad } \, , \, \underline{\quad } \, , \, \underline{\quad } \, , \, \underline{\quad } \, , \, \underline{\quad } \, , \, \underline{\quad } \, \, \}[/tex]

    Como poderíamos preencher os dez espaços?
    Bom, iniciemos o preenchimento com os números não primos de [tex]A[/tex]:

    [tex]S=\{ \, \, \underline{\textcolor{#6cda00}{1}} \, , \, \underline{\textcolor{#6cda00}{4} } \, , \, \underline{\textcolor{#6cda00}{6}} \, , \, \underline{\textcolor{#6cda00}{8} } \, , \, \underline{\textcolor{#6cda00}{9}} \, , \, \underline{\textcolor{#6cda00}{10}} \, , \, \underline{\textcolor{#6cda00}{12}} \, , \, \underline{\textcolor{#6cda00}{14}} \, , \, \underline{\textcolor{#6cda00}{15}} \, , \, \underline{ \, \, ? \, \, } \, \, \}[/tex]

    E agora, como preencheremos a última lacuna???
    Não tem jeito, não é? Só sobraram os números primos de [tex]A[/tex]

    [tex]S=\{ \, \underline{\textcolor{#6cda00}{1}} \, , \, \underline{\textcolor{#6cda00}{4} } \, , \, \underline{\textcolor{#6cda00}{6}} \, , \, \underline{\textcolor{#6cda00}{8} } \, , \, \underline{\textcolor{#6cda00}{9}} \, , \, \underline{\textcolor{#6cda00}{10}} \, , \, \underline{\textcolor{#6cda00}{12}} \, , \, \underline{\textcolor{#6cda00}{14}} \, , \, \underline{\textcolor{#6cda00}{15}} \, , \, \underline{ \, \, \textcolor{#800000}{primo} \, \, } \, \}[/tex]

Para amadurecer a resposta, vejamos as situações de todos subconjuntos com mais de nove elementos:

[tex]S_{10}=\{ \, \underline{\textcolor{#6cda00}{1}} \, , \, \underline{\textcolor{#6cda00}{4} } \, , \, \underline{\textcolor{#6cda00}{6}} \, , \, \underline{\textcolor{#6cda00}{8} } \, , \, \underline{\textcolor{#6cda00}{9}} \, , \, \underline{\textcolor{#6cda00}{10}} \, , \, \underline{\textcolor{#6cda00}{12}} \, , \, \underline{\textcolor{#6cda00}{14}} \, , \, \underline{\textcolor{#6cda00}{15}} \, , \, \underline{\textcolor{#800000}{p_1}} \, \}[/tex]

[tex]S_{11}=\{ \, \underline{\textcolor{#6cda00}{1}} \, , \, \underline{\textcolor{#6cda00}{4} } \, , \, \underline{\textcolor{#6cda00}{6}} \, , \, \underline{\textcolor{#6cda00}{8} } \, , \, \underline{\textcolor{#6cda00}{12}} \, , \, \underline{\textcolor{#6cda00}{10}} \, , \, \underline{\textcolor{#6cda00}{12}} \, , \, \underline{\textcolor{#6cda00}{14}} \, , \, \underline{\textcolor{#6cda00}{15}} \, , \, \underline{\textcolor{#800000}{p_1}} \, , \, \underline{\textcolor{#800000}{p_2}} \, \}[/tex]

[tex]S_{12}=\{ \, \underline{\textcolor{#6cda00}{1}} \, , \, \underline{\textcolor{#6cda00}{4} } \, , \, \underline{\textcolor{#6cda00}{6}} \, , \, \underline{\textcolor{#6cda00}{8} } \, , \, \underline{\textcolor{#6cda00}{9}} \, , \, \underline{\textcolor{#6cda00}{10}} \, , \, \underline{\textcolor{#6cda00}{12}} \, , \, \underline{\textcolor{#6cda00}{14}} \, , \, \underline{\textcolor{#6cda00}{15}} \, , \, \underline{\textcolor{#800000}{p_1}} \, , \, \underline{\textcolor{#800000}{p_2}} \, , \, \underline{\textcolor{#800000}{p_3}} \, \}[/tex]

[tex]S_{13}=\{ \, \underline{\textcolor{#6cda00}{1}} \, , \, \underline{\textcolor{#6cda00}{4} } \, , \, \underline{\textcolor{#6cda00}{6}} \, , \, \underline{\textcolor{#6cda00}{8} } \, , \, \underline{\textcolor{#6cda00}{9}} \, , \, \underline{\textcolor{#6cda00}{10}} \, , \, \underline{\textcolor{#6cda00}{12}} \, , \, \underline{\textcolor{#6cda00}{14}} \, , \, \underline{\textcolor{#6cda00}{15}} \, , \, \underline{\textcolor{#800000}{p_1}} \, , \, \underline{\textcolor{#800000}{p_2}} \, , \, \underline{\textcolor{#800000}{p_3}} \, , \, \underline{\textcolor{#800000}{p_4}} \, \}[/tex]

[tex]S_{14}=\{ \, \underline{\textcolor{#6cda00}{1}} \, , \, \underline{\textcolor{#6cda00}{4} } \, , \, \underline{\textcolor{#6cda00}{6}} \, , \, \underline{\textcolor{#6cda00}{8} } \, , \, \underline{\textcolor{#6cda00}{9}} \, , \, \underline{\textcolor{#6cda00}{10}} \, , \, \underline{\textcolor{#6cda00}{12}} \, , \, \underline{\textcolor{#6cda00}{14}} \, , \, \underline{\textcolor{#6cda00}{15}} \, , \, \underline{\textcolor{#800000}{p_1}} \, , \, \underline{\textcolor{#800000}{p_2}} \, , \, \underline{\textcolor{#800000}{p_3}} \, , \, \underline{\textcolor{#800000}{p_4}} \, , \, \underline{\textcolor{#800000}{p_5}} \, \}[/tex]

[tex]S_{15}=\{ \, \underline{\textcolor{#6cda00}{1}} \, , \, \underline{\textcolor{#6cda00}{4} } \, , \, \underline{\textcolor{#6cda00}{6}} \, , \, \underline{\textcolor{#6cda00}{8} } \, , \, \underline{\textcolor{#6cda00}{9}} \, , \, \underline{\textcolor{#6cda00}{10}} \, , \, \underline{\textcolor{#6cda00}{12}} \, , \, \underline{\textcolor{#6cda00}{14}} \, , \, \underline{\textcolor{#6cda00}{15}} \, , \, \underline{\textcolor{#800000}{p_1}} \, , \, \underline{\textcolor{#800000}{p_2}} \, , \, \underline{\textcolor{#800000}{p_3}} \, , \, \underline{\textcolor{#800000}{p_4}} \, , \, \underline{\textcolor{#800000}{p_5}} \, , \, \underline{\textcolor{#800000}{p_6}} \, \}[/tex]

onde [tex]\textcolor{#800000}{p_1}, \textcolor{#800000}{p_2}, \textcolor{#800000}{p_3}, \textcolor{#800000}{p_4}, \textcolor{#800000}{p_5}, \textcolor{#800000}{p_6} \in \{ \, 2, \, 3, \, 5, \, 7, \, 11, \, 13 \, \} \, .[/tex]

Então, o menor inteiro positivo [tex]m[/tex] tal que qualquer subconjunto de [tex]A[/tex] com [tex]m[/tex] elementos tenha, pelo menos, um número primo é [tex] \, \fcolorbox{black}{#eee0e5}{$m=10$} \, .[/tex]


Solução elaborada pelos Moderadores do Blog.

Se for conveniente, você pode obter um arquivo PDF desta página, com o problema e a solução, clicando no botão abaixo.
Você pode abrir o arquivo diretamente no seu navegador (Chrome, Edge, Firefox, Safari, entre outros), mas também pode utilizar o software gratuito Adobe Acrobat Reader.
Caso o dispositivo que você está utilizando não tenha o Acrobat Reader instalado, é só clicar AQUI para fazer o download adequado ao seu dispositivo.

Link permanente para este artigo: http://clubes.obmep.org.br/blog/problema-para-ajudar-na-escola-numeros-primos-em-um-conjunto/