Os centros dos 64 quadradinhos de um tabuleiro de xadrez de
estão marcados. Deseja-se cortar o tabuleiro com 13 linhas retas que não passem pelos pontos marcados e de forma tal que cada pedaço de recorte do tabuleiro tenha no máximo um ponto marcado. É possível fazer isso?
Passo 1
Beleza, o enunciado diz: temos os centros dos 64 quadradinhos de um tabuleiro
marcados. Queremos riscar 13 linhas retas (nenhuma passando por um ponto marcado) de modo que cada pedacinho resultante tenha no máximo um desses pontos. Pergunta: é possível?
Conteúdo: geometria combinatória – arranjo de retas e contagem de regiões. Vamos usar a fórmula do número máximo de regiões que linhas em posição geral podem dividir o plano.
Conteúdo: geometria combinatória – arranjo de retas e contagem de regiões. Vamos usar a fórmula do número máximo de regiões que
Passo 2
Teoria: quando você desenha
linhas em posição geral (isto é, nenhuma paralela, nenhum triple‐encontro, e nenhuma linha passando por ponto especial), o número máximo de regiões do plano que elas criam é
Por que?
- Com
- Supondo que com
e resolvendo a recorrência dá a soma dos primeiros
inteiros mais 1.
Passo 3
Aplicando para
:
Passo 4
Isso significa que, no máximo, 13 linhas podem dividir o plano em 92 pedaços. Como queremos isolar 64 pontos (cada pedaço com no máximo um ponto), precisamos de pelo menos 64 pedaços. E 92 ≥ 64, então sobra “capacidade” de pedaços para cada ponto ter o seu.
Resposta
Sim, é possível, porque 13 linhas bem posicionadas podem gerar até 92 regiões e 92 é maior que 64.