*29. Um ponto reticulado no plano é um ponto
em que
e
são números inteiros. Use a indução matemática para mostrar que pelo menos
linhas retas são necessárias para garantir que todo ponto reticulado
,
e
pertencem a essas linhas retas.
Passo 1
O enunciado nos dá o conjunto de pontos reticulados
e pede para mostrar, por indução em
, que qualquer cobertura de
por linhas retas requer pelo menos
linhas.
Passo 2
Base da indução
.
Nesse caso
Nesse caso
e para cobrir o ponto
é necessária no mínimo uma linha. Logo vale que precisamos de
linha.
Passo 3
Hipótese de indução.
Suponha que para algum toda cobertura de
Suponha que para algum
use pelo menos
linhas.
Passo 4
Passo indutivo
.
Considere e suponha que
linhas
cubram todos os pontos de
. Definamos a “diagonal superior”
Considere
que tem exatamente
pontos
. Há dois casos:
(I) Uma das linhas
coincide com
.
Então essa linha já cobre todos os pontos de
, e as outras
linhas devem cobrir
Então essa linha já cobre todos os
Pela hipótese de indução precisamos de
, ou seja,
.
(II) Nenhuma das
coincide com
.
Nesse caso cada linha não paralela a intersecta
em no máximo um ponto, e cada linha paralela a
não atinge nenhum ponto de
. Para cobrir os
pontos de
são então necessárias pelo menos
linhas, isto é,
.
Nesse caso cada linha não paralela a
Em ambos os cenários obtemos
.
Resposta
Pelo menos
linhas retas são necessárias para cobrir todos os pontos de
.