Dos problemes relacionats

Bon dia!

Avui dos problemes que en la seva resolució hi ha implicada la mateixa idea.

Primer problema

En la figura es pot veure un graf format per 16 vèrtexs i uns segments que connecten cada vèrtex amb uns altres tres. Una formiga surt del vèrtex A per fer un seguit de moviments. Un moviment consisteix a anar d’un vèrtex a un vèrtex veí seguint el segment que els connecta. En quins dels vèrtexs P, Q, R, S i T pot estar la formiga després de fer 2019 moviments?

Segon problema

Tenim un cub en el qual les arestes són de filferro i una formiga surt del vèrtex A i va passant d'un vèrtex a l'altre per les arestes. Després de fer un camí de 2020 arestes és possible que sigui al vèrtex B oposat l'A?

Solucions a dos problemes relacionats

Bon dia!

Com és habitual últimament és en Lluís qui ha enviat aquestes solucions:

Les solucions estan bé però en Lluís no explica en cap moment en què es basen les numeracions que fa.

La meva solució al primer problema és molt simple i es basa en pintar els 16 punts de la següent forma:

Com podeu veure he dividit els punts en dues classes: uns de negres i la resta blaus. Si us hi fixeu, cada punt negre està lligat a tres de blaus i cada punt blau a tres de negres. És a dir, si sortim d'un punt negre, anem a parar a un punt blau segur i, si sortim d'un punt blau, anem a parar a un punt negre. Per tant, en el problema passem d'un punt blau a un de negre i d'un punt negre a un de blau. El problema s'ha convertit en un problema de paritat. Com que el punt A és blau si fem un nombre parell de moviments anirem a parar en un de blau i si en fem un nombre senars anirem a parar en un punt negre. En el nostres cas en fem 2019, nombre senars i, per tant, l'únic punt dels P, Q, R, S i T al qual podem estar, és el Q, perquè tots els altres són blaus.

El segon problema es resol fent el graf d'un cub tal com es pot veure a la següent figura:

Suposo que ara trobar la solució és ben fàcil.