Olá meus amigos nerds. Hoje vamos resolver um probleminha de matemática, já que é isso que o problema 3742. Feynman pede para fazer. Mais especificamente, quantos quadrados diferentes existem em um quadriculado de N x N quadrados?
Solução
Para responder essa pergunta basta somar quantos quadrados de 1, 2, ..., N existem no quadriculado.
Para descrever um quadrado em um quadriculado é preciso apenas de um ponto: o ponto de início do quadrado, a partir desse ponto todos os outros quadradinhos do quadriculado que o quadrado ocupa ficam determinados.
Dito isso, como o quadriculado tem N x N existem N^2 quadrados de tamanho 1.
Posso começar um quadrado de tamanho 2 em qualquer uma das N linhas e N colunas com excessão da última linha e coluna. Assim existem (N-1)*(N-1) = (N-1)^2 quadrados de tamanho 2.
Já quadrados de tamanho 3 não podem começar nas duas últimas linhas e colunas. Assim teríamos (N-2)*(N-2)=(N-2)^2 quadradinhos de tamanho 3.
...
Por fim existe apenas 1 quadrado de tamanho N.
Em outras palavras:
1 -> N^2
2 -> (N-1)^2
3 -> (N-2)^2
...
N -> 1
Então a resposta é a soma dos quadrados dos números de 1 a N.
Para descrever um quadrado em um quadriculado é preciso apenas de um ponto: o ponto de início do quadrado, a partir desse ponto todos os outros quadradinhos do quadriculado que o quadrado ocupa ficam determinados.
Dito isso, como o quadriculado tem N x N existem N^2 quadrados de tamanho 1.
Posso começar um quadrado de tamanho 2 em qualquer uma das N linhas e N colunas com excessão da última linha e coluna. Assim existem (N-1)*(N-1) = (N-1)^2 quadrados de tamanho 2.
Já quadrados de tamanho 3 não podem começar nas duas últimas linhas e colunas. Assim teríamos (N-2)*(N-2)=(N-2)^2 quadradinhos de tamanho 3.
...
Por fim existe apenas 1 quadrado de tamanho N.
Em outras palavras:
1 -> N^2
2 -> (N-1)^2
3 -> (N-2)^2
...
N -> 1
Então a resposta é a soma dos quadrados dos números de 1 a N.
Nenhum comentário:
Postar um comentário