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\)" <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
To: <[EMAIL PROTECTED]>
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" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
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 é <[EMAIL PROTECTED]>
=========================================================================
=========================================================================
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 é <[EMAIL PROTECTED]>
=========================================================================
_________________________________________________________________ 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 é <[EMAIL PROTECTED]> =========================================================================
