quinta-feira, 14 de fevereiro de 2013

Um problema, várias soluções


O objetivo desta postagem é apresentar um problema muito interessante no que diz respeito à variedade de soluções possíveis. O enunciado do problema é o seguinte:

Tome muitas varetas, tais quais a representada na figura 1, e comece a construir algumas estruturas quadriculadas tais quais as representadas na figura 2.

vareta
Figura 1 - vareta

estruturas quadriculadas construídas com as varetas
Figura 2 - estruturas quadriculadas construídas com as varetas

Observe que:

- na primeira construção, utilizamos 1 vareta como base do quadrado quadriculado construído;

- na segunda construção, utilizamos 2 varetas como base do quadrado quadriculado construído;

- na terceira construção, utilizamos 3 varetas como base do quadrado quadriculado construído.

Suponha que continuemos a construir tais quadrados quadriculados indefinidamente conforme o padrão sugerido pela figura 2. A pergunta é a seguinte:

Quantas varetas serão necessárias para construir o n-ésimo quadrado?

ou, de outro modo,

Quantas varetas serão necessárias na n-ésima construção?

ou ainda

Quantas varetas serão necessárias para construir o quadrado quadriculado cuja base possui n varetas?

Note que quando n = 2, então a resposta é 12. O problema pede uma resposta genérica, em função de n.

SOLUÇÃO 1 (usando teoria dos grafos):

Esta solução é a solução que originalmente apresentei quando, na faculdade, o problema me foi proposto:

Olhando para cada construção como um grafo, vemos que cada construção representa um grafo planar conexo. Logo a versão plana do teorema de Euler para poliedros convexos se aplica, ou seja, vale que

V + F  A = 2   (#)

onde V representa o número de pontos em que há intersecção de varetas, F representa o número de regiões delimitadas por varetas (incluindo a exterior) e A representa o número de varetas. Os números V e F são fáceis de calcular se conhecermos quantas varetas há na base do quadrado. Assim, observando as figuras, podemos perceber que na n-ésima construção teremos:

V = (n + 1)²
e
F = n² + 1

Segue de (#) que

A = V + F − 2 = (n + 1)² + n² + 1 − 2 = 2n(n + 1)

Para maiores explicações sobre o que é um "grafo planar conexo", sugiro que o leitor viste esta postagem (acompanhando as continuações, o leitor poderá ainda compreender melhor o que diz o teorema acima utilizado bem como observar outra aplicação dele).

SOLUÇÃO 2 (usando teoria dos grafos, de novo!):

Esta segunda solução é uma que, mais uma vez, utiliza a linguagem da teoria dos grafos: como cada construção pode ser vista como um grafo planar conexo, vale que

SG = 2A   (##)

onde SG representa a soma dos graus e A representa o número de varetas (veja aqui uma explicação para a expressão (##)).

Considere agora o n-ésimo grafo. Ele possui n² + 1 regiões, das quais uma é a exterior. A região exterior tem grau igual a 4n (quatro "lados", cada um com n varetas) enquanto que todas as outras n² regiões têm grau exatamente igual a 4. Assim, a partir de (##), concluímos que

A = SG/2 = (4n + 4n²)/2 = 2n(n + 1)

Para maiores esclarecimentos sobre grau e região de um grafo, novamente remeto o leitor a esta postagem.

Note que nas duas soluções acima chamamos de "vareta" aquilo que tecnicamente se chama "aresta".

SOLUÇÃO 3 (usando ???): desafio para o leitor!

SOLUÇÃO 4 (usando ???): desafio para o leitor!

SOLUÇÃO 5 (usando ???): desafio para o leitor!

As soluções 3, 4 e 5 não foram "descobertas" por mim. Elas me foram apresentadas na aula em que o problema foi proposto. Desafiamos, então, o leitor a descobrí-las e o convidamos a apresentá-la na área dos comentários. 

Obs. 1: Em postagem posterior publicaremos as demais soluções, incluindo as possíveis soluções dos comentários dos leitores (o fato de eu ter deixado três soluções em branco indica que existem pelo menos mais três diferentes abordagens para este problema).

Obs. 2: eu categorizei esta postagem como Raciocínio Lógico pois acredito que a solução mais direta deste problema envolve mais uma "boa sacada" do que algum conhecimento muito específico.

Obs. 3: Veja outro problema com várias soluções no blog Fatos Matemáticos.

ATUALIZAÇÃO: confira aqui a continuação desta postagem, com as soluções prometidas.

Referência: notas de aula.
Erros podem ser relatados aqui.

8 comentários :

  1. Solução 3: Analisando dois quadrados consecutivos, vemos que o número de palitos a_n satisfaz a equação de recorrência:
    a_(n+1) = a_n + 4(n+1) com a_1 = 4.

    Sendo D (delta) o operador diferença definido por Da_n = a_(n+1) - a_n, segue que Da_n = 4(n+1). Aplicando o operador anti-diferença, temos

    a_n = D^(-1)[4(n+1)] = 4(n+1)n/2 + C

    Usando a condição inicial, segue que

    4 = a_1 = 2(1 + 1)1 + C => C = 0

    Logo, a_n = 2(n+1)n

    Obs. Outro modo de resolver a equação de diferença finita acima é através da transformada discreta de Laplace (TDL). Saiba mais em meu blog.

    ResponderExcluir
    Respostas
    1. Olá Prof Paulo. Esta abordagem através do operador diferença é inédita relativamente às três soluções pensadas inicialmente. Obrigado pela participação! Abraço. Pedro R.

      Excluir
    2. Este comentário foi removido pelo autor.

      Excluir
  2. Olá Educador, como vai? Recebemos seu e-mail no EDUCADORES MULTIPLICADORES

    Respondendo sua indagação: basta seguir as regrinhas e só. A escolha das postagens é por nossa conta. Agora, caso faça questão de você mesmo selecionar 10 links (e os títulos das postagens) completos e nos enviar por e-mail, tudo bem. A escolha é sua!

    Para saber mais sobre a parceria clique AQUI

    Irivan

    ResponderExcluir
  3. Oi, Pedro,

    Muito interessante estes problemas e as suas duas soluções apresentadas usando a teoria dos grafos e o teorema de Euler.

    A solução do professor Paulo Sérgio também é muito boa. Uma peculiar oportunidade para uso do Cálculo Discreto. Eu pensaria em usá-la se não tivesse usado primeiro.

    Neste caso, resolvo com este caminho:

    De alguns valores de A_n, vemos que a segunda diferença de seus termos consecutivos é constante(4), ou seja,

    4,12,24,...
    8,12,...
    4,4,4,...etc

    Isto é característico de uma progressão aritmética de segunda ordem, cujo termo genérico é

    A_n=A0+A1(n-1)+(A2/2)(n-1)(n-2)

    Onde A0, A1 e A2 correspondem aos números da primeira coluna:

    A0=4, A1=8 e A2=4

    Substituindo estes valores,

    A_n=4+8(n-1)+2(n-1)(n-2)

    A_n=4+8n-8+2n^2-6n+4

    A_n=2n+2n^2

    A_n=2n(n+1)

    Se a construção fosse um cubo de palitos, faria a terceira diferença dos termos consecutivos e usaria o termo genérico de uma PA de terceira ordem:

    An=A0+A1(n-1)+(A2/2)(n-1)(n-2)+(A3/6)(n-1)(n-2)(n-3)

    Abraços!

    ResponderExcluir
    Respostas
    1. Olá Aloisio. Esta abordagem através do termo geral de uma PA de 2ª ordem também é inédita relativamente às três soluções pensadas inicialmente. Agradeço a participação! Abraço. Pedro R.

      Excluir
  4. eu criei uma fórmula bem básica: [N*(N+1)]*2

    onde N é o número de varetas da base

    ResponderExcluir
    Respostas
    1. Olá nirsaun. A fórmula sua está correta! Abraço. Pedro R.

      Excluir

Atualizações dos nossos parceiros: