[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>
=========================================================================