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) |
.
Temos as seguintes possibilidades para
,
e
:
|
|
|
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
:
|
|
|
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.