Ola benedito e demais
colegas desta lista ... OBM-L,
(escreverei sem acentos)
Seja An o conjunto de todos os triangulos cujos lados são numeros
inteiros menores ou iguais a N. Entao, claramente, An-1 esta contido
em An ... Significa isso que - representando por (A) o numero de
elementos do conjunto A - podemos por :
(An) = (An-1) + ( Bn)
onde Bn e o conjunto dos elementos de An que não estao em An-1. E
facil ver que os elementos de Bn são todos os triangulos de An nos
quais ao menos um lado vale N.
Quantos elementos tem Bn ?
Bom, a principio, e facil ver que em Bn esta o triangulo equilatero de
lado N. E igualmente facil perceber que Bn congrega tambem todos os
triangulos isosceles e nao-equilateros nos quais dois de seus lados
valem N, a saber, os triangulos {N,N,1}, {N,N, 2}, ... {N,N,N-1}.
Computando tudo isso temos N triangulos. Portanto :
(Bn)= N + (Cn)
onde Cn e o conjunto de todos os triangulos de An nos quais um, e
somente um, dos lados vale N, a saber, os escalenos cujo maior lado
vale N e os isosceles não equilateros cujos lados iguais são menores
que N. Os triangulos de lados {N,N-1,N-2} e {N,N-1,N-1} são exemplos
validos para esta duas classes.
Quantos são os elementos de Cn ?
Todos os elementos de Cn tem um único lado medindo N e, alem disso,
este lado e o maior lado. Isto implica que se representarmos
genericamente um destes triangulos por {N, A, B}, devera ocorrer :
1)A+B >= N+1, pois devemos ter N < A+B
2)A+B =< 2N-2, pois A < N e B < N
significa isso que os elementos de Cn estao agrupados em classes
disjuntas, nas quais todos os elementos de uma mesma classe tem o
mesmo perimetro. Enumerando os elementos da classe {N,A,B} na qual
A+B=N+1 ate a enumeracao da classe {N,A,B} na qual A+B=2N-2 teremos
totalizado todos os elementos de Cn.
Seja portanto D2p ( indice “2p” ) a classe de triangulos {N, A, B} de
Cn na qual A+B=2p. Temos que 2p=N+1, N+2,..., 2N-2. Fixando uma D2p
qualquer, podemos IMAGINAR que cada elemento desta D2p e uma sequencia
de tres numeros, ordenados da esquerda para a direita, do maior lado
para o menor lado.
Agora, IMAGINE que as sequencias ordenadas descritas acima estao elas
mesmas ordenadas de forma decrescente pelo elemento central ( o
segundo termo de cada 3-sequencia ). O que vemos ?
(N, (N-1)-0, (2p-N+1)+0)
(N, (N-1)-1, (2p-N+2)+1)
(N, (N-3)-2, (2p-N+3)+2)
...
E ate onde podemos descer ? Ate X tal que (N-1)-X >= 2p-(N-1)+X pois
se (N-1)-X < p-(N-1)+X claramente que o triangulo {N,(N-1-X,p-(N-1)+X}
sera igual a algum dos anteriores, já computado. Assim :
X =< (N-1) – p.
Para considerar o valor X=0, fazemos: 1 + X =< N-p. E como 1+X deve
ser inteiro, para não dependermos da paridade de N, colocamos :
(D2p) = 1+X = piso(N – p)
De tudo que vimos chegamos a :
(An) = (An-1) + N + (Dn+1) + (Dn+2) + ... + (D2n-3) + (D2n-2)
o que resolve o problema original formulado pelo Benedito.
Agora, facamos alguns calculos praticos.
N=1 => A1= 1
Obvio, pois apenas o triangulo {1,1,1} atende as condicoes de simetria
do problema.
N=2 => A2= 3
Obvio, pois alem do triangulo {1,1,1} somente os triangulos {2,2,1} e
{2,2,2} interessam.
N=3 => A3 = A2 + 3 + D4 = 3 + 3 + piso(3-2) = 3 + 3 + 1 = 7
Os 4 novos triangulos são {3,3,3}, {3,3,2}, {3,3,1} e {3,2,2}
N=4 => A4=A3 +4+D5+D6 = 7 + 4 + piso(4 - 2,5) + piso(4 - 3)=13
Os 6 novos triangulos são {4,4,4},{4,4,3},{4,4,2},{4,4,1},{4,3,2} e {4,3,3}
Agora, vamos considerar com mais atencao a expressao que fornece o
numero de elementos de D2p:
(D2p)=piso(N - p)
Esta expressao e bonita ? Não sei … O que voces acham ? Eu tenho
minhas duvidas … A funcao “piso” da uma certa assimetria a formula,
tornando-a carrancuda. Ela e decididamente uma mulher com veu, mas eu
vou apostar e continuar esta viagem com ela para ver aonde ela me
conduz … Se ela for bela, ela sera fertil !
Esta formula nos diz quantos triangulos de lados inteiros positivos
tem perimetro p, com as limitacoes :
1)Um unico lado deve valer N
2)N+1 =< 2p =< 2N-2
E se quisessemos encontrar “todos os triangulos de lados inteiros que
tenham perimetro 2p”, independente das limitacoes acima ? Nos temos
elementos suficientes para resolver esta questao diretamente ?
Temos. Eis como :
Se um triangulo de lados inteiros tem perimetro 2p, o maior lado
possivel deve ser L= p -1 se 2p e par; deve ser L=p – 0,5 se 2p e
impar, pois em qualquer triangulo, o maior lado deve ser menor que a
soma dos outros dois. Sintetizamos tudo isso pondo L = piso(p – 0,5).
E o menor maior lado possivel ? E claro que se M e o menor maior lado
possivel deve ocorrer que 3M >= 2p. Assim, o menor maior lado
possivel e o menor M tal que 3M >= 2p => M=teto(2p/3).
Usando a notacao Si{ A,B : f(i) }=f(A) + f(A+1) + … + f(B-1) + f(B)
para representar o somatorio e aplicando a expressao D2p=piso(N-p) aos
resultados acima, chegamos a :
T(2p) = ( L – M + 1) + Si{ M , L : piso( (3i/2) – p ) }
onde M=teto(2p/3), L=piso(p-0,5) e T(2p) e o numero de triangulos com
lados inteiros e perimetro 2p
Este resultado e interessante em si, mas fornece um outro caminho para
se chegar a solucao do problema do Benedito, pois tal problema pode
ser olhado como a
BENEDITO = Si{3,3N : Ti}
Tirei o veu. Eu me rendo : D2p e bonita.
Eu acho que ate aqui esta bom .. antes de encerrar, registro que
gostaria de ver este problema sendo abordado via linha de comando (
não vale escrever um script ou programa ), nos moldes da solucao
apresentada pelo Alessandro Madruga relativa ao problema do numero de
7's em 4444^4444. Não vale usar qualquer das formulas que deduzi
acima.
Finalmente, esta solucao e dedicada aos amigos da notavel comunidade
do Debian/GNU Linux, o Sistema Operacional Universal !
http://www.debian.org/index.pt.html
Um abraco a todos
PSR,61311090D20E
> 2009/10/29 Benedito <b...@ccet.ufrn.br>:
> Problema
> Seja n um número inteiro positivo.
> Encontre o número máximo de triângulos não congruentes cujos lados
> tem comprimentos inteiros menores do que ou iguais a n.
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
