Hipertexto Pitágoras Matemática Elementar Matemática Superior Sítios Guia Rápido Serviços Notícias Fórum Índice Página do Editor Questões Respondidas Questões não Respondidas Portfolio

SOLUÇÃO DO PROBLEMA 2 DO I CONCURSO IBEROAMERICANO DE PROBLEMAS DE MATEMÁTICA

Waldeck Schützer


o problema

Consideremos a função polinomial nas variáveis ,..., , ,..., . Suponhamos que as variáveis tomam unicamente os valores 0 ou 1. Seja o número de -uplas para as quais o polinômio toma valor ímpar, e seja o número de -uplas para os quais o polinômio toma valor par. Prove que

Este problema foi classificado em segundo lugar no I Concurso Iberoamericano de Generación de Problemas de Matemática, promovido pela Sociedad Iberoamericana para la Promoción de la Matemática (SIPROMA) . O Juri Internacional, composto por Angelo Barone, Francisco Bellot, Carlos Bosch, Patricia Fauring e Eduardo Wagner, outorgou o 2º prêmio  aos  autores Gerardo Raggi e Humberto Cárdenas (México).


solução

Indicaremos por o número de -uplas para as quais o polinômio toma valor par, e por o número de -uplas para as quais ele toma valor ímpar. Iniciamos verificando as seguintes relações de recorrência:
 
 
(1)
(2)
Consideramos primeiro o caso . Temos as seguintes possibilidades para , e :

0
0
0 (par)
0
1
0 (par)
1
0
0 (par)
1
1
1 (ímpar)
 

Vemos que o número de 2-uplas para as quais o polinômio toma valor par é , e o número de 2-uplas para as quais o polinômio toma valor ímpar é .
Temos igualmente as seguintes possibilidades para , e :
 

0
0
0 (par)
0
1
0 (par)
1
0
0 (par)
1
1
1 (ímpar)

Observemos que o polinômio resulta par se e somente se:
i) e são pares, e o número de -uplas nestas condições é ;
ii) e são ímpares, e o número de -uplas nestas condições é .
Concluímos que .
Por outro lado o polinômio resulta ímpar se e somente se:
i) é par e é ímpar, e o número de -uplas nestas condições é ;
ii) é ímpar e é par, e o número de -uplas nestas condições é .
Concluímos que . Isto termina a verificação das relações de recorrência acima.

Apresentamos a seguir duas soluções para o problema dado.

1ª solução. Utilizaremos o Método da Indução Finita sobre o número natural para provar que


para todo . Vimos das relações de recorrência acima que e . Em conseqüência temos


e vale a afirmação (3) acima para . Suponhamos que a afirmação (3) seja verdadeira para , isto é,


Usando (1) e (2) calculamos o quociente da seguinte forma:


Usando a hipótese da indução e simplificando temos


Em virtude do método da Indução Finita esta relação é verdadeira para todo . Isto termina a nossa primeira solução do exercício.

2ª solução. Utilizaremos os métodos da Álgebra Linear para resolver a recorrência acima. Consideremos a matriz


é uma matriz diagonalizável. Seus autovalores são 4 e 2, com autovetores e , respectivamente. Portanto , onde


Notemos que , e assim


Considerando que


fazendo os cálculos obtemos


Utilizando este resultado concluímos que


Isto termina a segunda solução do problema. Observamos que nesta segunda solução obtivemos fórmulas para e .

início desta página
Este problema, de autoria de Gerardo Raggi e Humberto Cárdenas (México), foi classificado no I Concurso Iberoamericano de Generación de Problemas de Matemática. As soluções acima foram apresentadas por Waldeck Schützer (DM-UFSCar) em 06 de julho de 1998. José Ruidival dos Santos (DM-UFSCar) sugeriu o método para resolver as relações de recorrência. O texto foi preparado para publicação na Internet por Roberto R. Paterlini. Parcialmente utilizado o sistema Latex2html. Confira General License Agreement and Lack of Warranty sobre condições de uso.
Publicado em 01/08/98. Atualizado em 14/05/2002.