[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Quadrados em um Quadriculado.
Ola Claudio e demais
colegas desta lista ... OBM,
Resposta correta ! A percepcao que mata a questao e ver que num "quadrado
normal" de lado i cabem exatamente (i-1) "Quadrados inclinados". Assim, ser
QN(i) for o toal de quadrados de lados i, entao (i-1)*QN(i) e o total de
quadrados inclinados associados aos quadrados normais de lado i :
T(i)= QN(i) + (i-1)*QN(i) = i*QN(i)
Total de quadrados : somatorio de i*QN(i), i variando de 1 ate N. Como
claramente QN(i)=(N-i+1)^2, segue que :
Total de quadrados (T) : somatorio de i*(N-i+1)^2.
Vou colocar este somatorio de forma que ele seja conveniente para voce
responder o item 2.
T= somatorio de (i*(N-i+1)^2), i variando de 1 ate N.
T= 1*N^2 + 2*(N-1)^2 + 3*(N-2)^2 + ... + (N-1)*2^2 + N*(1^2)
T=
N^2 + (N-1)^2 + (N-2)^2 + (N-3)^2 + ... + 3^2 + 2^2 + 1^2
+ (N-1)^2 + (N-2)^2 + (N-3)^2 + ... + 3^2 + 2^2 + 1^2
+ (N-2)^2 + (N-3)^2 + ... + 3^2 + 2^2 + 1~2
+ (N-3)^2 + ... + 3^2 + 2^2 + 1^2
... ... ...
+ 3^3 + 2^2 + 1^2
+ 2^2 + 1^2
+ 1^2
A primeira linha e a soma dos N primeiros quadrados, que da :
BI(N,1) + 3*BI(N,2) + 2*BI(N,3)
A segunda linha e a soma dos N-1 primeiros qudrados, que da :
BI(N-1,1) + 3*BI(N-1,2) + 2*BI(N-1,3)
A terceira linha e a soma dos N-2 primeiros quadrados, que da :
BI(N-2,1) + 3*BI(N-2,2) + 2*BI(N-2,3)
e assim sucessivamente ... Vemos claramente que temos 3 colunas do triangulo
de Pascal. Podemos, pois, aplicar o teorema das colunas. Portanto, o
somatorio fica :
T=BI(N+1,2) + 3*BI(N+1,3) + 2*BI(N+1,4)
T=(BI(N+1,2) + BI(N+1,3)) + 2*(BI(N+1,3) + BI(N+1,4))
T=BI(N+2,3) + 2*BI(N+2,4)
T=(BI(N+2,3) + BI(N+2,4)) + BI(N+2,4)
T=BI(N+3,4) + BI(N+2,4) = BI(N+2,4) + BI(N+3,4)
T = BI(N+2,4) + BI(N+3,4)
Que grata surpresa ! Encontramos uma expressao ao mesmo tempo bela e simples
! Mais que isso : sao dois termos consecutivos da quinta coluna do triangulo
de Pascal. Como diria Goeth - "Sorvei, olhos meus, o que vos der a vida ...
A copiosa beleza no Universo difundida !" -, a beleza e realmente irma da
simplicidade ...
Agora e facil, certo ? Existem dois termos consecutivos da quinta coluna do
triangulo de Pascal cuja soma e uma potencia de 10 ?
Oportunamente eu vou falar sobre "combinacoes lineares" de numeros binomias.
E uma terra prenhe de tesouros poucos explorados ...
Um Abraco
Paulo Santa Rita
6,1836,310103
>From: "Cláudio \(Prática\)" <claudio@praticacorretora.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: <obm-l@mat.puc-rio.br>
>Subject: Re: [obm-l] Quadrados em um Quadriculado.
>Date: Fri, 31 Jan 2003 12:02:05 -0200
>
>Suponha que os lados do quadrado foram divididos em n partes iguais, cada
>uma com comprimento = 1.
>
>Sejam:
>D(k) = número de quadrados "direitos" (com lados paralelos ao quadrado
>maior) de lado com medida "k" contidos no quadrado maior (de lado "n").
>T(k) = número de quadrados "tortos" (com lados não paralelos aos do
>quadrado
>maior) e que cabem num quadrado "direito" de lado k, mas não num quadrado
>de
>k-1.
>
>Não é difícil ver que:
>D(1) = n^2, D(2) = (n-1)^2, D(3) = (n-2)^2, ..., D(k) = (n-k+1)^2, ...,
>D(n)
>= 1^2 = 1
>
>Além disso, temos:
>T(1) = 0, T(2) = 1, T(3) = 2, ..., T(k) = k-1, ..., T(n) = n-1
>Justificativa:
>Suponha que os vértices do quadrado "direito" sejam os pontos (0,0), (k,0),
>(0,k) e (k,k) no plano cartesiano.
>Cada quadrado "torto" contado em T(k) terá que ter cada um de seus vértices
>contido numa aresta distinta do quadrado "direito", caso contrário, ou ele
>teria dois vértices numa mesma aresta e seria "direito" ou então ele
>caberia
>num quadrado "direito" menor ==> ambas as situações contradiriam a
>definição
>de T(k).
>Além disso, como um vértice desse quadrado determina todos os outros,
>existe
>uma bijeção entre o conjunto de quadrados "tortos" contados em T(k) e o
>conjunto de vértices de tais quadrados contidos, por exemplo, na aresta que
>vai de (0,0) até (0,k). Estes últimos seriam (0,1), (0,2), ..., (0,k-1) -
>total de k-1 vértices ==> T(k) = k-1.
>
>Finalmente, temos a relação:
>Q(n) = [ D(1) + D(2) + ... + D(n) ] + [ D(1)*T(1) + D(2)*T(2) + ... +
>D(n)*T(n) ]
>Justificativa:
>Q(n) = no. total de quadrados "direitos" + no. total de quadrados "tortos"
>O primeiro termo entre colchetes é claramente o no. total de quadrados
>"direitos".
>Cada quadrado "direito" de lado "k" contribui T(k) quadrados "tortos" que
>só
>cabem nele.
>Assim, a contribuição dos quadrados "direitos" de lado "k" para o total de
>quadrados "tortos" perfaz D(k)*T(k) quadrados.
>Quadrados "tortos" menores já terão sido contados como contribuição de
>quadrados "direitos" menores.
>Logo, o segundo termo entre colchetes é realmente o no. total de quadrados
>"tortos".
>
>Usando D(k) = (n-k+1)^2 e T(k) = k-1, além de manipulações algébricas e de
>fórmulas manjadas para a soma dos primeiros "n" naturais, assim como de
>seus
>quadrados e cubos, chegamos a:
>
>Q(n) = n*(n+1)^2*(n+2)/12.
>
>**************
>
>Ainda estou pensando na segunda parte...
>
>
>Um abraço,
>Claudio.
>
>
>----- Original Message -----
>From: "Paulo Santa Rita" <p_ssr@hotmail.com>
>To: <obm-l@mat.puc-rio.br>
>Sent: Wednesday, January 29, 2003 5:22 PM
>Subject: [obm-l] Quadrados em um Quadriculado.
>
>
>Ola Pessoal !
>
>O problema abaixo e uma generalização de uma questão que foi proposta em
>outra lista, algum tempo atras. Não e de solução imediata, mas não e
>dificil.
>
>PROBLEMA : Divide-se cada lado de um quadrado em N partes iguais. Pelos
>pontos de divisão tracam-se paralelas aos lados do quadrado, originando
>assim um quadriculado.
>
>1) Com vertices nos pontos deste quadriculado, quantos quadrados podem ser
>construidos ( em funcao de N ) ?
>2) Seja Q(N) o numero de quadrados. Para todo P natural dado diga se existe
>um natural N tal que Q(N) = 10^P.
>
>OBS1 : Note que para responder 2 voce precisa responder 1 atraves de uma
>funcao que seja "manipulavel".
>
>OBS2 : considerar neste calculo tambem os quadrados "inclinados" em relação
>ao quadrado original.
>
>UMA SUGESTAO : Supondo que o quadrado original tem lado medindo N, seja Q o
>conjunto de todos os quadrados construtiveis cujos lados sejam paralelos
>aos
>lados do quadrado original e cujos lados tem a mesma medida L, L =< N. Em
>qualquer um destes quadrados a quantidade de quadrados inscritos e cujos
>lados nao paralelos aos lados do quadrado original e constante ...
>Manipule
>com habilidade as expressoes que vao surgir que elas se reduzirao a um
>polinomio bem simples. Isto responde ao item 1 e da condicoes de encarar o
>intem 2. Para responder 2 basta aplicar o que voce sabe sobre raizes
>racionais de equacoes polinomiais inteiras.
>
>Um Abraco
>Paulo Santa Rita
>4,1652,290103
>
>
>
>
>
>
>_________________________________________________________________
>MSN Messenger: converse com os seus amigos online.
>http://messenger.msn.com.br
>
>=========================================================================
>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>
>=========================================================================
>
>
>=========================================================================
>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>
>=========================================================================
_________________________________________________________________
MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.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>
=========================================================================