Roberto Ribeiro Paterlini*
Departamento de Matemática da UFSCar.

No estudo das soluções do problema abaixo deparamos com uma situação fórmula versus algoritmo. O problema comporta dois tipos diferentes de solução. Podemos obter uma fórmula que fornece uma resposta direta. Ou então podemos construir um algoritmo que também nos dá a resposta quando os dados são concretizados.

Uma experiência com este problema em sala de aula nos leva a algumas reflexões sobre o Ensino da Matemática. Não estaríamos nós, professores, enfatizando demasiadamente a associação entre solução de um problema e obtenção de uma fórmula, em detrimento da elaboração de algoritmos?

Sejam b e h inteiros positivos > 1. Considere um retângulo de base b e altura h reticulado por linhas paralelas aos lados, formando bh quadrados unitários. Quantos desses quadrados tem seu interior interceptados por uma diagonal do retângulo?

__________
*O autor agradece as sugestões do colega Sérgio Rodrigues.

Esse problema pode ser encontrado no artigo Counting Squares de David L. Pagni, publicado no periódico Mathematics Teacher, vol. 84, n.°9, dezembro de 1991, página 754. Nós o propusemos em uma aula de problemas para alunos de Licenciatura em Matemática da UFSCar. Na figura acima, temos b = 6 e h = 4, e pode-se ver que o número de quadrados unitários que têm seu interior interceptado pela diagonal é 8.

Não é fácil visualizar a fórmula correta a partir desses dados. Com a ajuda do professor, os estudantes viram que n = b + h mdc(b, h). Passaram então o restante da aula elaborando uma demonstração para essa fórmula.

Paralelamente a essas atividades, um estudante trabalhava de modo diferente, e no final da aula apresentou-nos uma solução, que resumimos a seguir.

Observou que trocando b por h e vice-versa o resultado não se modifica. Observou ainda que nos seguintes casos o problema é trivial. Primeiro, se  h = 1 (ou b = 1),  o número de quadrados unitários interceptados é igual a b (ou h, respectivamente). Segundo, se b = h, o número de quadrados interceptados é b.

Vejamos o caso 3 x 2. Esse retângulo deve ser decomposto em dois retângulos menores. O primeiro é o maior quadrado possível que caiba no retângulo (portanto, um quadrado 2 x 2). O segundo é o retângulo 1 x 2. Algebricamente temos

3 x 2 = 2 v 2 + 1 x 2.

A figura a seguir ilustra como deve ser subdividido o retângulo 3 x 2 em retângulos menores.

O estudante observou que os retângulos menores estão dentro dos dois casos triviais já considerados acima. Como o retângulo 2 x 2 nos fornece 2 quadrados unitários interceptados (caso b = h), e o retângulo 1 x 2 nos fornece também 2 (caso b = 1), então (concluiu o estudante) o número de quadrados unitários interceptados no retângulo 3 x 2 é 4.

Para melhor ilustrar o procedimento, vejamos também o caso 11 x 7. Esse retângulo é decomposto em 4 retângulos menores. Primeiro retiramos o maior quadrado possível, no caso, um quadrado 7 x 7. Do restante, repetimos o procedimento: novamente tomamos o maior quadrado possível (no caso, um quadrado 4 x 4). E assim por diante. Paramos quando o retângulo inicial se esgota ou sobra um retângulo do tipo b = 1 ou h = 1. No nosso exemplo particular temos a decomposição:

11 x 7 = 7 x 7 + 4 x 4 + 3 x 3+ 1 x 3.

Cada um desses retângulos menores está dentro dos dois casos triviais considerados acima. Então (concluiu o estudante) o número de quadrados unitários interceptados no retângulo 11 x 7 é a soma

7 + 4 + 3 + 3 = 17.

Termina aqui a solução de nosso estudante. Não nos apresentou demonstração da validade do algoritmo, mas verificamos que funcionava perfeitamente.

Apresentamos primeiro uma demonstração da fórmula: o número de quadrados unitários interceptados é b + h — mdc(b, h) (*)

Indicaremos por 1, 2,..., k os pontos da diagonal que são comuns a uma linha horizontal ou vertical do reticu­ado. Suponhamos que os pontos estejam ordenados, isto é, j está entre j 1 e j +1. Confira a figura ao lado.

Cada um dos segmentos 12, 23, ... , k 1 k está univocamente associado a um quadrado unitário que tem seu interior interceptado pela diagonal. Como temos k 1 desses segmentos, nosso problema ficará resolvido quando determinarmos k 1 em função de b e h.

Por definição k é o número de pontos da diagonal que são comuns a uma das linhas do reticulado. A diagonal intercepta exatamente uma vez cada uma das b + 1 linhas verticais e cada uma das h + 1 linhas horizontais. Mas do número b + 1 + h + 1 devemos subtrair o número de pontos da diagonal que são comuns com algum vértice de um quadrado unitário, de modo que estes pontos não sejam contados duas vezes.

Um desses pontos é certamente (x₀, y₀) = (0,0). Os outros pontos (x_i, y_i), i 1, são tais que x_i e y_i são inteiros positivos e a inclinação do segmento que une (0,0) a (x_i, y_i) é a mesma que a da diagonal, isto é,

Esses pontos podem ser obtidos considerando-se todas as frações m/n equivalentes a h/b tais que m h e n b. A "menor" dessas frações é a fração irredutível p/q que é obtida simplificando a fração h/b por mdc(b,h). Depois, 'multiplicando-se'  p/q  por 1, 2, 3, ... , mdc(b,h), obtemos as frações procuradas. Assim, contando com (0,0), existem mdc(b, h) + 1 pontos (x_i, y_i), i 0.

Por exemplo, sejam b = 12 e h = 8 (ver figura abaixo).  Como mdc(12,8) = 4, simplificando-se 8/12 por 4 obtemos a fração equivalente irredutível 2/3. Assim, as frações equivalentes

fornecem os pontos (3,2), (6,4), (9,6) e (12,8), que pertencem à diagonal.

Voltando aos cálculos anteriores,

k = b + l + h +1 (mdc(b,h) + 1)     ou     k 1= b + h mdc(b,h).

Portanto existem b + h mdc(b,h) quadrados unitários que têm seu interior interceptado pela diagonal. Fica assim demonstrada a fórmula (*).

Vamos fazer agora algumas considerações sobre a solução do estudante. Trata-se de uma sequência de procedimentos que, executados corretamente, nos levam à solução, desde que b e h sejam fornecidos em valores numéricos. Dizemos que essa sequência de procedimentos é um algoritmo.

A princípio ficamos surpresos com essa solução. Mas dois fatos nos levaram a pensar que o algoritmo estava correto. Primeiro, sua semelhança com o algoritmo euclidiano para o cálculo do máximo divisor comum. Segundo, aplicando o algoritmo a alguns exemplos, verificamos que funcionava perfeitamente. Fizemos então um estudo posterior, no qual constatamos:

a)     A fórmula b + h — mdc(b,h) implica a validade do algoritmo;

b)     A fórmula b + h — mdc(b,h) pode ser obtida do algoritmo;

c)       A veracidade do algoritmo pode ser obtida independentemente da fórmula.

Provaremos as afirmações a) e b), as quais significam que a fórmula e o algoritmo são equivalentes. A afirmação c) será deixada para o exercício da argúcia do leitor.

Indicaremos por Nb h o número de quadrados unitários interceptados por uma diagonal do retângulo b x h. Algumas identidades óbvias são:  N_b.h = N_h.h ,   N_b.b = b  e  N_1.h = h.  Por outro lado, o algoritmo consiste essencialmente da seguinte propriedade: dados os inteiros positivos b h, se b  qh + r, onde 0 r < h, então

N_b._h = qN_h._h + N_r._h = qh + N_r._h.                                     (**)

a) A fórmula b + h mdc(b,h) implica a validade do algoritmo.

Supondo válida a fórmula, temos   N_b.h = b + h mdc(b,h).   Portanto

N_b._h = b + h mdc(b,h)

                = qh + r + h mdc(h,r)

   = qh + N_r.h,       

e isso implica a veracidade de (**) e, conseqüentemente, do algoritmo.

b)  A fórmula b + h mdc(b,h) pode ser obtida do algoritmo.

Para sistematizar, anotaremos  b = a₁  e  h = a₂.  O algoritmo euclidiano aplicado a a₁ e a  a₂ pode ser assim desenvolvido:

  a₁ = q₁a₂ + a₃,      0 a₃ < a₂,

  a₂ = q₂a₃ + a₄,      0 a₄ < a₃,

  a₃ = q₃a₄ + a₅,      0 a₅ < a₄,

a_n-3= q_n-3a_n-2 + a_n-1,    0 a_n-1 < a_n-2,

a_n-2= q_n-2a_n-1 + a_n,    0 a_n < a_n-1,

a_n-1= q_n-1a_n + 0,

onde a_n = mdc(a₁, a₂). Somando-se todas as equações acima, vem

a₁ + a₂₁ + ^{. . .} + a_n-1 = (q₁a₂ + ^{. . .} + q_n-1a_n) + (a₃ + ^{. . .} + a_n)

donde

a₁ + a₂  = (q₁a₂ + ^{. . .} + q_n-1a_n) +  a_n,

ou

q₁a₂ + ^{. . .} + q_n-1a_n = a₁ + a₂ a_i.

Aplicando repetidamente a propriedade (**) acima, temos

como queríamos demonstrar.

É principalmente a diversidade de abordagens dos assuntos em estudo que ativa a flexibilidade e a capacidade de compreensão da mente dos estudantes. Essa diversidade faz compreender ao estudante de uma maneira prática que há muitos modos de tratar o mesmo problema intelectual.

No Ensino da Matemática através de Problemas, vimos que devemos colocar nossa atenção na possibilidade de se apresentarem soluções na forma de algoritmos. A elaboração de algoritmos desenvolve qualidades de organização e previsão, e é uma atividade que não deve ser omitida no ensino formal da Matemática.

Bibliografia

Pagni, D. L. Counting Squares, em Mathematics Teacher, vol. 84, n.° 9, dezembro de 1991, página 754.

Roberto Ribeiro Paterlini é professor de Matemática na Universidade Federal de São Carlos e dedica a maior parte de seu trabalho profissional à formação de professores de Matemática para o 1.° e  2.° graus.