Mostre que existe um tabuleiro 6 times 4, 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 7 times 4 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 n 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 n=6.
(b) Mostrar que, se n=7, forçando 7 colunas, sempre aparece um retângulo monocromático.
Para resolver precisaremos usar:
  • Uma construção explícita para n=6 baseada em subconjuntos de tamanho 2 de 1,2,3,4.
  • Um argumento de contagem (pigeonhole) sobre pares de linhas para n=7.

Passo 2

Construção para n=6.
Em cada coluna escolhemos exatamente duas linhas para pintar de branco, e as outras duas de preto. Há binom42=6 maneiras de escolher 2 linhas entre 4; usamos todas elas.
Nomeemos as linhas por 1,2,3,4. Cada coluna j corresponde ao subconjunto
Sjsubset1,2,3,4, |Sj|=2,
e pintamos de branco as linhas em Sj e de preto as linhas em 1,2,3,4setminus Sj.
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 n=6.
Considere duas colunas quaisquer, digamos corresponentes a S e T, ambos subconjuntos de tamanho 2.
  • Para aparecer retângulo branco em duas linhas r<s, precisaríamos ter r,ssubset Scap T. Mas |S|=|T|=2 e Sneq T implica |Scap T|<=1. Logo não há par r,s contido em ambos.
  • Para aparecer retângulo preto em r<s, precisaríamos ter r,ssubset S^ccap T^c. Mas |S^c|=|T^c|=2 e, de novo, |S^ccap T^c|<=1.
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 4times7 há retângulo monocromático.
Denote por C1,dots, C7 as colunas, e em cada coluna Ci considere o conjunto de pares de linhas em que essa coluna é monócroma (isto é, as duas casas têm a mesma cor). Formalmente,
Li ;=;lr,ssubset1,2,3,4:na coluna i, casas em r,s têm mesma corr ê
binom42=6 pares r,s no total. Em cada coluna i, se ela tiver k brancas e 4-k pretas, então
|Li| ;=;binomk2+binom4-k2;>=;binom22+binom22=2
Como temos 7 colunas, a soma total das cardinais sumi=1^7|Li|>=7cdot2=14. Pelo princípio da casa dos pombos, ao redistribuir esses “marcadores de pares” em apenas 6 pares possíveis, algum par fixo r,s aparece em pelo menos
llceil 146rrceil ;=;3
dos Li. Ou seja, existem ao menos três colunas i<j<k nas quais as linhas r e s são monócronas (ou seja, ou todas brancas ou todas pretas). Dessas três colunas, duas terão exatamente a mesma cor em (r,s) (duas brancas ou duas pretas). Essas duas colunas e as linhas r,s formam um retângulo cujos quatro vértices são da mesma cor.

Resposta

(a) Para 6times4 basta usar todas as binom42=6 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 7times4 gera, por contagem de pares de linhas monócronas, um par r,s que surge em pelo menos três colunas; dessas, duas terão a mesma cor em r e em s, dando um retângulo todo branco ou todo preto.

Exercícios de Livros Relacionados