Arquivo mensais:dezembro 2017

Retângulos inteiros

Rookie

Quando eu era mais jovem, fiz uma prova oral de matemática dessas bem difíceis. Preparei-me durante quase dois anos apenas para essa prova, e o resultado foi bom, eu passei. Nela havia duas questões, uma de análise matemática e uma de álgebra linear, que eu nem me lembro direito1. Por sorte eu tinha estudado bem os temas que caíram e acabei, para minha surpresa, acabando a prova antes do tempo. Sem saber o que fazer, o examinador decidiu improvisar. Achando que seria interessante lançar uma “questão extra” para eu começar nos cinco minutos que faltavam, propôs-me um problema que me acompanhou durante esses últimos nove anos. Esse problema, e sua solução mais elegante que conheço, é o post de hoje. Seu enunciado é revoltantemente simples, e eu ainda lembro para que ponto da lousa2 eu olhava quando o ouvi pela primeira vez:

Imagine um grande retângulo composto de pequenos retângulos, como quarteirões de tamanhos variados que compõem um grande bairro retangular. Cada um dos pequenos retângulos tem um lado que é um número inteiro. Prove que o retângulo grande tem pelo menos um lado inteiro.

A solução padrão, aquela que eu mais encontro quando busco pelo problema na internet, envolve usar integrais complexas marotas que contam com o fato de um caminho em volta de cada retângulo ser equivalente a um caminho em volta do retângulo grande, pois os caminhos “internos” dos retângulos menores se compensam. Não vou entrar em detalhes porque, ainda que essa solução seja interessante, e provavelmente era a que o examinador queria, integrais complexas não fazem justiça à revoltante simplicidade desse resultado. Deve haver uma maneira mais intuitiva de provar isso, algo que esteja à altura da intuição que esse enunciado traz. Então vou apresentar a solução que encontrei cuja elegância mais se aproxima daquilo que eu esperava para esse problema, algo que tenha valido a pena esperar nove anos para ver.

Qual o problema desse enunciado? Ele é dado como uma verdade, mas ele não parece dever ser verdade. Eu consigo, em minha inocência e sem papel, imaginar que um retângulo poderia ser formado de pequenos retângulos com apenas um lado inteiro cada e, com um arranjo inteligente, ter dois lados que são frações, ou números irracionais. Mas o fato de o resultado ser verdade implica que eu terei um problema tentando fechar o retângulo. É um exercício fascinante que eu recomendo para entender de onde ver a intuição da solução que vou apresentar: tente compor um grande retângulo usando pequenos, desenhe livremente, apenas impondo que os retângulos internos tenham ao menos um lado inteiro. Invariavelmente você será confrontado com o problema de fechar o retângulo, e uma de duas opções será verdadeira: ou o retângulo que fecha o grande retângulo não terá um lado inteiro, ou o grande retângulo terá um lado inteiro.

A partir dessa intuição, vamos resolver esse problema. O melhor jeito de explorar essa questão de fechar o retângulo é de colocar todo o problema em um tabuleiro de xadrez 1/2 x 1/2. Algo mais ou menos assim:

E coloquemos também uma representação de nosso grande retângulo, com pequenos retângulos desenhados dentro apenas para referência (eu não desenhei isso em escala).

Nosso objetivo é provar que, se os retângulos internos têm todos ao menos um lado inteiro, então ou a ou b são inteiros. Vamos colocar isso no tabuleiro para ter algumas ideias.

O primeiro resultado importante que devemos listar aqui é o teorema fácil de ver: se um retângulo tem um lado inteiro, ele cobre uma área que é 50% branca e 50% preta. Ora, se um lado dele é um inteiro p, ele passa por p quadrados pretos e p quadrados brancos. Ainda que ele não comece exatamente na quina entre os quadrados, ele sempre atravessa a mesma quantidade de pretos e brancos naquele lado e, logo, pouco importa o quanto aumentamos ele do lado que não é inteiro, ele é obrigado a cobrir a mesma área de pretos e de brancos.

Cada um dos pequenos retângulos satisfaz o teorema acima, então cada um deles cobre a mesma área preta e branca. Visto que a área coberta pelo retângulo grande é a soma das áreas dos pequenos, o retângulo grande cobre a mesma quantidade de área preta e branca, pois cada uma de suas parcelas satisfaz essa propriedade.

É claro que isso não basta. Provei que todo retângulo de lado inteiro cobre pretos e brancos igualmente, mas preciso provar a volta, preciso provar que todo retângulo que cobre a mesma área de pretos e brancos tem ao menos um lado inteiro. Para isso, vamos provar por absurdo. Suponha que o retângulo grande não tem um lado inteiro. Então posso cortar o grande retângulo em quatro outros retângulos.

Este símbolo \lfloor a \rfloor significa “parte inteira de a”, ou seja, arredondar o número a para o baixo até encontrar um número inteiro. Por exemplo: \lfloor 2.1\rfloor=2. Minha ideia foi de quebrar o grande retângulo em um retângulo maior com os dois lados inteiros (o laranja), dois retângulos médios com pelo menos um lado inteiro (os vermelhos) e um pequeno retângulo com o que sobrou (o verde). Note que se o grande retângulo inicial não tem nenhum lado inteiro (nossa hipótese), o verde também não tem nenhum lado inteiro, porque os lados dele são “a parte que não é inteira” de a e b. Se os lados do retângulo original fossem 2.5 e 3.6, os lados do retângulo verde seriam 0.5 e 0.6.

O retângulo laranja tem ao menos um lado inteiro (tem dois!), então cobre a mesma proporção de pretos e brancos. Os vermelhos também têm ao menos um lado inteiro, então também cobrem a mesma área de pretos e brancos. E agora vem o elemento chave, e aquele que usa o fato dos retângulos menores terem um lado inteiro: como eu sei que a soma desses quatro retângulos cobre a mesma área preta e branca, e como três deles também cobrem, o menor deles, o verde, deve obrigatoriamente cobrir a mesma proporção de área preta e branca.

Eu pareço apenas ter empurrado o problema com a barriga: antes queria provar que o grande retângulo cobrir a mesma área preta e branca implica ter lado inteiro, agora quero provar que um retângulo pequenino faz isso, parece trocar seis por meia dúzia. Mas há  uma diferença fundamental entre o retângulo verde e o grande retângulo: o retângulo verde começa em uma quina e é necessariamente menor que um quadrado 1×1.

E por que isso é importante? Tente desenhar um retângulo dentro de um quadrado 1×1 que cubra a mesma área de pretos e brancos. Sem muito esforço, você perceberá que só existem duas opções:

Ou ele é inteiro na horizontal e x na vertical, ou ele é inteiro na vertical e cobre x na horizontal. É impossível criar um retângulo de dimensões x, y < 1 começando na origem que cubra a mesma proporção de pretos e brancos!  Mas, por definição, o retângulo verde não possui nenhum lado inteiro, caímos em contradição! Como retângulo grande cobre a mesma área de pretos e brancos, o verde deve cobrir também, e a única maneira de isso acontecer, visto que ele está confinado no quadrado 1×1, é tendo um lado inteiro. Assim, o retângulo grande deve necessariamente ter um lado inteiro.

E o que eu fiz quando me apresentaram a pergunta, quando essa era minha questão final na prova oral? É evidente que entrei em pânico, ainda que tenha mantido a compostura. Meu cérebro correu toda a matemática que conhecia e eu não tinha a mais vaga ideia de nem por onde começar. Com cara de jogador de poker, esbocei um retângulo na lousa, escrevi dimensões a e b e fingi pensar um pouco. Porque o examinador percebeu meu pânico, ou por pura misericórdia divina, ele olhou o relógio e disse: “Ah, infelizmente temos apenas cinco minutos, acho que não vai dar para resolver.”. De fato, não dava em cinco minutos. Tivesse eu mais nove anos, quem sabe não apresentaria uma solução mais elegante.

  1. Aos curiosos, a de análise era para provar a convergência de uma série de funções, dessas de provar que convergência de gente absolutamente contínua, e a de álgebra linear era para provar em que condições uma dada matriz 2×2 era diagonalizável, coisa fácil. []
  2. Superior esquerdo. []