[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] Re: [obm-l] tri�ngulos
Ola Rafael e demais
colegas desta lista,
O problema a que voce se refere ja foi proposto ( pelo Grande e Saudoso
amigo Bruno Leite ) e resolvido aqui na lista. Segue abaixo a solucao
apresentada :
Caro Bruno,
Saudacoes !
Antes de abordarmos propriamente a questao que voce propos considero
importante, para uma maior claridade na exposicao, fixar a notacao que
usaremos. Assim, representaremos por :
{ N/R } o numero binomial de numerador N e denominador P, vale dizer:
{ N/P } = (N!)/(P! (N-P)!); Se N < R, { N/R } = 0
Si[1,R] F(i) o somatorio de F(i), "i" variando de 1 ate R.
A solucao que obteremos esta dividida em duas partes. Na primeira, que
representaremos por A(n), estarao computados todos os triangulos equilateros
com vertice para cima. O total de triangulos com vertices para baixo sera
representado por V(n). Nas duas funcoes "n" representa o comprimento do lado
do triangulo inicial.
Seja ABC um tringulo equilatero de lado "n" imaginado como se BC fosse a
base e A o vertice. Entre A e B, no sentido de A para B, inserimos N-1
pontos D1, D2, ..., Dn-1 de forma que o lado AB fique dividido em N partes
iguais, Por estes pontos tracamos N-1 paralelas a BC que interceptarao AC
respectivamente nos pontos E1, E2, ..., En-1, Chamaremos de "base i" ao
segmento DiEi. A base BC sera referenciado com "a base n".
O total de triangulos equilateros com lado unitario e vertice para cima, que
representaremos por T1, e facilmente computavel. Com efeito, sobre a base 1
( D1E1) cabe um triangulo; sobre a base 2 cabem dois triangulos; sobre a
base tres cabem tres triangulos ... sobre a base N cabem N triangulos. Isto
e :
T1 = 1 + 2 + 3 + ... + N = (N(N+1))/2 = { N+1/2 }
O total de triangiulos equilateros com lado igual a 2 e vertice para cima (
T2 ) segue a mesma logica: sobre a base 2 ( D2E2 )cabe um triangulo; sobre a
base 3 cabem dois triangulos; ...; sobre a base N cabem N-1 triangulos. Isto
e:
T2 = 1 + 2 + 3 + ... + (N-1) = ((N-1)N)/2 = { N/2 }
No caso dos triangulos com lado 3 :
T3 = 1 + 2 + 3 + ,,, + (N-2) = ((N-2)(N-1))/2 = { N-1/2 }
E assim sucessivamente ... O que queremos e calcular T1 + T2 + ,,, + Tn.
Ficara :
T1+T2+T3+...+Tn={ N+1/2 }+{ N/2 }+{ N-1/2 }+...+{ 2/2 }={ N+2/3 }
Portanto, o total de triangulos com vertices para cima, que convencionamos
chamar A(n) e que e a primeira parte de nossa formula, e:
A(n) = { N+2/3 }
Precisamos agora calcular V(n), o total de triangulos equilateros com
vertice para baixo.
Seja P=[ N/2 ] "o maior inteiro que n�o supera N/2". Observe que se N for
par, entao P=N/2. Se N for impar, P = (N-1)/2.
A expressao E = N/2 - P = N/2 - [N/2], assume o valor zero se N e par.
Se N for impar, E = 1/2 ( um meio )
Observe que num triangulo equilatero qualquer P e o lado do maior triangulo
com vertice para baixo que cabe neste triangulo
Quantos triangulo equilateros com lado P cabem no triangulo equilagtero com
lado N ? 1 (sobre a base P=DpEp), se N e par ; 1+2 se P for impar ( 1 sobre
a base P=DpEp e 2 sobre a base P+1=Dp+1Ep+1). E se o lado do triangulo for
"P-1" ? 1 + 2 + 3 se N for par; 1+2+3+4 se N for impar.
Esse "valor a mais" que o triangulo de lado impar tem chamarei de "Excesso"
e representarei por E(p). Assim, um triangulo de lado impar K pode ser
pensado como um de lado par "K-1" mais um Excesso E(k)
Assim, sendo P=[N/2], "o maior inteiro que n�o supera N/2", fica :
1 ( Lado P) => se N e par: 1 ; se N e impar: 1+2 ( aqui E(1) = 2 )
2 (Lado P-1) => se N e par: 1+2+3 ; se N e impar: 1+2+3+4
( aqui E(2) = 4 )
3 (Lado P-2) => : se N e par: 1+2+3+4+5; se N e impar: 1+2+3+4+5+6
( aqui E(3) = 6)
................
P (Lado 1) => se N e par: 1+2+...+(2P-1); se N e impar: 1+2+...+(2P-1)+2P
( aqui E(p) = 2P )
Assim, se N e par n�o somamos o excesso. Se N e impar, somamos. Ora, a
expressao E = ( N/2 - [N/2] ) = ( N/2 - P ) tem essas caracteristicas, sendo
zero par N par e 1/2 para N impar. Logo, representando por S(n) =
1+2+3+...+N, tudo que obtivemos acima pode ser expresso por :
K ( lado P-k+1) => 1+2+3+...+(2K-1) + 4K(N/2 - P), independente de N ser
par ou impar !!!!!!!!!!
A expressao de V(n), que representa todos os triangulos equilateros com
vertice para baixo, sera:
V(n) = S(1) + S(3) + S(5) + ... + S(2P-1) + 4(1+2+...+P)(N/2 - P)
V(n) = S(1)+S(3)+S(5)+...+S(2p-1) + 4{ P+1/2 }( N/2 - P )
V(n) = { P/1 }*S(1) + { P/2 }*(S(3)-S(1)) + { P/3 }*(S(5) - 2S(3) + S(1)) +
4*{ P+1/2 }*(N/2 - P)
Mas S(1) = 1, S(3) = 6 e S(5) = 15. Logo
V(n) = { P/1 } + 5{ P/2 } + 4{ P/3 } + 4{ P+1/2 }( N/2 - P )
Nesta ultima expressao, conforme j� dissemos, { N/R } representa o numero
binomial (N!)/(P!(N-P)!) com { N/R } = 0 se N < R. N e o comprimento do lado
do triangulo equilatero e P=[N/2] e o maior inteiro que n�o supera N/2.
A expressao final que voce procura e A(n) + V(n), que chamaremos de
T(n). Portanto :
T(N)={ N+2/3 }+{ P/1 }+ 5*{ P/2 }+ 4*{ P/3 }+ 4*{ P+1/2 }*( N/2 - P )
Independente de N ser par ou impar !
E SEM PRECISAR USAR DUAS FORMULAS !
Finalmente, n�o sei se voce percebeu que um quadrado de lado N tambem
permite enunciar uma questao semelhante. Neste figura n�o h� quadrado
menores invertidos, visto que a inversao de um quadrado gera um outro
identico ao primeiro, mas h� uma gama enorme de "quadrados inclinados" e eu
j� calculei que um raciocinio semelhante ao que desenvolvemos acima permite
solucionar esta questao. Voce gostaria de tentar
resolve-la ?
>From: "Bruno Leite" <superbr@hotmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Problema horroroso
>Date: Sun, 26 Sep 1999 10:58:34 PDT
>
>Seja f(n) o n�mero de tri�ngulos equil�teros (0<i<=n)que est�o contidos num
>tri�ngulo equil�tero de lado n (num triangulado, digamos)
>
>Ex: f(1)=1 pois num tri�ngulo eq. de lado 1 h� apenas um tri�ngulo.
> f(2)=5 pois num tr.eq. de lado 2 h� um triangulo de ponta cabe�a, tr�s
>tr. de lado 1 "certos" e um grand�o.
> f(3)=13 pois temos 9 pequenos, 3 m�dios e um grande.
> f(4)=27 etc
> /\
> /\/\
> /\/\/\
>/\/\/\/\
>
>
>A figura ilustra o caso n=4 (� preciso fingir que h� tamb�m as divis�es
>horizontais, formando uma malha triangular.)
>
>� f�cil ver que h�:
>16 tri�ngulos do tipo /\ ou \/ (lado 1)
>7 tri�ngulos de lado 2 (6 /\ e 1 \ /)
> / \ \/
>3 tri�ngulos lado 3 e
>1 de lado 4.
>
>
>Pede-se f(n) em fun��o de n (f�rmula expl�cita)
>Eu comecei a estudar esse problema h� 2 anos mas sempre desisti por falta
>de resultados. J� achei v�rias rela��es mas n�o acho a f�rmula geral.
>Gostaria MUITO que algu�m falasse como se faz.
>
>Se algu�m que se interessou n�o entender o enunciado muito bem, eu fa�o
>umas figuras explicativas para ajudar.
>
>Bruno Leite
>
>From: Rafael WC <rwcinoto@yahoo.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: OBM <obm-l@mat.puc-rio.br>
>Subject: [obm-l] tri�ngulos
>Date: Sat, 18 May 2002 18:43:46 -0700 (PDT)
>
>Pessoal, ontem mandei uma d�vida sobre contar o total
>de tri�ngulos de todos os tamanhos de uma figura como
>a que enviei abaixo novamente. Pensei muito sobre esse
>problema e cheguei a uma f�rmula n�o muito amig�vel,
>mas at� que n�o � ruim. J� d� at� pra escrever um
>algoritmo pra rodar no computador se quiser.
>
>Primeiro, eu chamei de x o n�mero de lados de
>tri�ngulos que temos na base. Por exemplo, se tivermos
>um tri�ngulo s� x = 1.
>/_\
>
>Se tivermos uma figura com quatro tri�ngulos de menor
>tamanho, temos:
> /_\
>/_\ /_\
>
>x = 2
>
>Na figura que mandei, temos x = 4.
>
>Com isso, j� que voc� tem tri�ngulos de diferentes
>tamanhos, voc� deve contar separadamente os tri�ngulos
>que t�m como lado 1 tra�o, 2 tra�os, 3 tra�os...E
>depois tem que contar os tri�ngulos que est�o de
>cabe�a pra baixo com esses mesmos tamanhos.
>
>Se voc� fizer isso em fun��o dos tra�os da base n�o
>fica muito ruim. Todas as linhas vou escrever a soma
>de v�rias parcelas de x menos alguma coisa. Quando
>voc� for calcular para algum x, voc� vai fazer as
>subtra��es at� encontrar o valor zero, a� voc� para.
>Por exemplo, na primeira linha temos:
>x + (x - 1) + (x - 2) + (x - 3) + ...
>
>Se voc� tiver x = 2, voc� ir� somar at� x + (x - 1),
>porque o pr�ximo dar� zero e a� voc� deve parar.
>
>Bom, no final voc� encontra isso:
>tri�ngulos de lado 1:
>cabe�a pra cima = x + (x - 1) + (x - 2) + (x - 3) +
>...
>cabe�a pra baixo = (x - 1) + (x - 2) + (x - 3) + ...
>total = x + 2.[(x - 1) + (x - 2) + (x - 3) + ...]
>� como se o tri�ngulo maior de todos fosse dividido em
>v�rias linhas, a� voc� vai contando de cada linha.
>
>tri�ngulos de lado 2:
>cabe�a pra cima = (x - 1) + (x - 2) + (x - 3) + (x -
>4) + ...
>cabe�a pra baixo = (x - 3) + (x - 4) + (x - 5) + ...
>total = (x - 1) + (x - 2) + 2.[(x - 3) + (x - 4) +
>...]
>
>Por que aqui come�amos a ter de cabe�a pra baixo s�
>com (x - 3)? Porque para termos um tri�ngulo de cabe�a
>pra baixo, o tri�ngulo maior tem que ter o dobro de
>tra�os na base do que o tamanho do tri�ngulo. Como
>esse tem lado 2, precisamos ter x = 4, que se fizermos
>(x - 3) dar� 1. Enquanto x for menor que 4 esse n�mero
>ser� negativo ou zero e a� n�o vamos contar.
>
>tri�ngulos de lado 3:
>cabe�a pra cima = (x - 2) + (x - 3) + (x - 4) + (x -
>5) + ...
>cabe�a pra baixo = (x - 5) + (x - 6) + (x - 7) + ...
>total = (x - 2) + (x - 3) + (x - 4) + 2.[(x - 5) +
>...]
>
>E assim teremos sempre esse padr�o. Os tri�ngulos de
>cabe�a pra cima come�am sempre com (x - a), onde "a" �
>o n�mero anterior ao tamanho do tri�ngulo. E os
>tri�ngulos de cabe�a pra baixo come�am sempre com x -
>(2a - 1). Depois os outros termos voc� vai tirando
>sempre 1.
>
>No final das contas voc� pode somar tudo isso. Soma os
>tri�ngulo de cabe�a pra cima com os de cabe�a pra
>baixo de todos os tamanhos. O problema � que n�o pode
>desenvolver muita coisa, porque n�o pode misturar x -
>3 com x - 4, porque se voc� tiver x = 4, voc� n�o ter�
>o termo x - 4. Mas somando apenas x - 1 com x - 1 e x
>- 2 com x -2, voc� ter�:
>total = x + 3.(x - 1) + 4.(x - 2) + 6.(x - 3) + 7.(x -
>4) + 9.(x - 5) + 10.(x - 6) + 12.(x - 7) + 13.(x - 8)
>+ ...
>
>No final voc� tem ent�o todos os fatores x, x - 1, x -
>2, x - 3, ... e os coeficientes de cada um t�m uma
>ordem at� boazinha:
>1, (pula o 2), 3, 4, (pula o 5), 6, 7, (pula o 8), 9,
>10, (pula o 11), 12, 13, (pula o 14), ...
>
>E voc� vai usar a f�rmula at� o termo em que quando
>fizer a diferen�a de x com alguma coisa d� zero. Ou
>voc� pode at� fazer a seguinte regra: considere que
>desse valor total voc� vai pegar apenas os x primeiros
>termos.
>
>Por exemplo, vamos pegar o tri�ngulo da figura que tem
>4 tra�os na base, ou seja x = 4. Ent�o vamos pegar at�
>o quarto termo dessa f�rmula e fazer x = 4:
>total = x + 3.(x - 1) + 4.(x - 2) + 6.(x - 3)
>total = 4 + 3.(4 - 1) + 4.(4 - 2) + 6.(4 - 3)
>total = 4 + 3.3 + 4.2 + 6.1
>total = 4 + 9 + 8 + 6
>total = 27
>
>E a� voc� pode fazer pra qualquer x. Aquele menor que
>tinha x = 2, s� pegamos os 2 primeiros termos:
>total = x + 3.(x - 1)
>total = 2 + 3.(2 - 1)
>total = 2 + 3.1
>total = 2 + 3
>total = 5
>
>De qualquer jeito voc� n�o precisa ficar contando um
>por um e correr o risco de se perder mais facilmente.
>
>Mas o meu problema agora � o seguinte. Suspeito que
>ainda d� para simplificar a f�rmula, considerando duas
>f�rmulas, uma para quando x � par e outra para quando
>x � �mpar. Talvez simplifique, mas a� voc� tem duas
>f�rmulas, n�o sei. Ainda n�o consegui.
>
>Ser� que algu�m consegue melhorar daqui pra frente. O
>pior acho que j� passou.
>
>Um abra�o,
>
>Rafael.
>
>=====
>Rafael Werneck Cinoto
> ICQ# 107011599
> rwcinoto@yahoo.com
> rafael.caixa@gov.com.br
> matduvidas@yahoo.com.br
>http://www.rwcinoto.hpg.com.br/
>
>__________________________________________________
>Do You Yahoo!?
>LAUNCH - Your Yahoo! Music Experience
>http://launch.yahoo.com
><< contatriang.gif >>
_________________________________________________________________
Converse com amigos on-line, conhe�a o MSN Messenger:
http://messenger.msn.com
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista � <nicolau@mat.puc-rio.br>
=========================================================================