Ensino Médio

Mensagem não lidapor **leomaxwell** » 30 Set 2017, 14:19 · Mensagem não lida por **leomaxwell** » 30 Set 2017, 14:19

Sejam [tex3]a[/tex3] e [tex3]b[/tex3] números inteiros, com [tex3]a< b< 2a[/tex3] . Então, dado mais da metade dos inteiros no conjunto {1, 2, ..., a+b}, pelo menos dois deles diferem por [tex3]a[/tex3] ou por [tex3]b[/tex3]

A questão estava em inglês, tentei traduzir e pode ser que eu não tenha pego alguma informação relevante pro problema. Quem quiser ver ela original, é essa aqui:
Let a and b be postive integers, with a < b < 2a. Then, given more than half of the integers in the set {1, 2, ..., a + b}, some two of the given integers differ by a or by b.

Obrigado desde já!

Mensagem não lidapor **Tassandro** » 27 Mai 2020, 09:33 · Mensagem não lida por **Tassandro** » 27 Mai 2020, 09:33

Podemos considerar os números desde [tex3]1[/tex3] a [tex3]a+b[/tex3] como vértices em um gráfico e se tomarmos um subconjunto [tex3]S \subseteq \{1,\dots,a+b\}[/tex3] então podemos traçar uma aresta por cada par [tex3]i,j \in S[/tex3] (sempre e quando [tex3]i \neq j[/tex3] ). Podemos também etiquetar cada aresta com a diferença entre [tex3]i[/tex3] e [tex3]j[/tex3] . O problema então consiste em demonstrar que é impossível selecionar [tex3]S[/tex3] de tal forma que nenhuma das arestas esteja etiquetada com [tex3]a[/tex3] ou [tex3]b[/tex3] .
Vamos definir uma função [tex3]f[/tex3] em [tex3]\{1,\dots,a+b\}[/tex3] por
[tex3]\displaystyle f(m) = \begin{cases} m+a & \text{se } m \leq b, \\ m-b & \text{se } b < m. \end{cases} \tag*{}[/tex3]
Um fato importante é que, para qualquer [tex3]m[/tex3] , a diferença entre [tex3]m[/tex3] e [tex3]f(m)[/tex3] é sempre igual a [tex3]a[/tex3] ou [tex3]b[/tex3] . Igualmente importante é que esta funcão é uma bijeção em [tex3]\{1,\dots,a+b\}[/tex3] .
Assim, o que queremos é escolher [tex3]S[/tex3] para que nenhum par de números em [tex3]S[/tex3] tenha diferença [tex3]a[/tex3] ou [tex3]b[/tex3] , então nenhum número de [tex3]S[/tex3] pode ter imagem em [tex3]S[/tex3] . Ou seja, se [tex3]m \in S[/tex3] então [tex3]f(m) \notin S[/tex3] .
Daqui se segue que [tex3]S \cap f(S) = \varnothing[/tex3] . Mas isso implica que
[tex3]|S \cup f(S)| = |S| + |f(S)| = 2|S| > a+b, \tag*{}[/tex3]
pelo fato de que [tex3]S[/tex3] contém mais da metade dos elementos de [tex3]\{1,\dots,a+b\}[/tex3] . E isto é uma contradição, porque ao ser [tex3]S \cup f(S)[/tex3] um subconjunto de [tex3]\{1,\dots,a+b\}[/tex3] não pode ter mais de [tex3]a+b[/tex3] elementos. Portanto é impossível que [tex3]S[/tex3] exista.
[tex3]\blacksquare[/tex3]

Ensino Médio ⇒ Princípio da Casa dos Pombos Tópico resolvido

Princípio da Casa dos Pombos

Re: Princípio da Casa dos Pombos

Ensino Médio ⇒ Princípio da Casa dos Pombos Tópico resolvido

Princípio da Casa dos Pombos

Re: Princípio da Casa dos Pombos

Entrar | Registrar