Solució al huité repte

El huité repte era el de les granotes.

Granotes botadores

Com bé va comentar Mar Guerola, la fórmula per al mínim nombre de moviments amb n granotes en cada part és n·(n+2).

Per a descobrir aquesta fórmula podem procedir calculant la quantitat total de moviments per a diversos valors de n i veure que és vàlida per a tots ells, però no estaríem segurs que sempre vaja a funcionar. De manera que si volem saber per què és eixa la fórmula vàlida haurem de pensar en una estratègia per a comptar els moviments de les granotes.

Anem a analitzar diferents valors de n i ho farem comptant la quantitat de moviments seguits de les granotes del mateix color.

Si n=1: 1 verda, 1 marró i 1 verda, és a dir en total 1+1+1=3 moviments.

Si n=2: 1 verda, 2 marrons, 2 verdes, 2 marrons i 1 verda, és a dir en total 1+2+2+2+1=8 moviments.

Si n=3: 1 verda, 2 marrons, 3 verdes, 3 marrons, 3 verdes, 2 marrons i 1 verda, és a dir en total 1+2+3+3+3+2+1=15 moviments.

Només observant aquestos valors probablement ja observeu la seqüència de moviments, de manera que si tenim un valor n genèric tindrem:

1+2+3+…+(n-2)+(n-1)+n+n+n+(n-1)+(n-2)+…+3+2+1 moviments, que si recordeu la suma d’una successió aritmètica podreu traure fàcilment, ja que consisteix en sumar des del número 1 fins a n dues vegades i després sumar-li n:

1+2+3+…+(n-2)+(n-1)+n=n·(n+1)/2

Si ho multipliquem per 2 tindrem n·(n+1)

I si finalment si sumem n tindrem n·(n+1)+n=n·(n+1+1)=n·(n+2) que és la fórmula que buscàvem.

Una altra cosa seria comprovar que efectivament es tracta de la mínima quantitat de moviments i que no es pot fer en menys moviments, però això ja us ho deixe a vosaltres.

3 pensaments sobre “Solució al huité repte

Deixa un comentari

Fill in your details below or click an icon to log in:

WordPress.com Logo

Esteu comentant fent servir el compte WordPress.com. Log Out / Canvia )

Twitter picture

Esteu comentant fent servir el compte Twitter. Log Out / Canvia )

Facebook photo

Esteu comentant fent servir el compte Facebook. Log Out / Canvia )

Google+ photo

Esteu comentant fent servir el compte Google+. Log Out / Canvia )

Connecting to %s