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