Contando quadrados e retângulos

Fonte.

Quantos quadrados há em um tabuleiro de xadrez? E mais: dado um jardim retangular, quantos retângulos ou quadrados menores podemos reservar para decorações?

Embora pareçam questões triviais de contagem, é possível fazer uma exploração aprofundada e descobrir modos bem elegantes de resolvê-las.

Pré-requisitos

Como vamos falar de problemas de contagem, recomendo um domínio básico de análise combinatória. Você pode encontrar uma rápida introdução aqui.

Quadrados dentro de quadrados

Quantos quadrados há em um tabuleiro de xadrez 8x8? Ou seja, quantos quadrados 1x1, 2x2, ..., 8x8 existem?

Como somos muito sofisticados, não vamos nos sujeitar a contar diretamente um por um. Ao invés disso, podemos notar uma coisa interessante. Como exemplo, vamos pegar um quadrado 3x3 qualquer e tentar movê-lo pelo tabuleiro. O máximo possível que conseguimos deslocá-lo à direita é a este ponto:

Onde o canto superior esquerdo, marcado, ocupa a 6ª coluna. Claro, se fosse a 7ª ou 8ª coluna, partes do quadrado estariam fora do tabuleiro. Generalizando, um quadrado de lado l pode ocupar no máximo a coluna (9 - l). O mesmo raciocínio aplica-se à vertical:

Onde o canto superior esquerdo ocupa a 6ª fileira. Novamente, um quadrado de lado l pode ocupar no máximo a fileira (9 - l). Portanto, para cada quadrado de tamanho l, basta calcular de quantos modos podemos colocar o canto superior esquerdo: há (9 - l) possibilidades para sua posição horizontal e (9 - l) possibilidades para sua posição vertical. Ou seja, (9 - l)² possibilidades no total. Prosseguimos para cada quadrado:

- 8x8: (9 - 8)² = 1
- 7x7: (9 - 7)² = 4
- 6x6: (9 - 6)² = 9
- 5x5: (9 - 5)² = 16
- 4x4: (9 - 4)² = 25
- 3x3: (9 - 3)² = 36
- 2x2: (9 - 2)² = 49
- 1x1: (9 - 1)² = 64
- Total: 204

Estranhamente, calcular quantos quadrados há no tabuleiro é equivalente a somar os 8 primeiros quadrados perfeitos!

Será coincidência? Há uma maneira mais intuitiva de abordar o problema?

Soma dos n primeiros quadrados perfeitos

Vamos tentar montar o tabuleiro do zero a partir dos quadrados perfeitos. Ok, do zero não, começando por 1²:

Agora "somando" com 2²:

Temos 4 quadrados 1x1 e um quadrado 2x2, 5 quadrados no total. De fato, isso corresponde a 1² + 2². Prosseguindo para 3x3:

Com isso, temos 1² + 2² + 3² = 14 quadrados no total. Deu para ver onde queremos chegar, certo? Somar os n primeiros quadrados perfeitos é a mesma coisa que montar um quadrado nxn. Quando enfim acoplarmos o 8º quadrado, teremos o tabuleiro original:

Ou seja, 1² + 2² + ... + 8² quadrados no total. Fica faltando apenas uma maneira mais rápida de realizar o cálculo, uma fórmula prática. De fato, a soma S dos quadrados dos n primeiros inteiros positivos (ou seja, os n primeiros quadrados perfeitos) é:

$$ S = \frac{2n^3 + 3n^2 + n}{6} $$

Há várias e várias demonstrações da fórmula, algumas das quais podem ser vistas aqui.

Retângulos dentro de retângulos

Em quantas regiões retangulares podemos dividir um terreno retangular 3x2?

Primeiro, vamos desenhar o retângulo maior e separá-lo em unidades. Marcamos também os pontos presentes nos cantos dos pequenos quadrados que dividem o retângulo:

Para determinar um retângulo, basta uma linha horizontal e uma linha vertical; as outras duas linhas saem automaticamente. Verificamos que:

- Uma linha horizontal é determinada por um ponto inicial e um ponto final. Como há 4 pontos na horizontal, temos um total de \(C^4_2\) combinações possíveis.

- Similarmente, uma linha vertical é determinada por um ponto inicial e um ponto final. Há 3 pontos disponíveis, e portanto \(C^3_2\) combinações possíveis.

Daí, basta usar o princípio multiplicativo para encontrar \(C^4_2 \times C^3_2 = 18\) possibilidades de construir um retângulo. Generalizando: em um retângulo mxn, temos \(C^{m + 1}_2 \times C^{n + 1}_2\) retângulos no total.

Quadrados dentro de retângulos

Em quantas regiões quadradas podemos dividir um terreno retangular 5x3?

Ainda não sabemos calcular quantos quadrados há dentro de um retângulo, mas se for um quadrado sim. Como 5 > 3, imaginemos primeiramente um quadrado 3x3. Sabe-se que a quantidade de quadrados é dada por \(\frac{2n^3 + 3n^2 + n}{6}\), ou 1² + 2² + 3², resultando em 14 quadrados.

Agora, aumentemos por um o comprimento do quadrado. Assim, obtém-se um retângulo 4x3:

Nota a região marcada? São os novos quadrados 1x1 adicionados com o aumento do comprimento; mais especificamente, foram 3 novos quadrados. Além dos quadrados, foram acrescentados 4 novos pontos. Para cada novo par de pontos, há um novo quadrado (afinal, um quadrado é determinado por um lado, por sua vez determinado por dois pontos). Portanto, há \(C^4_2 = 6\) novos quadrados.

Aumentamos o comprimento novamente e chegamos a um retângulo 5x3. Novamente, temos 3 novos quadrados e consequentemente 4 novos pontos. Também há \(C^4_2 = 6\) novos quadrados.

Portanto, a resposta final é 14 + 6 + 6 = 26 regiões quadradas, mas poderíamos continuar somando 6 se o comprimento fosse maior do que 5. De modo geral, a quantidade de quadrados em uma região retangular mxn, com m > n, é:

$$ \frac{2n^3 + 3n^2 + n}{6} + (m - n) C^{n + 1}{2} $$

Claro que o mesmo raciocínio é válido quando n > m, daí:

$$ \frac{2m^3 + 3m^2 + m}{6} + (n - m) C^{m + 1}{2} $$

Fontes

Counting Rectangles
Soma dos quadrados dos primeiros n números inteiros positivos
Square pyramidal number - Wikipedia