Es 10 : Una pulce parte dal punto x = 2015 sulla retta reale e fa solo salti di lunghezza 1, in avanti o all’indietro. Quando però
capita su un multiplo di 6 il salto successivo può solo essere in avanti. Quante diverse sequenze di 15 salti può fare?
Questo problema (all'interno della nostra batteria che non era quella dei titolari) è stato risolto solo dalla mia squadra (più precisamente da me xD) fino a 10 minuti dalla fine. Cosa che mi ha fatto piacere perché abbiamo preso non pochi punti ma che mi ha fatto venire un dubbio su come l'ho risolto.
Io l'ho risolto così:
Testo nascosto:
Ho creato una tabella che rappresentasse il numero di casi possibili dopo ogni salto suddivisi rispetto al modulo in base 6 del numero del punto dove si trovava la pulce.
In questo modo avevo 6 colonne , una per modulo (una per i numeri $ 0 mod6 $ , una per i numeri $ 1 mod6 $ e così via) e 15 righe , una per salto (nella prima la situazione dopo un salto , nella seconda la situazione dopo due e così via) .
Dopo aver riempito la prima riga , per quelle successive bastava sommare i valori contenuti nella cella in alto a sinistra e in quella in alto a destra rispetto alla cella stessa.(stando attenti a non sommare nella colonna $ 5 mod6 $ quelli della colonna $ 0 mod6 $).
Andavo avanti a sommare tutta la tabella e così facendo alla fine bastava sommare i risultati nell'ultima riga e ottenevo il risultato.
Questo metodo risolutivo mi ha impiegato 10-15 minuti (si , sono lento con a fare i calcoli e quello che li fa a tutti e sei in squadra era già occupato da teoria dei numeri) ma mi è sembrato troppo "forza bruta" , diciamo non elegante. Volevo chiedere se c'era un metodo (e penso che ci fosse conoscendo le mente brillante del prof. Callegari che ha scritto la gara) magari più rapido con cui risolvere questo esercizio.
PS: Se qualcuno sa se ha un nome (che non sia "Forza bruta") il metodo che ho usato mi farebbe davvero piacere saperlo perché ho visto che riesco a risolvere molti problemi con questo metodo xD
16 esimi GAS '2016 finalmenteeeee! #RovigoPower xD
Corretto un po' il tex .... è meglio usare \bmod per scrivere mod ... e mettere un po' di spazi tra le formule -- EG
Ciao,
il metodo che si usa per risolvere questo problema (come molti del prof.Callegari) si chiama combinatoria ricorsiva, ed effettivamente implica in sé un po' di "forza bruta" perché non fa uso di una formula ma solo di passaggi ripetuti per arrivare al risultato. Ti riporto qui la soluzione che ho trovato in gara (che è poi più o meno la stessa che il prof.Callegari ci ha mostrato alla fine).
Innanzitutto bisogna accorgersi che dalle caselle corrispondenti a $ 1\bmod6 $ e $ 5\bmod6 $ parte lo stesso numero di percorsi lunghi $ n $ (che chiamiamo $ X_{n} $), e così per la coppia $ 2\bmod6 $ - $ 4\bmod6 $ (chiamiamoli $ Y_{n} $, anche se non li utilizzeremo). Infine, chiamiamo $ Z_{n} $ il numero di percorsi lunghi $ n $ che partono da una casella corrispondente a $ 3\bmod6 $.
All'inizio, la pulce si trova su un punto del tipo $ 5\bmod6 $, pertanto può andare o in un punto del tipo $ 0\bmod6 $ (in avanti) o $ 4\bmod6 $ (all'indietro). Cosa succede facendo il secondo passo? Se il primo passo è su una casella multipla di 6, il secondo passo porterà obbligatoriamente avanti, e dunque ad una casella del tipo $ 1\bmod6 $. Invece, se il primo passo era all'indietro, il secondo passo potrà riportare sulla casella iniziale ($ 5\bmod6 $) o potrà andare ancora indietro ($ 3\bmod6 $). Da questi dati, otteniamo la seguente relazione:
$ X_{n} $=$ 2X_{n-2} $+$ Z_{n-2} $
Analogamente, partendo da un punto del tipo $ 3\bmod6 $, il primo passo può portare o a $ 2\bmod6 $ o a $ 4\bmod6 $, che essendo equivalenti portano col secondo passe entrambe o a una casella del tipo $ 3\bmod6 $ o $ 1\bmod6 $. Quindi:
$ Z_{n} $=$ 2X_{n-2}+2Z_{n-2} $
Dato ciò, calcoliamo alcuni valori "di partenza", ossia $ X_{1}=2 $, $ Z_{1}=2 $ (ossia: i percorsi lunghi $ 1 $ che partono da una di queste caselle sono $ 2 $, uno che porta in avanti e uno che porta indietro). Da qui, possiamo trovare $ X_{15} $ usando le due formule di cui sopra (riporto solo i risultati):
finalmenteeeee! #RovigoPower xD