Princípio da Casa dos Pombos
{Princípio da casa dos pombos -PCP}
{Notações }
Primeiro, vamos introduzir uma notação, denotaremos neste texto $I_n=\{1, \cdots, n\} .$
{Princípio da casa dos pombos -PCP}
[Proposição][Princípio das gavetas de Dirichlet- Ou princípio da casas dos pombos.]
Se temos $m$ conjuntos $(A_k)_1^m$ e $n$ elementos $n>m$, com $\sum^{m}_{k=1}|A_k|=n$ então existe $A_t$ dentre os $(A_k)_1^m$, tal que $|A_t|>1.$
Esse resultado diz que se temos $n$ elementos e $m$ conjuntos tais que $n>m$ então deve haver um conjunto com pelo menos $2$ elementos.
[Demonstração]
Supondo que $|A_k| \leq 1\; \forall \;k$, então aplicando a soma $\sum^{m}_{k=1}$ em ambos lados dessa desigualdade temos
$$n=\sum^{m}_{k=1}|A_k|\leq m \Rightarrow n \leq m $$
o que contraria a hipótese de $n>m$
,portanto deve valer $|A_t|> 1 $ para algum $t \in I_n$.
C.Q.D.
[Exemplo]
Um professor apostou com seus alunos que em sua turma haveria dois alunos que fazem aniversário no mesmo dia do mês. O professor sabia que ganharia a aposta. Quantos alunos no mínimo tinha em sua turma?
Um mês tem no máximo $31$ dias, se temos no mínimo $32$ alunos pelo $PCP$ pelo menos dois fazem aniversário no mesmo mês.
[Proposição]
Seja um grupo de $n$ pessoas $n \geq 2$ existem pelo menos duas pessoas com o mesmo número de conhecidos.
[Demonstração]
Vamos considerar que a relação de conhecer seja simétrica, isto é, se $A$ conhece $B$ então $B$ conhece $A$ e que n\ta o seja reflexiva $A $ n\ta o conhece $A$ (estranho?). Cada pessoa pode conhecer no máximo $n-1$ pessoas (pois n\ta o consideramos conhecer a si mesmo) e no mínimo $0$, vamos separar então essas pessoas em $n$ conjuntos definidos pela quantidade de pessoas que cada uma conheça. Sendo $A_{k}$ o conjunto formado por pessoas que conhecem $k$ pessoas. Temos que se $A_{0}$ possui uma pessoa, pelo menos, então $A_{n-1}$ deve ser vazio não haverá uma pessoa que conheça todas as outras. Se $A_{n-1}$ possui pelo menos uma pessoa então $A_{0}$ \'e vazio, em qualquer um desses casos vamos ter $n$ pessoas para $n-1$ conjuntos, logo pelo princípio da casa dos pombos segue a proposição. (Caso $A_{n-1}$ e $A_{0}$ sejam vazios temos $n$ pessoas para $n-2$ conjuntos então a proposição segue também.)
C.Q.D.
[Proposição]
Todo subconjunto de $I_{2n}$ contendo $n+1$ elementos possui n\'umeros consecutivos (e logo primos entre si).
[Demonstração]
Dividimos os elementos de $I_{2n}$ que t\^em $2n$ elementos em $n$ conjuntos com $2$ elementos da forma $\{k,k+1\}$ com $k$ em $[1,2n-1]$, temos que escolher ent\ta o $n+1$ elementos nesses conjuntos de $n$ elementos, assim pelo princ\'ipio da casa dos pombos pelo menos um deles vai ter $2$ elementos , logo consecutivos e primos entre si.
C.Q.D.
[Proposição]
Sejam $p$ bolsos e $n$ moedas, então podemos dividir as $n$ moedas entre os $p$ bolsos com a condição de cada bolso ter quantidade distinta de outro bolso e ter no mínimo $s$ moedas $\Leftrightarrow$ o número de moedas for maior ou igual ao valor $ps+\frac{p(p-1)}{2}.$
[Demonstração]
Sejam $p $ bolsos, cada um dos bolsos simbolizaremos por $a_{k}$ com $k \in I_p$, como cada bolso deve ter no mínimo $s$ moedas colocamos $s$ moedas em cada bolso, considere então $a_{1}$, ele é um bolso que possui $s$ moedas, mas como os outros bolsos devem ter quantidade diferente de $a_{1}$ então adicionamos uma moeda a cada outro bolso, assim $a_{k}$, $k \neq 1$ terá $s+1$ moedas, continuamos o processo com $a_{2}$ que possui $s+1$ moedas e adicionamos aos outros bolsos que não $a_{1}$ e $a_{2}$ $+1$ moeda, no fim desse processo teremos que $a_{k}$ terá $s+k-1$ moedas, tomamos a soma dessas moedas então
$$\sum^{p}_{k=1}s+k-1 =sp +\sum^{p}_{k=1}(k-1)=ps+\sum^{p-1}_{k=0}(k)=ps+\frac{k(k-1)}{2}\bigg|^{p}_{0}=ps+\frac{p(p-1)}{2}$$
então deve-se ter no mínimo essa quantidade de moedas $ps+\frac{p(p-1)}{2}$, qualquer valor superior a essa quantidade pode ter a diferença adicionada ao $p$-ésimo bolso, que as condições do problema ainda continuam verificadas.
C.Q.D.
[Exemplo]
Um saco contém objetos de duas cores, branca e preta. Qual o menor número de objetos que podemos tirar de modo a garantir que dois objetos retirados possuam a mesma cor?
A quantidade é de três objetos. Ao retirar dois objetos, podemos ter um de cada cor, ao retirarmos três objetos pelo menos dois devem possuir a mesma cor. Podemos pensar nesse caso como sendo duas casas, uma casa "branca " e a outra casa "preta" ao colocarmos três objetos nas duas casas, alguma casa deve ter dois objetos pelo princípio da casa dos pombos.
[Exemplo]
Mostre que dados $m+1$ números é possível escolher dois deles tais que sua diferença seja divisível por por $m$.
Resolvemos esse problema usando congruências , deseja-se provar que entre os $m+1$ números existem dois $a_1$ e $a_2$ tais que
$$a_1 \equiv a_2 \mod \;m $$
pois isso vale $\Leftrightarrow$ $m| (a_1-a_2)$ ou que $a_1 $ e $a_2$ possuem o mesmo resto na divisão por $m$ .
Os possíveis restos(casas) são $m$, naturais variando de $0$ até $m-1$, cada um dos $m+1$ inteiros deve estar em uma dessas "casas" como temos $m+1$ elementos para $m$ casas então o princípio da casa dos pombo garante que dois deles devem estar na mesma casa e por isso possuem mesmo resto na divisão por $m$, que equivale a dizer que sua diferença é divisível por $m$ .
[Exemplo][OBM 2012-Nível 3- Primeira fase -Questão 3]
Em uma pesquisa de rua, cada entrevistado respondeu a quatro perguntas, podendo sua resposta
ser sim ou não, para cada uma das perguntas. Qual o número mínimo de entrevistados para
garantirmos que duas pessoas responderam igualmente a todas as perguntas?
Temos duas respostas para cada pergunta, então no total temos $2^4 =16$ perguntas pelo princípio da casa dos pombos precisamos ter pelo menos $17$ entrevistados .
[Proposição][ Princípio geral da casa dos pombos.]
Se temos $m$ conjuntos $(A_k)_1^m$ e $n$ elementos, com $\sum^{m}_{k=1}|A_k|=n$ então existe $A_t$ em $(A_k)_1^m$ tal que $|A_t|\geq \lceil\frac{n}{m} \rceil .$
Esse resultado diz que se temos $n$ elementos e $m$ conjuntos então deve haver um conjunto com pelo menos $\lceil\frac{n}{m} \rceil$ elementos.
[Demonstração]
Suponha por absurdo que todos conjuntos tenham $|A_k|\leq \lceil\frac{n}{m} \rceil-1 $ isso vale $\Leftrightarrow |A_k|<\frac{n}{m} $ então somando todos temos
$$\underbrace{\sum_{k=1}^{m}|A_k| }_{n} < \sum_{k=1}^{m} \frac{n}{m}=m\frac{n}{m} =n \Leftrightarrow $$
$$n<n $$
o que é absurdo, então deve realmente existir um conjunto $A_t$ com $|A_t| \geq \lceil\frac{n}{m} \rceil . $
C.Q.D.
[Exemplo]
Temos $25$ caixas de maçãs, sendo maçãs de $3$ tipos, cada caixa possui apenas um tipo de maçã. Mostre que pelo menos $9$ caixas possuem o mesmo tipo de maçã .
Pensamos nas casas, como sendo os tipos de maçãs, que são $3$ e nas caixas como sendo os pombos, usando o principio geral temos pelo menos
$$ \lceil\frac{25}{3} \rceil=9\; caixas .$$
[Exemplo]
Um país possui $M$ times de futebol, cada um deles com $11$ jogadores. Existem $10 $ aviões, cada um sendo ocupado por $M$ jogadores, um jogador prefere ir de bicicleta mostre que é garantido que pelo menos um time inteiro vai conseguir ir completo na viagem .
Temos $10 .M+1$ jogadores com locomoção garantida, num total de $11 M =10M+M$ então $M-1$ jogadores ficam ainda sem transporte, para um número $M$ de times, então algum time deve possuir todos seus elementos com ida garantida.
[Exemplo]
Dados $8$ números naturais positivos diferentes, todos menores que $16$, então pelo menos três pares deles possuem a mesma diferença positiva.
Sejam $x_1, \cdots , x_8$, as diferenças variam de $15-1=14$(que pode ser escrito de apenas uma maneira) até $1$ no caso de números consecutivos. O número de diferenças é $k-1$ com $x_k$
$$x_k-x_{k-1},\;\cdots\; ,x_k-x_1. $$
Somando de $k=2$ até $8$, temos
$$\sum_{k=2}^8 (k-1)= \sum_{k=1}^7 (k) = \frac{7.8}{2} = 28 . $$
Sendo que para diferença $14$ temos apenas uma possibilidade, que é $15-1$, então restam $27$ para $13$ diferenças. Então temos $3$ como resultado.
[Exemplo]
Em um conjunto de $7$ pessoas, a soma de suas idades é de $332$ anos, prove que podemos escolher três pessoas tais que a soma de suas idades não seja menor do que $142$ anos .
Enumeramos as $7$ pessoas da maior idade para menor idade . Suponha que a idade das três pessoas mais velhas $x_1,x_2,x_3$ sejam menor que $142$, daí a soma da idade de mais novas também
$$\underbrace{x_1+x_2+x_3}_{< 142}+\underbrace{x_4+x_5+x_6}_{<142}+x_7 =332 < x_7+284 \Rightarrow x_7 > 332 -284 =48 ,$$
disso segue também que cada $x_k> 48$ pois $x_7$ é o menor, então a soma total é maior que $7.48=336$ que é absurdo .
Então deve valer que $x_1+x_2+x_3 \geq 142$ , para a soma dos maiores.
{Princípio da casa dos pombos e geometria}
[Exemplo]
Qual o maior número de quadrados em um tabuleiro $8 \times 8$ que pode ser colorido de azul, de modo que em qualquer arranjo de três quadrados (um triminó), pelo menos um quadrado não está colorido de azul?.
A resposta é $32$. Se tivéssemos $33$ ou mais quadrados pintados de azul, tomando a divisão do tabuleiros em blocos quadrados $2 \times 2$ de quadrados (temos $16$ deles), teríamos $ \lceil \frac{33}{16}\rceil=3 $ algum dos blocos teria $3$ quadrados pintados, logo um triminó pintado. Com $32$ ainda podemos ter todos triminos com um bloco não colorido, basta pintar dois quaisquer em um dos $16$ blocos, isso totaliza $32$ pintados.
[Exemplo]
Qual o menor número de quadrados de um tabuleiro $8 \times 8$ que pode ser colorido de azul de modo que em qualquer triminó, pelo menos um quadrado esteja colorido de azul?
Com $32$ quadrados coloridos de azul, temos sempre um quadrado de um triminó de azul (fazer imagem). Com $31$ quadrados azuis temos um triminó não colorido de azul, pois separando o tabuleiro em $16$ blocos $2 \times 2$ de $4$ quadrados, devemos ter um quadrado com $0$ ou $1$ quadros pintados pois se tivessemos um número maior ou igual a dois em cada bloco teríamos um número maior ou igual que $32$ de quadros pintados.
[Exemplo]
Um triângulo equilátero não pode ser completamente coberto por dois triângulos equiláteros menores.
Temos três vértices do triângulo maior, se houvesse cobertura, um dos triângulos cobriria dois vértices e portanto teria um segmento interno com medida maior do que seu lado, o que não pode acontecer.
{Aplicações}
[Exemplo]
No município do Rio de janeiro há pelo menos $6$ milhões de pessoas. Sabendo que cada pessoa tem no máximo $500$ mil fios de cabelo na cabeça segue que no Rio de Janeiro existem pelo menos
$$\frac{6 \;000\; 000}{500\;000}=12 $$
pessoas que não são carecas e possuem a mesma quantidade de fios de cabelo na cabeça.
[Exemplo]
Rodrigo tem $1624$ contatos no facebook. Pelo menos quantos contatos dele fazem aniversário no mesmo dia?
$$\frac{1624}{365}>4 $$
logo pelo menos $5$ amigos fazem aniversário no mesmo dia.
[Exemplo]
Se você pega cinco cartas de um baralho de 52 cartas, então pelo menos duas vão ser do mesmo naipe.
Aqui a divisão feita é de $5$ (número de cartas retiradas) por $4$ (número de naipes),
$$ \frac{5}{4}>1 $$
logo temos pelo 2 cartas do mesmo naipe.
{Notações }
Primeiro, vamos introduzir uma notação, denotaremos neste texto $I_n=\{1, \cdots, n\} .$
{Princípio da casa dos pombos -PCP}
[Proposição][Princípio das gavetas de Dirichlet- Ou princípio da casas dos pombos.]
Se temos $m$ conjuntos $(A_k)_1^m$ e $n$ elementos $n>m$, com $\sum^{m}_{k=1}|A_k|=n$ então existe $A_t$ dentre os $(A_k)_1^m$, tal que $|A_t|>1.$
Esse resultado diz que se temos $n$ elementos e $m$ conjuntos tais que $n>m$ então deve haver um conjunto com pelo menos $2$ elementos.
[Demonstração]
Supondo que $|A_k| \leq 1\; \forall \;k$, então aplicando a soma $\sum^{m}_{k=1}$ em ambos lados dessa desigualdade temos
$$n=\sum^{m}_{k=1}|A_k|\leq m \Rightarrow n \leq m $$
o que contraria a hipótese de $n>m$
,portanto deve valer $|A_t|> 1 $ para algum $t \in I_n$.
C.Q.D.
[Exemplo]
Um professor apostou com seus alunos que em sua turma haveria dois alunos que fazem aniversário no mesmo dia do mês. O professor sabia que ganharia a aposta. Quantos alunos no mínimo tinha em sua turma?
Um mês tem no máximo $31$ dias, se temos no mínimo $32$ alunos pelo $PCP$ pelo menos dois fazem aniversário no mesmo mês.
[Proposição]
Seja um grupo de $n$ pessoas $n \geq 2$ existem pelo menos duas pessoas com o mesmo número de conhecidos.
[Demonstração]
Vamos considerar que a relação de conhecer seja simétrica, isto é, se $A$ conhece $B$ então $B$ conhece $A$ e que n\ta o seja reflexiva $A $ n\ta o conhece $A$ (estranho?). Cada pessoa pode conhecer no máximo $n-1$ pessoas (pois n\ta o consideramos conhecer a si mesmo) e no mínimo $0$, vamos separar então essas pessoas em $n$ conjuntos definidos pela quantidade de pessoas que cada uma conheça. Sendo $A_{k}$ o conjunto formado por pessoas que conhecem $k$ pessoas. Temos que se $A_{0}$ possui uma pessoa, pelo menos, então $A_{n-1}$ deve ser vazio não haverá uma pessoa que conheça todas as outras. Se $A_{n-1}$ possui pelo menos uma pessoa então $A_{0}$ \'e vazio, em qualquer um desses casos vamos ter $n$ pessoas para $n-1$ conjuntos, logo pelo princípio da casa dos pombos segue a proposição. (Caso $A_{n-1}$ e $A_{0}$ sejam vazios temos $n$ pessoas para $n-2$ conjuntos então a proposição segue também.)
C.Q.D.
[Proposição]
Todo subconjunto de $I_{2n}$ contendo $n+1$ elementos possui n\'umeros consecutivos (e logo primos entre si).
[Demonstração]
Dividimos os elementos de $I_{2n}$ que t\^em $2n$ elementos em $n$ conjuntos com $2$ elementos da forma $\{k,k+1\}$ com $k$ em $[1,2n-1]$, temos que escolher ent\ta o $n+1$ elementos nesses conjuntos de $n$ elementos, assim pelo princ\'ipio da casa dos pombos pelo menos um deles vai ter $2$ elementos , logo consecutivos e primos entre si.
C.Q.D.
[Proposição]
Sejam $p$ bolsos e $n$ moedas, então podemos dividir as $n$ moedas entre os $p$ bolsos com a condição de cada bolso ter quantidade distinta de outro bolso e ter no mínimo $s$ moedas $\Leftrightarrow$ o número de moedas for maior ou igual ao valor $ps+\frac{p(p-1)}{2}.$
[Demonstração]
Sejam $p $ bolsos, cada um dos bolsos simbolizaremos por $a_{k}$ com $k \in I_p$, como cada bolso deve ter no mínimo $s$ moedas colocamos $s$ moedas em cada bolso, considere então $a_{1}$, ele é um bolso que possui $s$ moedas, mas como os outros bolsos devem ter quantidade diferente de $a_{1}$ então adicionamos uma moeda a cada outro bolso, assim $a_{k}$, $k \neq 1$ terá $s+1$ moedas, continuamos o processo com $a_{2}$ que possui $s+1$ moedas e adicionamos aos outros bolsos que não $a_{1}$ e $a_{2}$ $+1$ moeda, no fim desse processo teremos que $a_{k}$ terá $s+k-1$ moedas, tomamos a soma dessas moedas então
$$\sum^{p}_{k=1}s+k-1 =sp +\sum^{p}_{k=1}(k-1)=ps+\sum^{p-1}_{k=0}(k)=ps+\frac{k(k-1)}{2}\bigg|^{p}_{0}=ps+\frac{p(p-1)}{2}$$
então deve-se ter no mínimo essa quantidade de moedas $ps+\frac{p(p-1)}{2}$, qualquer valor superior a essa quantidade pode ter a diferença adicionada ao $p$-ésimo bolso, que as condições do problema ainda continuam verificadas.
C.Q.D.
[Exemplo]
Um saco contém objetos de duas cores, branca e preta. Qual o menor número de objetos que podemos tirar de modo a garantir que dois objetos retirados possuam a mesma cor?
A quantidade é de três objetos. Ao retirar dois objetos, podemos ter um de cada cor, ao retirarmos três objetos pelo menos dois devem possuir a mesma cor. Podemos pensar nesse caso como sendo duas casas, uma casa "branca " e a outra casa "preta" ao colocarmos três objetos nas duas casas, alguma casa deve ter dois objetos pelo princípio da casa dos pombos.
[Exemplo]
Mostre que dados $m+1$ números é possível escolher dois deles tais que sua diferença seja divisível por por $m$.
Resolvemos esse problema usando congruências , deseja-se provar que entre os $m+1$ números existem dois $a_1$ e $a_2$ tais que
$$a_1 \equiv a_2 \mod \;m $$
pois isso vale $\Leftrightarrow$ $m| (a_1-a_2)$ ou que $a_1 $ e $a_2$ possuem o mesmo resto na divisão por $m$ .
Os possíveis restos(casas) são $m$, naturais variando de $0$ até $m-1$, cada um dos $m+1$ inteiros deve estar em uma dessas "casas" como temos $m+1$ elementos para $m$ casas então o princípio da casa dos pombo garante que dois deles devem estar na mesma casa e por isso possuem mesmo resto na divisão por $m$, que equivale a dizer que sua diferença é divisível por $m$ .
[Exemplo][OBM 2012-Nível 3- Primeira fase -Questão 3]
Em uma pesquisa de rua, cada entrevistado respondeu a quatro perguntas, podendo sua resposta
ser sim ou não, para cada uma das perguntas. Qual o número mínimo de entrevistados para
garantirmos que duas pessoas responderam igualmente a todas as perguntas?
Temos duas respostas para cada pergunta, então no total temos $2^4 =16$ perguntas pelo princípio da casa dos pombos precisamos ter pelo menos $17$ entrevistados .
[Proposição][ Princípio geral da casa dos pombos.]
Se temos $m$ conjuntos $(A_k)_1^m$ e $n$ elementos, com $\sum^{m}_{k=1}|A_k|=n$ então existe $A_t$ em $(A_k)_1^m$ tal que $|A_t|\geq \lceil\frac{n}{m} \rceil .$
Esse resultado diz que se temos $n$ elementos e $m$ conjuntos então deve haver um conjunto com pelo menos $\lceil\frac{n}{m} \rceil$ elementos.
[Demonstração]
Suponha por absurdo que todos conjuntos tenham $|A_k|\leq \lceil\frac{n}{m} \rceil-1 $ isso vale $\Leftrightarrow |A_k|<\frac{n}{m} $ então somando todos temos
$$\underbrace{\sum_{k=1}^{m}|A_k| }_{n} < \sum_{k=1}^{m} \frac{n}{m}=m\frac{n}{m} =n \Leftrightarrow $$
$$n<n $$
o que é absurdo, então deve realmente existir um conjunto $A_t$ com $|A_t| \geq \lceil\frac{n}{m} \rceil . $
C.Q.D.
[Exemplo]
Temos $25$ caixas de maçãs, sendo maçãs de $3$ tipos, cada caixa possui apenas um tipo de maçã. Mostre que pelo menos $9$ caixas possuem o mesmo tipo de maçã .
Pensamos nas casas, como sendo os tipos de maçãs, que são $3$ e nas caixas como sendo os pombos, usando o principio geral temos pelo menos
$$ \lceil\frac{25}{3} \rceil=9\; caixas .$$
[Exemplo]
Um país possui $M$ times de futebol, cada um deles com $11$ jogadores. Existem $10 $ aviões, cada um sendo ocupado por $M$ jogadores, um jogador prefere ir de bicicleta mostre que é garantido que pelo menos um time inteiro vai conseguir ir completo na viagem .
Temos $10 .M+1$ jogadores com locomoção garantida, num total de $11 M =10M+M$ então $M-1$ jogadores ficam ainda sem transporte, para um número $M$ de times, então algum time deve possuir todos seus elementos com ida garantida.
[Exemplo]
Dados $8$ números naturais positivos diferentes, todos menores que $16$, então pelo menos três pares deles possuem a mesma diferença positiva.
Sejam $x_1, \cdots , x_8$, as diferenças variam de $15-1=14$(que pode ser escrito de apenas uma maneira) até $1$ no caso de números consecutivos. O número de diferenças é $k-1$ com $x_k$
$$x_k-x_{k-1},\;\cdots\; ,x_k-x_1. $$
Somando de $k=2$ até $8$, temos
$$\sum_{k=2}^8 (k-1)= \sum_{k=1}^7 (k) = \frac{7.8}{2} = 28 . $$
Sendo que para diferença $14$ temos apenas uma possibilidade, que é $15-1$, então restam $27$ para $13$ diferenças. Então temos $3$ como resultado.
[Exemplo]
Em um conjunto de $7$ pessoas, a soma de suas idades é de $332$ anos, prove que podemos escolher três pessoas tais que a soma de suas idades não seja menor do que $142$ anos .
Enumeramos as $7$ pessoas da maior idade para menor idade . Suponha que a idade das três pessoas mais velhas $x_1,x_2,x_3$ sejam menor que $142$, daí a soma da idade de mais novas também
$$\underbrace{x_1+x_2+x_3}_{< 142}+\underbrace{x_4+x_5+x_6}_{<142}+x_7 =332 < x_7+284 \Rightarrow x_7 > 332 -284 =48 ,$$
disso segue também que cada $x_k> 48$ pois $x_7$ é o menor, então a soma total é maior que $7.48=336$ que é absurdo .
Então deve valer que $x_1+x_2+x_3 \geq 142$ , para a soma dos maiores.
{Princípio da casa dos pombos e geometria}
[Exemplo]
Qual o maior número de quadrados em um tabuleiro $8 \times 8$ que pode ser colorido de azul, de modo que em qualquer arranjo de três quadrados (um triminó), pelo menos um quadrado não está colorido de azul?.
A resposta é $32$. Se tivéssemos $33$ ou mais quadrados pintados de azul, tomando a divisão do tabuleiros em blocos quadrados $2 \times 2$ de quadrados (temos $16$ deles), teríamos $ \lceil \frac{33}{16}\rceil=3 $ algum dos blocos teria $3$ quadrados pintados, logo um triminó pintado. Com $32$ ainda podemos ter todos triminos com um bloco não colorido, basta pintar dois quaisquer em um dos $16$ blocos, isso totaliza $32$ pintados.
[Exemplo]
Qual o menor número de quadrados de um tabuleiro $8 \times 8$ que pode ser colorido de azul de modo que em qualquer triminó, pelo menos um quadrado esteja colorido de azul?
Com $32$ quadrados coloridos de azul, temos sempre um quadrado de um triminó de azul (fazer imagem). Com $31$ quadrados azuis temos um triminó não colorido de azul, pois separando o tabuleiro em $16$ blocos $2 \times 2$ de $4$ quadrados, devemos ter um quadrado com $0$ ou $1$ quadros pintados pois se tivessemos um número maior ou igual a dois em cada bloco teríamos um número maior ou igual que $32$ de quadros pintados.
[Exemplo]
Um triângulo equilátero não pode ser completamente coberto por dois triângulos equiláteros menores.
Temos três vértices do triângulo maior, se houvesse cobertura, um dos triângulos cobriria dois vértices e portanto teria um segmento interno com medida maior do que seu lado, o que não pode acontecer.
{Aplicações}
[Exemplo]
No município do Rio de janeiro há pelo menos $6$ milhões de pessoas. Sabendo que cada pessoa tem no máximo $500$ mil fios de cabelo na cabeça segue que no Rio de Janeiro existem pelo menos
$$\frac{6 \;000\; 000}{500\;000}=12 $$
pessoas que não são carecas e possuem a mesma quantidade de fios de cabelo na cabeça.
[Exemplo]
Rodrigo tem $1624$ contatos no facebook. Pelo menos quantos contatos dele fazem aniversário no mesmo dia?
$$\frac{1624}{365}>4 $$
logo pelo menos $5$ amigos fazem aniversário no mesmo dia.
[Exemplo]
Se você pega cinco cartas de um baralho de 52 cartas, então pelo menos duas vão ser do mesmo naipe.
Aqui a divisão feita é de $5$ (número de cartas retiradas) por $4$ (número de naipes),
$$ \frac{5}{4}>1 $$
logo temos pelo 2 cartas do mesmo naipe.
Comentários
Postar um comentário