22.7.17

Problemas matemáticos da Lusofonía-3


Editado o 24/07/2017: Esta entrada non resolve o problema proposto, como ben apunta Efe nos comentarios. Na entrada seguinte aparece unha solución de verdade. Déixovos que atopedes vós o erro.


Da Olimpíada de Matemática da Comunidade de Países de Língua Portuguesa xa falei por acó, e tamén da ausencia dunha web en condicións para consultala. Por sorte o ano 2016 foi celebrada no Brasil, onde xa teñen unha infraestrutura formidable arredor das olimpíadas, envexa de moitos outros países.

6ª Olimpíada de Matemática da CPLP


Na olimpíada do 2016 houbo varios problemas interesantes, por exemplo o 4º, sobre unha competición de futebol, que non reproduzo por ter un aire semellante ao da entrada previa. Mais o problema no que reparei foi o último, o 6º, que trataba de números:

Considere as potências de 2 com expoente inteiro positivo, ou seja, os números da forma $2^n$ em que n é um inteiro positivo: 2,4,8,16,... Prove que toda potência de 2 com expoente inteiro positivo pode ser escrita na forma

$$5xy-x^2-2y^2$$

com x e y ímpares positivos.

Vou compartir a secuencia que me levou a resolver o problema, pero antes, para non subtraer a diversión de resolvelo aos amables lectores, velaquí unha adiviña sinxela. A ver se descubrides que cuestión matemática representa a seguinte imaxe minimalista:

A solución, nesta páxina, e o resto de obras de Crockett Johnson aquí

Onde estabamos? Ah, si, con

$$5xy-x^2-2y^2$$

Outra persoa con máis intuición ca min seguramente poderá ver xa con claridade o asunto. Como eu non teño tanta vista, cando tento resolver un problema destes o primeiro que fago é, vaia,... fedellar, termo non recollido literalmente nas recomendacións de Polya mais que recolle o seu espírito.

Neste caso fedellar significa probar con casos pequenos das potencias de 2 e ver se observamos un patrón:
A primeira sae rápido:
$$2^1=5 \cdot 1 \cdot1-1^2-2\cdot1^2$$
Para escribir menos LATEX, vou chamar
$$f(x,y)=5xy-x^2-2y^2$$
A segunda(xa coa nova notación), tamén:
$$2^2=f(2,1)$$
As sucesivas:
$$2^3=f(2,3)$$
$$2^4=f(3,5)$$

Chegado a este punto, que foi o que vin? Pois si, números de Fibonacci. Neste momento pensei que tiña solucionado o conto, pois xa ía elucubrando como obter a representación dunha potencia de 2 desde a representación da anterior, ou das dúas anteriores...
Se lembrades a sucesión de Fibonacci,
$$1,1,2,3,5,8,13,21,...$$
E comparades coas primeiras representacións que obtiven,
$$(1,1),(2,1),(2,3),(3,5),...$$
Parece razoable pensar que os pares van aparecendo de xeito consecutivo na sucesión de Fibonacci.
Pasei uns minutos dándolle voltas porque non vía a zoca que metera, ao crer que o patrón dos pares ordenados era
$$(F_{n},F_{n-1})\rightarrow (F_{n+1},F_{n})$$
Pero os pares non cumpren nin ese patrón nin nada semellante. Se avanzamos na sucesión, vemos que o par $(5,8)$ falla:
$$f(5,8)=47$$
$$f(8,5)=86$$
Se temos en conta que a paridade dos números de Fibonacci é impar-impar-par-impar-impar-par-... veremos que o par impar-par nunca vai funcionar  nesa orde, pois  f(impar,par) é claramente impar.

A sensación de que unha idea que un cre exitosa resulta un fracaso é tremenda, e moitas veces é aí cando se deixan de lados os problemas, polo menos a min xa me ten pasado un feixe de veces.

Que fixen ante este fracaso (parcial)? Seguir fedellando.

Entón, for no particular reason, escribín a función en forma matricial:
$$f(x,y)=\left( \begin{array}{ccc} x & y \end{array} \right)  \left( \begin{array}{ccc}
-1 & \frac{5}{2} \\
\frac{5}{2} & -2 \end{array} \right) \left( \begin{array}{ccc} x \\ y  \end{array} \right) $$

Tiven unha epifanía cando vin a matriz? Non. Aí quedou. A resolución de problemas non é como as TV movies, unha mágoa.

Mais, de súpeto, mirando para a expresión alxébrica $f(x,y)$ obviei as variables e fixeime só nos números, e vin...
$$5-1-2=2$$

O que provocou, agora si, a iluminación: se considero pares cos dous números iguais,obterei o dobre dun cadrado. Vedes por que isto é útil?
$$f(x,x)=5x \cdot x-x^2-2x^2=2x^2 $$
Collendo $x=2^n$, obtemos $f(2^n,2^n)=2(2^n)^2=2\cdot 2^{2n}=2^{2n+1}$

Que case, case, resolve o problema: xa o temos resolto para potencias impares de 2.

O que veu despois para resolver o caso de potencias pares, supoño que é inmediato, pero non sei como se me ocorreu:

Collendo pares ordenados nos que o primeiro número é o dobre do segundo, vemos o camiño:
$$f(2x,x)=5 \cdot 2x \cdot x-(2x)^2-2\cdot x^2=4x^2$$
Só temos que considerar $x=2^{n-1}$ para obter $f(2^n,2^{n-1})=4(2^{n-1})^2=(2^n)^2=2^{2n}$

E así representamos as potencias pares de 2. Xunto ao anterior, queda demostrado que todas as potencias de 2 de expoñente positivo poden ser escritas dese xeito, agás erratas. Se alguén atopa unha solución distinta, pode deixala nos comentarios.

4 comentarios:

  1. Pero, ¿no decías que X e Y debían ser impares? Igual el gallego me despista.

    ResponderEliminar
    Respostas
    1. Si, iso dixen...ao facer copy/paste do pdf da olimpíada, e non o volvín ler. Vou deixar o post como exemplo do que non hai que facer, non comprobar se un resolveu o que pedía o problema :/

      Eliminar
  2. Pero, entonces, debían ser pares, ¿no? Deja una aviso para lectores futuros, que yo me he vuelto loco intentando hacerlo tal y como estaba.

    ResponderEliminar
    Respostas
    1. Non, non, o que pon en portugués: X E Y TEÑEN QUE SER IMPARES.
      Xa atopei unha solución, curiosamente na liña do primeiro que pensara, se teño tempo publícoa noutro post despois.

      Eliminar