[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Quadrados em um Quadriculado.
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>
=========================================================================