*29. Um ponto reticulado no plano é um ponto (x, y) em que x e y são números inteiros. Use a indução matemática para mostrar que pelo menos n+1 linhas retas são necessárias para garantir que todo ponto reticulado (x, y) \operatorname{com} x \geq 0, y \geq 0 e x+y \leq n pertencem a essas linhas retas.

Passo 1

O enunciado nos dá o conjunto de pontos reticulados
S_n = \{(x,y)\in\mathbb{Z}^2 \mid x\ge0,\;y\ge0,\;x+y\le n\}
e pede para mostrar, por indução em n, que qualquer cobertura de S_n por linhas retas requer pelo menos n+1 linhas.

Passo 2

Base da indução n=0.
Nesse caso
S_0 = \{(0,0)\},
e para cobrir o ponto (0,0) é necessária no mínimo uma linha. Logo vale que precisamos de 0+1=1 linha.

Passo 3

Hipótese de indução.
Suponha que para algum n-1\ge0 toda cobertura de
S_{n-1} = \{(x,y)\in\mathbb{Z}^2 \mid x\ge0,\;y\ge0,\;x+y\le n-1\}
use pelo menos n linhas.

Passo 4

Passo indutivo n-1\to n.
Considere S_n e suponha que k linhas \ell_1,\dots,\ell_k cubram todos os pontos de S_n. Definamos a “diagonal superior”
D=\{(x,y)\in\mathbb{Z}^2\mid x\ge0,\;y\ge0,\;x+y=n\},
que tem exatamente n+1 pontos (0,n),(1,n-1),\dots,(n,0). Há dois casos:
(I) Uma das linhas \ell_i coincide com D.
Então essa linha já cobre todos os n+1 pontos de D, e as outras k-1 linhas devem cobrir
S_n\setminus D = S_{n-1}.
Pela hipótese de indução precisamos de k-1\ge n, ou seja, k\ge n+1.
(II) Nenhuma das \ell_i coincide com D.
Nesse caso cada linha não paralela a D intersecta D em no máximo um ponto, e cada linha paralela a D não atinge nenhum ponto de D. Para cobrir os n+1 pontos de D são então necessárias pelo menos n+1 linhas, isto é, k\ge n+1.
Em ambos os cenários obtemos k\ge n+1.

Resposta

Pelo menos n+1 linhas retas são necessárias para cobrir todos os pontos de S_n.

Exercícios de Livros Relacionados