Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
11
O PRINCÍPIO DAS GAVETAS DE DIRICHLET
THE PRINCIPLE OF DIRICHLET DRAWERS
Juliano Ferreira de Lima¹; Marco Antonio Travassos¹; Vanessa de
Freitas Travello¹; Antonio Carlos Tamarozzi².
¹Aluno do curso de Lic. em Matemática da UFMS e bolsista do Programa de Educação
Tutorial/SESU – Matemática – UFMS - Campus de Três Lagoas;
²Professor Associado do curso de Lic. em Matemática da UFMS e tutor do Programa
de Educação Tutorial/SESU – Matemática – UFMS - Campus de Três Lagoas;
¹[email protected]; ²[email protected];
RESUMO - O Princípio das gavetas de Dirichlet também conhecido
como O Princípio da Casa dos Pombos, pode ser apresentado tanto
como um resultado matemático, quanto como um método de prova.
Como um resultado matemático, o Princípio das gavetas de Dirichlet é
bastante simples e intuitivo e parece, à primeira vista, ser de pouca
aplicabilidade. Mas, quando usado como um método de prova, ele se
torna uma ferramenta extremamente poderosa na resolução de
problemas, como veremos no decorrer desse trabalho. O Princípio das
Gavetas de Dirichlet recebeu este nome depois que o matemático
alemão Dirichlet usou frequentemente este princípio em seu trabalho,
no século XIX.
Palavras-chave: Casa dos pombos; Função; Análise de dados;
Contagem e Conjuntos.
ABSTRACT - The Principle of the drawers of Dirichlet's Principle also
known as the House of Pigeons, can be presented both as a
mathematical result, and as a method of proof. As a mathematical
result, the Dirichlet drawer principle is quite simple and intuitive and
seems at first sight to be of little applicability. But when used as a
method of proof, it becomes an extremely powerful tool in solving
problems, as we shall see in the course of this work. The Principle of
Drawers Dirichlet is named after the German mathematician Dirichlet
often used this principle in his work, in the nineteenth century.
Keywords: House of pigeons; Function; Data Analysis; Sets and
Counting.
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 11-19. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000078
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
12
1 INTRODUÇÃO
2 METODOLOGIA
No presente trabalho apresentamos o
O trabalho é resultado de uma
princípio da casa dos pombos, também
pesquisa teórica, desenvolvida através de
conhecido como princípio das gavetas ou
discussões do tema com o orientador e
princípio
princípio
apresentações de seminários. Teve início
matemático baseia-se na afirmação simples
como parte das atividades do programa de
de que, se temos que distribuir
pombos em
educação tutorial (PET) – Matemática, sobre
gaiolas, então ao menos uma das
estudos de métodos de contagem, dentro da
gaiolas conterá, no mínimo, dois pombos.
área de Introdução à Combinatória e
Matematicamente falando, isto é equivalente
Aritmética. O trabalho incluiu as etapas de
a dizer que se o número de elementos de um
leitura e resoluções de exercícios e a seleção
conjunto finito
for maior do que o número
de atividades propostas com aplicações
de elementos de um outro conjunto , então
interessantes para propor a estudantes do
uma função de
ensino
de
Dirichlet.
em
Este
não pode ser injetiva.
médio.
Como
medida
para
o
O princípio de Dirichlet pode ser aplicado em
despertar do interesse no tema, priorizamos
muitos problemas formais, incluindo aqueles
problemas com aplicações em situações
que envolvem um conjunto infinito. Ele é
geométricas.
muito útil para resolver problemas que, pelo
menos à primeira vista, não são imediatos e
admite
consequências
conforme
mostram
apresentamos
surpreendentes,
os
neste
3 RESULTADOS
exemplos
trabalho.
A
Suponha que um grupo de
que
voe
sua
empoleirarem-se. Visto que há
aplicação exige identificar, na situação dada,
para
dentro
de
pombos
casas
para
pombos e
casas, pelo menos uma dessas
casas
quem faz o papel dos pombos e quem faz o
deverão ter no mínimo dois pombos. O
papel das gaiolas.
funcionamento deste processo pode ser
O
admite
atestado com o seguinte argumento. Se cada
generalizações que também possui grande
casa tiver no máximo um pombo, então no
espectro aplicativo. As demonstrações e
máximo
aplicações podem ser apresentadas de
sobrando um pombo. Por esta razão este
maneira simples, acessível e cativante aos
principio de contagem matemática, recebeu
estudantes e constituem o objetivo deste
o nome de “Princípio da casa dos pombos”.
trabalho.
princípio
de
Dirichlet
pombos estarão acomodados
Vamos
visualizar
aplicações
evidenciam esta abordagem
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 11-19. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000078
que
como um
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
13
método
importante
de
contagem
Corolário. Uma função
de um
matemática, que ultrapassa este senso
conjunto
comum de pombos e casas.
conjunto com elementos não é injetiva.
O Princípio da Casa dos Pombos foi
ou mais elementos para um
Demonstração. Suponhamos que para
utilizado publicamente, pela primeira vez,
cada elemento
pelo
temos uma caixa que contém todos os
matemático
Dirichlet
em
1834
alemão
com
G.
o
Lejeune
nome
de
elementos
Schubfachprinzip ("princípio das gavetas").
Em
sua
homenagem,
portanto,
ficou
, no contradomínio de
do domínio de
, tal que
. Como o domínio contém
ou
mais elementos e o contradomínio contém
conhecido como Princípio das Gavetas de
apenas
Dirichlet.
pombos nos diz que uma das caixas contém
Seja
elementos, o princípio da casa dos
Teorema 1. (O Princípio de Dirichlet)
dois ou mais elementos
um número inteiro positivo. Se
significa que
ou mais objetos são colocados dentro de
não pode ser uma função
injetora.
caixas, então há uma caixa que terá dois ou
mais objetos.
do domínio. Isso
Exemplo 1. Quantos alunos deve
haver em uma sala para podermos afirmar
Demonstração. Vamos demonstrar o
que pelo menos dois estudantes tenham a
princípio da casa dos pombos usando uma
mesma nota em uma determinada prova, se
demonstração por absurdo. Suponha que
a nota é graduada em um número inteiro de
nenhuma das
caixas contenha mais de um
a
objeto. Então, a contagem de no máximo um
?
Solução: De 0 a 10 existem
objeto em cada uma das caixas, fornece um
números possíveis. O princípio de Dirichlet
total de no máximo
mostra que entre
objetos, o que é uma
contradição, porque há pelo menos
estudantes há pelo
menos dois com a mesma nota.
objetos.
O princípio da casa dos pombos
O princípio da casa dos pombos pode
afirma que deverá haver pelo menos dois
ser utilizado para demonstrar resultados
objetos na mesma caixa quando existirem
puramente matemáticos, como o seguinte.
mais objetos que caixas. Desta forma, o
Se o número de elementos de um conjunto
princípio de Dirichlet, pode ser generalizado
finito
da forma seguinte, onde, o símbolo ⌈ ⌉
é maior que o número de elementos
de outro conjunto , então uma função de
em
não
pode
ser
injetiva,
como
representa o maior inteiro menor ou igual a
.
observamos no corolário a seguir.
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 11-19. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000078
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
14
Teorema 2. (A Generalização do
Princípio de Dirichlet). Se
colocados em
objetos são
caixas, então há pelo menos
uma caixa com ⌈
⌉ objetos.
Demonstração.
Faremos
)
Exemplo 3. Em uma gaveta há
de meias brancas e
objetos. Então, o
número total de objetos é no máximo
(⌈ ⌉
((
⌉
, assim
podemos afirmar que pelo menos 42 pessoas
uma
Suponha que nenhuma das caixas
⌉
Dirichlet vemos que: ⌈
nasceram no mesmo mês.
demonstração por absurdo.
tenha mais que ⌈
Solução: Utilizando o teorema de
)
pares
pares de meias pretas.
Quantas meias deverão ser retiradas ao
acaso para termos certeza de obter um par
de meias da mesma cor?
Solução: Pensando nas meias como
)
pombos e nas duas cores como as duas casas,
em que a inequação ⌈
⌉
foi
usada. Isto é um absurdo, pois há um total de
vemos que com
com a mesma cor.
objetos. Portanto, existe ao menos uma
caixa com ⌈
⌉ objetos.
Exemplo 4. João convidou 49 amigos
para sua festa de aniversário. Podemos
Existem inúmeros problemas que
avaliam o número mínimo de objetos, de tal
forma que pelo menos
afirmar que em sua festa existiam pelo
menos:
desses objetos
deverão estar uma distribuídos em
caixas
a)
as
caixas.
Assim,
percebemos
trivialmente que se tivermos
objetos, a
generalização do princípio da casa dos
pombos afirma que existem pelo menos
objetos em uma das caixas, desde que
⌈
⌉
.
Apresentamos
pessoas que fazem aniversario no
mesmo mês ?
quando esses objetos forem distribuídos
entre
meias haverá duas meias
b)
pessoas que nasceram no mesmo
c)
pessoas que nasceram no mesmo
ano?
dia da semana?
d)
pessoas que nasceram no mês de
janeiro?
Solução:
a
seguir,
uma
a) Verdadeira.
sequencia de exemplos que utiliza o Principio
O ano tem
de Dirichlet nas duas formas, clássica e
cada mês como uma casa. Assim,
extendida.
Pelo princípio da casa dos pombos, vemos:
Exemplo 2. Entre
meses e podemos considerar
pessoas pelo
[
menos quantas nasceram no mesmo mês?
]
b) Falsa.
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 11-19. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000078
.
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
15
O numero 49 não é suficientemente grande
lado . Mostremos que pelo menos um dos
para podermos assegurar a afirmação, diante
segmentos
do número de anos que os convidados
comprimento menor ou igual a √ .
podem ter nascido.
eles
determinam
tem
Solução: Neste caso, está claro que os
c) Verdadeira.
A semana tem
que
objetos são os
pontos.
dias (domingo, segunda,
terça, ..., sábado), assim, a afirmação é
verdadeira pois
[
]
d) Falsa.
Pelo item (a) podemos garantir que pelo
menos um mês em que pelo menos
pessoas nasceram, mas o princípio da casa
dos pombos, não assegura qual é o mês.
Figura 1. Ilustração do enunciado.
Exemplo 5. Qual o menor número de
alunos necessário em uma sala de aula para
podermos afirmar que pelo menos quatro
receberão a mesma nota, se são possíveis
cinco notas:
.
de
estudantes necessários para garantir que
pelo menos quatro alunos tirem a mesma
nota é o menor número inteiro
⌉
identificação das gavetas. Devemos subdividir
o quadrado dado em
partes de modo tal
que a distância entre dois pontos situados em
Solução: O número mínimo
⌈
O ponto chave da resolução está na
uma destas partes nunca seja maior que √ .
(Figura2).
tal que
. Através da generalização do
princípio da casa dos pombos vemos que o
menor número inteiro é
. Notemos
que se tivermos apenas
estudantes, é
possível que haja três que receberão cada
nota, e não quatro. Assim,
é o número
procurado.
Exemplo 6. Escolhem-se
pontos ao
acaso sobre a superfície de um quadrado de
Figura 2. Resolvendo o enunciado.
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 11-19. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000078
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
16
Solução: Por definição, num plano
Basta dividi-lo nos quatro quadrados
existem infinitos pontos que estão contidos
determinados pelas retas que unem os
nele e estes, supostamente podem ser
pontos médios dos lados opostos.
divididos em azul e vermelho.
Imaginemos neste plano um triângulo
equilátero de lado igual a 10 cm, conforme a
figura seguinte
Figura 3. Explorando o enunciado.
Utilizando o Teorema de Pitágoras no
Triângulo ABC, vemos que
√ , logo, os
Figura 4. Triângulo equilátero.
dois pontos que estão dentro da mesma
gaveta não podem ter comprimento maior
que √ .
Como são duas cores (casas) e três
pontos (pombos). Pelo princípio da casa dos
Assim, cada uma destas quatro
gavetas, a distância máxima entre dois
pontos é igual à sua diagonal, que mede
Portanto, dados
.
pontos, pelo menos
pombos teremos dois pontos da mesma cor.
Exemplo
8.
Consideremos
quadrado com os lados medindo
um
. Na
superfície quadrangular por ele determinada,
estarão em uma mesma “gaveta” e, assim,
marquemos
determinam um segmento de comprimento
Mostre que pelo menos um dos segmentos
menor ou igual a√ .
determinados
Exemplo 7. Todos os pontos de um
plano são pintados de azul ou vermelho.
Provemos que é possível encontrar dois
pontos
da
mesma
cor
que
distam
aleatoriamente
por
esses
pontos.
pontos
tem
comprimento menor que ou igual a √ u.c.
(u.c. significa unidade de comprimento).
Solução: Consideremos um quadrado
de lado igual a
, em seguida, vamos
exatamente 10 cm.
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 11-19. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000078
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
17
dividi-lo em
à
quadrados menores lado igual
.
existirão, pelo menos, dois pontos cujo
segmento por eles determinado mede no
máximo √
.
Exemplo 9. Escolhem-se nove pontos
no interior de um quadrado de lado
.
Mostrar que é possível escolher três pontos
de tal forma que a área do triângulo que
formam é menor ou igual a
Solução: Sabemos que os nove pontos
Figura 5. Quadrado de lado
.
estão contidos no quadrado de lado
.
Consideremos
e
e
Ao considerarmos os quadradinhos
um
quadrado
pontos médios do quadrado
como mostra a figura a seguir.
como casas e os pontos como pombos, a
quantidade de casas será
a quantidade de pombos
que é menor que
, assim, pelo
Princípio da Casas dos Pombos, pelo menos,
um quadrado possuirá
pontos.
Consideremos o triângulo retângulo
.
Figura 7. Quadrado de lado
Notemos que temos
pombos) e
.
pontos (nove
quadrados menores (quadro
casas), assim, pelo princípio da casa dos
pombos, em um quadrado terá pelo menos
pontos.
Suponhamos que os três pontos
Figura 6. Quadrado de lado
.
estejam no quadrado
Utilizando o Teorema de Pitágoras no
Triângulo ABC, vemos que
√
, logo,
, logo, a maior
distância entre eles pode ser apenas
,
ou seja, apenas no caso dos pontos serem
exatamente os vértices do quadrado.
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 11-19. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000078
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
18
Consideremos o triângulo formado
por
.
há apenas
inteiros positivos ímpares
menores que
, podemos afirmar, a partir
do princípio da casa dos pombos, que dois
dos inteiros
deverão ser
iguais. Então, há números inteiros
que
. Considere
comum de
e
como o valor
. Assim,
. Concluímos que se
divide ; enquanto e
divide
e , tal
e
, então
, então
.
Figura 8. Triângulo isósceles de lado
4 DISCUSSÃO
.
Alguns resultados e afirmações na
No triângulo
matemática tornam-se atraentes porque
temos:
exploram relações entre conjuntos finitos e
são expressos em uma linguagem coloquial.
Parte desta atratividade vem justamente do
fato
De onde segue a afirmação.
números inteiros positivos
não excedentes a
deverá haver um
número inteiro que divide um dos outros
inteiros.
números inteiros
por
um inteiro ímpar. Em outras palavras, temos
para
um
ser
formulados
vezes, a partir deles, diversos problemas são
resolvidos, sem recorrer a fórmulas ou a
técnicas complicadas.
O Principio de Dirichlet apresentado
uma formulação simplificada e de grande
facilidade de assimilação, o referido tem
como um produto de uma potência de
é
podem
neste trabalho, descreve esta situação. Com
Solução: Podemos escrever cada um
dos
que
simplificadamente, e, não obstante, muitas
Exemplo 10. Mostremos que entre
quaisquer
de
condições de resolver problemas de impacto,
dentro e fora da Matemática.
, em que
número
inteiro
(possivelmente nulo) e
não
negativo
5 CONSIDERAÇÕES FINAIS
é ímpar. Os inteiros
O trabalho é resultado de uma
são todos números inteiros
pesquisa teórica, desenvolvida através de
positivos ímpares menores que
. Visto que
discussões do tema com o orientador e
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 11-19. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000078
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
19
apresentações de seminários como parte das
REFERÊNCIAS
atividades do Programa de Educação Tutorial
LIMA, Elon Lages. Número e Funções Reais /
Elon Lages Lima. Rio de Janeiro: SBM, 2013.
297p. (Coleção PROFMAT, 07).
(PET) – Matemática (UFMS/CPTL), no estudo
de Introdução à Combinatória e Aritmética. O
trabalho incluiu uma etapa de leitura e
resoluções de exercícios, desenvolvimento
das atividades propostas e a investigação dos
resultados obtidos. O estudo e as atividades
desenvolvidas foram avaliados através da
apresentação de seminários de discussão.
Como
resultado
deste
trabalho
LIMA, Elon Lages. A Matemática do Ensino
Médio / Elon Lages Lima. Rio de Janeiro:
SBM, 1999. (Coleção do Professor de
Matemática).
MARTINEZ, Fabio Brochero; et al. Teoria dos
números: um passeio com primos e outros
números familiares pelo mundo inteiro /
Fabio Brochero Martinez; et al. 2 ed. Rio de
Janeiro: IMPA, 2013, 481 P. (Projeto
Euclides).
apresentamos a proposta de inserir o
Princípio da Casa dos Pombos no ensino
básico, como recurso para despertar o
interesse do estudo pela Matemática. Com
efeito, trata-se de um assunto acessível, para
o qual podem ser elaboradas sequencias de
problemas interessantes e relevantes para o
cotidiano
dos
estudantes.
De
maneira
gradual pode atingir um grau sofisticado de
generalização
do
tema,
de
modo
a
aperfeiçoar competências de investigação,
organização e comunicação da informação.
MORGADO, Augusto César de Oliveira;
CARVALHO, João Bosco Pitombeira;
CARVALHO,
Paulo
Cezar
Pinto;
FERNANDEZ,
Pedro.
Análise
Combinatória e Probabilidade com as
soluções dos exercícios. Coleção do
Professor de Matemática. Nona edição. Rio
de Janeiro: Sociedade Brasileira de
Matemática, 2006.
MUNIZ NETO,Antonio Caminha. Tópicos de
Matemática Elementar: combinatória /
Caminha Muniz Neto. -1. ed. Rio de janeiro:
SBM, 2012.
ROSEN, Kenneth H. Matemática discreta e
suas aplicações / Kenneth H. Rosen;
[tradução João Giudice]. São Paulo: McGrawHill, 2009.
AGRADECIMENTOS
Os autores agradecem ao FNDE Fundo Nacional de Desenvolvimento da
SCHEINERMAN, Eduard R.
Matemática
Discreta: uma introdução/ Thomson
Learning, 2006.
Educação, pelo suporte financeiro concedido
ao PET – Matemática (UFMS/CPTL), no
desenvolvimento das atividades de ensino,
pesquisa e extensão, que possibilitaram este
trabalho.
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 11-19. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000078