Mostre que existe um tabuleiro
, cujas casas são todas pretas ou brancas, no qual nenhum retângulo tem as 4 casas dos vértices da mesma cor. Mostre que, em todo tabuleiro
cujas casas são todas pretas ou brancas, sempre existe um retângulo cujas 4 casas extremas têm a mesma cor. (Observação: no tabuleiro casas adjacentes não têm necessariamente cores diferentes).
Passo 1
O problema trata de colorir as casas de um tabuleiro de 4 linhas por
colunas em duas cores (branco e preto) de modo que não exista retângulo cujos quatro vértices sejam da mesma cor.
(a) Mostrar que já é possível para .
(b) Mostrar que, se , forçando 7 colunas, sempre aparece um retângulo monocromático.
(a) Mostrar que já é possível para
(b) Mostrar que, se
Para resolver precisaremos usar:
- Uma construção explícita para
baseada em subconjuntos de tamanho 2 de . - Um argumento de contagem (pigeonhole) sobre pares de linhas para
.
Passo 2
Construção para
.
Em cada coluna escolhemos exatamente duas linhas para pintar de branco, e as outras duas de preto. Há maneiras de escolher 2 linhas entre 4; usamos todas elas.
Nomeemos as linhas por . Cada coluna
corresponde ao subconjunto
Em cada coluna escolhemos exatamente duas linhas para pintar de branco, e as outras duas de preto. Há
Nomeemos as linhas por
e pintamos de branco as linhas em
e de preto as linhas em
.
Assim obtemos exatamente 6 colunas, cada uma com 2 brancas e 2 pretas, percorrendo todos os pares de linhas de 1 a 4.
Assim obtemos exatamente 6 colunas, cada uma com 2 brancas e 2 pretas, percorrendo todos os pares de linhas de 1 a 4.
Passo 3
Não há retângulo monocromático na construção de
.
Considere duas colunas quaisquer, digamos corresponentes a e
, ambos subconjuntos de tamanho 2.
Considere duas colunas quaisquer, digamos corresponentes a
- Para aparecer retângulo branco em duas linhas
, precisaríamos ter . Mas e implica . Logo não há par contido em ambos. - Para aparecer retângulo preto em
, precisaríamos ter . Mas e, de novo, .
Em consequência, nenhuma dupla de colunas produz quatro cantos todos brancos nem todos pretos.
Passo 4
Prova de que em qualquer coloração de
há retângulo monocromático.
Denote por as colunas, e em cada coluna
considere o conjunto de pares de linhas em que essa coluna é monócroma (isto é, as duas casas têm a mesma cor). Formalmente,
Denote por
Há
pares
no total. Em cada coluna
, se ela tiver
brancas e
pretas, então
Como temos 7 colunas, a soma total das cardinais
. Pelo princípio da casa dos pombos, ao redistribuir esses “marcadores de pares” em apenas 6 pares possíveis, algum par fixo
aparece em pelo menos
dos
. Ou seja, existem ao menos três colunas
nas quais as linhas
e
são monócronas (ou seja, ou todas brancas ou todas pretas). Dessas três colunas, duas terão exatamente a mesma cor em
(duas brancas ou duas pretas). Essas duas colunas e as linhas
formam um retângulo cujos quatro vértices são da mesma cor.
Resposta
(a) Para
basta usar todas as
colunas com exatamente duas casas brancas e duas pretas, escolhendo cada par de linhas para ser a parte branca. Esse arranjo não permite intersecção de dois pares iguais nem de dois pares de complementos iguais, logo não há retângulo monocromático.
(b) Qualquer coloração de gera, por contagem de pares de linhas monócronas, um par
que surge em pelo menos três colunas; dessas, duas terão a mesma cor em
e em
, dando um retângulo todo branco ou todo preto.
(b) Qualquer coloração de