Dotzé repte: Reordenant

En aquest repte l’objectiu és reordenar els nombres 1, 2, 3, 4, 5 i 6 que es troben ordenats de major a menor i posar-los ordenats de menor a major, com es pot veure en la següent imatge:

Reordenació

Reordenació

Només tenim dos moviments permesos:

– Un nombre es pot moure a la casella del seu costat si està buida.

– Un nombre pot botar a un altre (com en el joc de les dames) si la casella a la que bota està buida.

De fet, seguint aquestes regles només podem elegir entre dos moviments inicials, o el 6 es mou a la casella buida del seu costat, o el 5 bota al 6 per a ocupar la casella buida.

El repte consistirà en trobar quina és la mínima quantitat de moviments necessària per a aconseguir posar els nombres en l’ordre de menor a major.

I si aconseguiu obtindre la quantitat mínima quan tenim 6 nombres, també seria interessant obtindre la quantitat mínima quan tenim n nombres, és a dir, obtindre una fórmula en funció del valor n.

Ànim i sort.

14 pensaments sobre “Dotzé repte: Reordenant

  1. Una cosa… Es que porte un bon rato intentant treure la fòrmula i no la trobe. Crec que tinc els mínims moviments possibles amb 2,3,4,5 i 6 nombres. Volia preguntar si apartir d’aquests resultats ja puc treure-la. O he de intentar-ho amb nombres més grans? Moltes gràcies!!😃

    • No em digues que ja has sigut capaç d’obtindre els moviments mínims per a 2, 3, 4, 5 i 6… no m’ho puc creure.
      Podries posar quins són eixos mínims moviments?
      Per cert, com ho has fet?, ho has fet amb fitxes amb els nombres i has anat fent els moviments o escrivint tots els passos?
      La veritat és que m’has sorprés.
      Respecte a la fórmula jo no l’he calculada encara (de fet encara no m’he posat a traure els mínims moviments per a cada cas) i de fet no sé si algú ho haurà fet alguna vegada. Potser sigues la primera 🙂 Aquest repte no l’he vist mai per a obtindre els mínims moviments i molt menys per a traure la fórmula, així que potser no siga possible, però segur que tu la traus.
      De tota manera, amb els casos que tens, d’existir una fórmula, potser la pugues intuir ja amb eixos casos. Podries intentar calcular per a 7 i 8 i així ampliar un poc la visió.
      Si em passes els mínims moviments, potser puga ajudar-te un poc 🙂
      Intentaré fer quan abans els moviments mínims (per a saber que ho he fet bé els compararé amb els teus 😉 ) i intentaré traure la fórmula.
      Vinga, a veure si traus la fórmula abans que jo.

  2. 2=3
    3=5
    4=10
    5=16
    6=21

    Potser no puc treure la fórmula perquè algun dels resultats està mal, però jo no ho he aconseguit fer amb menys moviments. D’altra banda m’extranya que hi haja més diferència de passos entre 4 i 5 nombres que entre 5 i 6. No sé si m’entens…
    Jo ho he calculat escrivint tots els passos ( ja que no són molts), però les fitxes són una molt bona idea!
    Adéu!!

    • Fantàstic Irene, has sigut tan ràpida que jo no he pogut fer-ho abans que tu.
      Només he tingut temps per a comprovar els casos de 2 i de 3, que coincidisc amb els resultats que tu has tret.
      Per al cas de 4 també ho he tret amb 10, però he de mirar que no es pot amb menys.
      El 5 igual, encara no he provat que siga la quantitat mínima, però el que sí tens correcte és el 6, que era el que jo plantejava en el repte. Efectivament són 21 moviments com a mínim. No imaginava que ho trauries tan ràpid. M’has sorprés realment (em pareix que una cosa tan espectacular com 133 es queda inclús curt 😉 )
      Respecte a la fórmula, potser no existisca, però em dóna la sensació que sí existirà. Amb els nombres que tens no pareix que siga suficient per a obtindre una expressió general, a no ser que en el procés de resoldre cadascun dels casos hages observat alguna pauta que permeta calcular la quantitat total a partir del procés seguit (si recordes, és el que es feia en el huité repte, encara que per a obtindre la fórmula en eixe repte es podia fer únicament mirant els resultats que s’obtenien).
      Aquest repte és prou més complicat i per això m’ha sorprés que ho tragueres tan ràpid. Ara bé, la fórmula ja és un escaló de dificultat prou més gran, encara que probablement al teu abast.
      Estaria de categoria disposar dels casos amb 7 i 8 nombres, però jo crec que costaria prou obtindre els moviments mínims. Si els intentares ja comentes els resultats. Per la meua part, quan tinga un poc de temps intentaré fer els casos des del 2 fins el 8 i intentaré veure alguna pauta, ja siga en el procés o en els propis resultats.
      Gràcies Irene.

  3. Amb 7 nombres els mínims moviments que he aconseguit fins ara són 33, encara que crec que es pot fer amb menys…
    Per cert, amb 4 i amb 6 nombres els passos sí que segueixen un patró.
    6=3+1+2+1+3+1+2+1+3+1+2+1
    4=2+1+1+1+2+1+1+1
    El resultat amb 2 i 3 nombres:
    2=1+1+1
    3=1+1+1+1+1
    Amb 5 i 7 no he trobat cap patró clar…
    Adéu i bon cap d’any!

    • Interessants els patrons que has trobat, Irene.
      Jo encara no m’he pogut posar a mirar res 😦 però agafaré el camí que m’has marcat i així intentaré trobar una expressió general per a n nombres.
      Si el de 8 nombres es pot fer amb 36 moviments, ja tindria una possible expressió per al cas parell. De totes maneres ho hauria de comprovar. El que tinc en ment són uns determinats nombres que apareixen en el “Triangle de Pascal”.
      Com encara no he pogut trobar temps per a intentar el problema, no puc assegurar si estem en els casos mínims, però fixa’t amb el que tu has tret:

      2 -> 1+1+0+1
      4 -> 2+1+1+1+2+1+1+1
      6 -> 3+1+2+1+3+1+2+1+3+1+2+1

      El 8 serà com segueix?
      8 -> 4+1+3+1+4+1+3+1+4+1+3+1+4+1+3+1

      Com no ho puc comprovar ara, ho intentaré l’any que ve, però potser tu sigues capaç de fer-ho inclús aquest mateix any 🙂 🙂 🙂 però descansa, que ja toca preparar l’any nou.
      Feliç any nou !!!

      • No m’he pogut ressistir, m’he fet unes fitxetes i efectivament el patró és correcte.
        El 8 és com pareixia i supose que és extensible a qualsevol nombre parell, encara que he de comprovar-ho.
        L’expressió per al cas parell és per tant expressable per una fórmula, només queda calcular-la i de fet és senzill si mirem el “Triangle de Pascal” i observem una de les diagonals. L’expressió és la mateixa que per a traure els nombres del triangle de Pascal, que està basada en nombres combinatoris. Si mires com traure els nombres apropiats del “Triangle de Pascal” veuràs que és fàcil.
        Faltarà el cas senar (imparell), on haurem de trobar un patró, però ja saps, sense la teua ajuda no podré 😉
        Però això ja per a l’any que ve, ja que ara sí no tinc ni un minut més.
        Feliç any nou!!!

  4. Ja he trobat el patró dels imparells 🙂
    I efectivament existeixen fórmules vàlides per al cas parell i per al cas imparell.
    El cas imparell té una dificultat just en l’últim cicle de moviments.
    El de 7 es pot fer amb 31 i el de 9 amb 50.
    Et pose la seqüència del cas amb 3 nombres, amb 5 i amb 7 i a veure si detectes el patró:
    3-> IiDiD
    5-> IIiDDdIIiDDiIddD
    7-> IIIiDDDdIIIiDDDdIIIiDDDiIIddddD
    on “I” és un bot a l’esquerre, “i” un desplaçament a l’esquerre, “D” un bot a la dreta i “d” un desplaçament a la dreta.

    Respecte a les fórmules són expressions de grau 2 tant per al cas parell com per a l’ imparell, és a dir an^2+bn+c on s’ha de descobrir els valors a, b i c (alguns són fraccions).

    A veure si ho traus.

  5. Hola!!
    He entés perfectament el patró dels imparells!! El que no puc aconseguir és treure la fórmula… He mirat a Internet el referent al mètode de Gauss i he intetat fer-ho, però no m’ix… No sé com resoldre una equació amb tres incògnites… De totes maneres aniré intentant-ho.
    Adéu i bona nit!!

    • Perfecte Irene. La qüestió era trobar el patró per a fer qualsevol cas, tant parell com imparell i ara ja està clar. De fet no únicament podem traure els mínims moviments, també el procediment per a aconseguir fer-ho amb eixos moviments.
      Et comente un exemple del mètode de Gauss:

      si n=2 -> 4a + 2b + c=3
      si n=4 -> 16a+ 4b + c=10
      si n=6 -> 36a+ 6b + c=21

      És aplicar el mètode de reducció de manera que al final ens quede una equació amb una incògnita, una equació amb dues incògnites i una amb les tres, i així ja es pot resoldre.

      Vaig a resoldre l’exemple anterior no estrictament per Gauss. Vaig a fer reducció.

      Puc restar la segona equació menys la primera i obtindré:
      12a+2b=7
      I si restem la tercera equació menys la primera obtindrem:
      32a+4b=18

      Ara ja hem aconseguit dues equacions amb dues incògnites. Puc de nou aplicar reducció a aquestes dues equacions fent per exemple la segona que hem obtés menys el doble de la primera que hem obtés, de manera que tindrem:
      8a=4, és a dir a=1/2

      Ara ja puc substituir este valor de a en qualsevol de les dues equacions i obtindrem b=1/2. I amb els valors coneguts de a i b ja podem substituir-los en qualsevol de les tres equacions original i així obtenim c=0.

      Per tant la fórmula per al cas parell és:
      Quantitat de moviments=(n^2 + n)/2

      Si proves la fórmula veuràs que funciona correctament 🙂

      Per al cas imparell s’hauria de fer de manera similar. Si ho has entés ja el podràs fer, encara que ja serà un altre dia 😉

      Bona nit i gràcies.

  6. Ja tinc la fórmula per als imparells!!!😝
    a=1/2
    b=3/2
    c=-4
    Aleshores la fórmula és: quantitat mínima de moviments=(n^2+3n)/2-4

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