|
No primeiro, a maior dificuldade é determinar qual
a posição e dimensões de cada retângulo adicionado a fim de maximizar o número
de sub-divisões obtidas.
*************
O segundo é um pouco mais fácil:
Supondo que são desenhadas retas (ao invés de
segmentos) temos o seguinte:
1 reta ==> A(1) = 2 áreas distintas
2 retas ==> A(2) = 4 áreas
distintas
3 retas ==> A(3) = 7 áreas
distintas
Cada reta adicionada deve interceptar todas as
outras já existentes de modo que no máximo duas retas se encontrem em cada ponto
do plano. Isso significa que esta nova reta interceptará n-1 retas e, portanto,
passará por (n-1) + 1 = n regiões, dividindo cada uma delas em duas novas
regiões. Ou seja, a n-ésima reta criará n noves regiões.
Teremos, portanto, a recorrência: A(n) = A(n-1) + n, cuja solução pode ser obtida da seguinte
forma:
A(1) = 1 + 1
A(2) = A(1) + 2
A(3) = A(2) + 3
....
A(n-1) = A(n-2) + (n-1)
A(n) = A(n-1) + n
Somando estas n equações e cancelando os termos
comuns (técnica normalmente conhecida como "telescopagem"),
obtemos:
A(n) = 1 + (1 + 2 + ... + n) = 1 + n*(n+1)/2 = (n^2
+ n + 2)/2
A(n) = 1597 ==>
(n^2 + n + 2)/2 = 1597 ==>
n^2 + n - 3192 = 0 ==>
n = 56 ou n = -57 ==> (desprezando a
raiz negativa)
n = 56 retas.
****************
O terceiro apresenta a mesma dificuldade que o
primeiro. Acho que o principal requisito é que no máximo duas arestas de
triângulos distintos se interceptem em cada ponto do plano (e naturalmente, que
cada ponto seja vértice de no máximo 1 triângulo).
Por exemplo:
A(1) = 2 (o interior e o exterior do
triângulo)
A(2) = 8 (figura homeomorfa a uma estrela de
David)
A(3) = 20 (cada lado do 3o. triângulo intercepta
duas arestas de cada um dos dois primeiros e cria 3 novas regiões
juntamente com os dois primeiros triângulos (portanto, total de 9). Além disso,
o 3o. triângulo cria mais 3 novas regiões, cada uma das quais tem um vértice em
comum com ele - logo: 9 + 3 = 12 novas regiões ==> Total = 8 + 12 =
20).
Sem fazer uma figura fica difícil visualizar. De
qualquer forma, a recorrência é bem menos óbvia.
Um abraço,
Claudio.
|