O Princípio das Gavetas

Se distribuir mais objetos do que gavetas pelas gavetas, alguma ficará com dois. Este é todo o princípio; a mestria está na escolha das gavetas. Aqui tem três problemas com gavetas ocultas: escolha os números ou as cores das ligações e a página mostrará qual gaveta transbordou.

Exemplo resolvido — O Princípio das Gavetas

Números nas gavetas	uma colisão é forçada
Gaveta com dois	5 \| 10
gaveta 9	9
gaveta 11	11
gaveta 13	13
gaveta 15	15

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — O Princípio das Gavetas

O princípio das gavetas: se N objetos são colocados em k gavetas e N > k, alguma gaveta contém pelo menos dois. Mais precisamente, alguma gaveta contém pelo menos ⌈N/k⌉, o menor número inteiro que é maior ou igual a N/k.

O que significa cada símbolo

N: o número de objetos colocados
k: o número de gavetas
⌈N/k⌉: N/k arredondado por excesso: o mínimo que a gaveta mais cheia tem de conter

De onde vem a fórmula

Porquê ⌈N/k⌉. Se cada gaveta contivesse menos de N/k objetos, as k gavetas juntas conteriam menos de k × N/k = N, no entanto contêm todos os N. Portanto alguma gaveta contém pelo menos N/k, e como tem um número inteiro de objetos, contém pelo menos ⌈N/k⌉. Cinco ligações em duas cores dão ⌈5/2⌉ = 3 de uma cor; dezasseis ligações em três cores dão ⌈16/3⌉ = 6.
A escolha das gavetas para os divisores. Cada número inteiro é, de forma única, um número ímpar vezes uma potência de 2, m × 2ᵃ; coloque-o na gaveta m. Dois números numa gaveta são m × 2ᵃ e m × 2ᵇ com a < b, e o primeiro divide o segundo. Os números ímpares de 1 a 2n são 1, 3, …, 2n − 1, o que dá n gavetas, portanto n + 1 escolhas forçam dois na mesma gaveta. O limite é exato: n + 1, …, 2n são n números, um por gaveta, e nenhum divide outro, pois duplicar o menor deles já ultrapassa 2n.
De somas iguais a grupos disjuntos. Dois grupos diferentes A e B com a mesma soma podem partilhar alguns números. Retire os números partilhados de ambos: cada soma desce o mesmo valor, logo continuam iguais. Nenhum dos grupos fica vazio, pois se A estivesse contido em B, B teria uma soma maior, já que todos os números são positivos. O que sobra são dois grupos disjuntos e não vazios com somas iguais, e é isso que a página desenha.

Nove números de 1 a 16: um divide sempre outro 🖖

Escreva cada número como um número ímpar multiplicado por uma potência de 2: 12 = 3 × 4, 10 = 5 × 2. Os números com a mesma parte ímpar vão para a mesma gaveta, e o menor divide o maior, pois diferem apenas por potências de 2. De 1 a 16 existem oito números ímpares, logo oito gavetas, e nove escolhas colocam dois na mesma gaveta. Pressione 9 a 16 para ver oito números que escapam, um por gaveta: apenas 10 das 12.870 escolhas de oito números o fazem. Depois pressione 9 a 16 e 5. Todas as 11.440 escolhas de nove números contêm um par em que um divide o outro, e as gavetas provam-no sem ser preciso verificar nenhuma.

Entre seis pessoas, três são amigos mútuos ou três são desconhecidos 🖖

Pressione Seis pessoas e tome a pessoa 1. As suas cinco ligações apresentam-se em duas cores, logo pelo menos três partilham uma; digamos que são amigos. Se quaisquer dois desses três forem amigos entre si, eles e a pessoa 1 formam três amigos mútuos. Se não o forem, esses três são desconhecidos mútuos. De qualquer forma surge um triângulo, e o argumento nunca precisou de olhar para as cores. Cinco pessoas conseguem evitá-lo, com amizades ao redor de um pentágono e desconhecidos nas suas diagonais. Das 1.024 formas de colorir as ligações de cinco pessoas, 12 evitam um triângulo de uma só cor, e cada uma delas é esse pentágono nalguma disposição. Nenhuma das 32.768 para seis o consegue. Greenwood e Gleason apresentaram este argumento em 1955.

Dez números de dois algarismos escondem sempre duas somas iguais, e nove também 🖖

Pressione Dez números. Dez números distintos de dois algarismos formam 2¹⁰ − 1 = 1.023 grupos não vazios, e um grupo apenas pode somar um valor de 10 até 90 + 91 + … + 99 = 945, o que dá 936 valores. Logo, dois grupos partilham uma soma; retire os números que têm em comum e as somas mantêm-se iguais enquanto os grupos se tornam disjuntos. Este foi o primeiro problema das Olimpíadas Internacionais de Matemática de 1972. Com nove números distintos são 511 grupos contra um máximo de 846 somas, e a contagem nada diz. A verdade vai além da contagem: para que nove números tenham todas as somas de grupo diferentes, um deles tem de ser pelo menos 161 (cálculo de J. P. Grossman), portanto nove números de dois algarismos colidem sempre. Oito podem escapar; pressione Oito que escapam.

Problema resolvido na íntegra

Quantas pessoas forçam um triângulo de uma só cor com três cores? 4 passos
Cada par de pessoas é agora composto por amigos, desconhecidos ou rivais: três cores em vez de duas. Quantas pessoas garantem três que estejam todas ligadas numa única cor?

Abrir este problema na ferramenta
1. Com duas cores, o argumento da página parte das ligações de uma pessoa:
  
  $6 people : 5 links, 2 colours \Rightarrow ⌈ \frac{5}{2} ⌉ = 3 share a colour$
2. Com três cores, tome uma pessoa entre 17. As suas 16 ligações dividem-se em três cores:
  
  $17 people : 16 links, 3 colours \Rightarrow ⌈ \frac{16}{3} ⌉ = 6 share a colour$
3. Se quaisquer dois desses seis estiverem ligados por essa mesma cor, eles e a primeira pessoa formam um triângulo de uma só cor:
  
  $a link of that colour among the 6 \Rightarrow a triangle through person 1$
4. Se não estiverem, esses seis usam apenas as outras duas cores, e a festa de seis pessoas da página já garante um triângulo entre eles:
  
  $no such link \Rightarrow the 6 use 2 colours \Rightarrow a triangle, since R (3, 3) = 6$
Resposta

Dezassete pessoas são sempre suficientes, e Greenwood e Gleason demonstraram em 1955 que dezasseis não são: eles pintaram as ligações de dezasseis pessoas em três cores sem nenhum triângulo de uma só cor. Com quatro cores ninguém conhece a resposta; esta situa-se entre 51 e 62.

$R (3, 3, 3) = 17; 51 \leq R (3, 3, 3, 3) \leq 62$

Percurso de aprendizagem

Métodos de demonstração

Referências (5)

The party problem solved exactly as this page solves it, the pentagon with red sides and blue diagonals for five and one person's five links for six, and Theorem 4, three colours need exactly 17 people, which is the worked problem: R. E. Greenwood and A. M. Gleason, "Combinatorial Relations and Chromatic Graphs", Canadian Journal of Mathematics 7, 1–7 (1955).
The equal-sums problem as it was set, ten distinct two-digit numbers, with the count of 1,023 groups against sums of at most 945: 14th International Mathematical Olympiad, 1972, Problem 1; problem and solution in J. Scholes's IMO archive (Kalva).
Why nine two-digit numbers cannot escape either: nine numbers with all their subset sums different need one at least as large as 161: OEIS Foundation, "A276661: Least k such that there is a set S in {1, 2, ..., k} with n elements and the property that each of its subsets has a distinct sum", The On-Line Encyclopedia of Integer Sequences.
Three colours are settled at 17; four are not, and the answer lies between 51 and 62: OEIS Foundation, "A003323: Multicolor Ramsey numbers R(3,3,...,3), where there are n 3's", The On-Line Encyclopedia of Integer Sequences.
The principle stated and used, including its generalised form, ⌈N/k⌉ in some box: E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §15.8, The Pigeonhole Principle.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.