Una scatola di fiammiferi

[franco]

Una scatola contiene 2023 fiammiferi.
Il gioco consiste nel toglierli rispettando, dalla prima all'ultima mossa, la seguente regola: alla prima mossa si prende un solo fiammifero; per tutte le mosse successive bisogna prendere un fiammifero in più o uno in meno rispetto alla mossa precedente, ma prendendone comunque almeno uno.
Quante mosse servono, come minimo, per svuotare la scatola?

ciao

Franco

www.diophante.fr
E6937 (problema proposto da Augustin Genoud)


Une boîte contient 2023 allumettes.
Le jeu consiste à les sortir en respectant la règle suivante du premier au dernier coup : au premier coup, il faut prendre une seule allumette ; à tous les coups suivants, il faut prendre une allumette en plus ou en moins que le coup précédent, mais il faut sortir au minimum une allumette.
Combien faut-il de coups, au minimum, pour sortir toutes les allumettes ?

[Maurizio59]

Servono almeno 65 mosse.

[franco]

Servono almeno 65 mosse.

Sicuramente con meno di 65 mosse non si può fare.
Però non è detto che 65 siano sufficienti ...

Io non ho provato a risolverlo analiticamente (ancora non riesco a capire come prenderlo); andando per "tentativi ragionati" sono riuscito a completare il gioco in 69 mosse ma è possibilissimo si possa fare di meglio.

[Maurizio59]

Sicuramente con meno di 65 mosse non si può fare.
Però non è detto che 65 siano sufficienti ...

E' evidente che per minimizzare il numero di mosse bisogna ridurre al minimo i numeri "discendenti".
Consideriamo la sequenza con un unico numero discendente:
$S= 1+2+3+4+...+m+(m-1)+(m)+ (m+1)+(m+2)+...+n$
La somma è: $S= n(n+1)/2 +2m-1$
Se n = 63 essa diventa $S= 2015+2m$ per cui si ha m = 4.
La sequenza, formata da 65 numeri, è perciò:
$1+2+3+4+3+4+5+6+7+...+ 63$.
Dimostrare che la sequenza non può essere formata da 64 numeri non è semplicissimo.

[franco]

Sicuramente con meno di 65 mosse non si può fare.
Però non è detto che 65 siano sufficienti ...

E' evidente che per minimizzare il numero di mosse bisogna ridurre al minimo i numeri "discendenti".
Consideriamo la sequenza con un unico numero discendente:
$S= 1+2+3+4+...+m+(m-1)+(m)+ (m+1)+(m+2)+...+n$
La somma è: $S= n(n+1)/2 +2m-1$
Se n = 63 essa diventa $S= 2015+2m$ per cui si ha m = 4.
La sequenza, formata da 65 numeri, è perciò:
$1+2+3+4+3+4+5+6+7+...+ 63$.
Dimostrare che la sequenza non può essere formata da 64 numeri non è semplicissimo.

Con 63 mosse evidentemente non è possibile perchè $S=1+2+3+...+63=2016<2023$
Quindi bisogna fare almeno una mossa in diminuzione e quindi un minimo di 64 mosse.

Facendone solo una, il valore della somma delle 64 mosse risulta (se non ho fatto errori) $S=1950+2x$ dove $x$ ($>2$) è il numero della mossa in diminuzione.
$S$ è sempre pari e non può quindi mai assumere il valore $2023$
Per cui le mosse in diminuzione devono essere almeno due ...

Non penso sia difficile fare un programmino in basic per provare tutte le possibili combinazioni di 2 o 3 mosse in riduzione, però sarebbe più elegante risolverlo senza usare la forza bruta

Come dicevo in precedenza, io ho trovato una sequenza vincente con 4 mosse in riduzione per un totale di 69 mosse.
Le mosse in riduzione sono 19, 20, 22 e 23

[Quelo]

Partiamo da una serie di 63 termini, la somma è 2016
La differenza per arrivare a 2023 è dispari e vale 7
Come mostrato da Maurizio, se usiamo un discendente, aggiungiamo due mosse per un valore di 2n-1, dove n è il termine prima del discendente
La soluzione è una sola, n=4, con 65 mosse

Togliamo il 63, la somma ora vale 1953 e la differenza è 70 e non può essere compensata da un discendente, che apporta un contributo dispari
Con due discendenti avremo un contributo pari, ma anche 4 mosse in più, quindi un totale di 66 mosse
Se sono due discendenti separati avremo 2(m+n-1), se sono consecutivi 4(n-1), ma la sostanza non cambia

Se togliamo anche il 62, l'ultimo termine è il 61 (t), la somma vale 1891 (s), differenza 132 (d), con 2 discendenti (k), 65 mosse (m)
Le soluzioni possibili sono n=34, oppure m+n=67
Esempio:
1+2+...+33+34+33+32+33+34+35+...+61=2023
1+2+...+30+29+30+31+...+36+37+36+37+38+...+61=2023

Togliendo ulteriori termini avremo
t=60, s=1830, d=193, k=3, m=66
t=59, s=1770, d=253, k=3, m=65
t=58, s=1711, d=312, k=4, m=66
t=57, s=1653, d=370, k=4, m=65
t=56, s=1596, d=427, k=5, m=66
t=55, s=1540, d=483, k=5, m=65
t=54, s=1485, d=538, k=6, m=66
t=53, s=1431, d=592, k=6, m=65
t=52, s=1378, d=645, k=7, m=66
t=51, s=1326, d=697, k=7, m=65
t=50, s=1275, d=748, k=8, m=66
t=49, s=1225, d=798, k=8, m=65

Per quanto ho potuto verificare, non si arriva mai a 64

[Gianfranco]

Con 65 mosse si può risolvere.
Ci ho lavorato su ma poi ho visto che la soluzione è già stata postata da Maurizio e completata da Franco e Quelo.
Bravissimi!
---
Qui aggiungo solo qualche precisazione sul fatto che con 64 mosse non si può risolvere.

Uso i numeri triangolari.
64 è un numero pari e il 64° numero triangolare, 2080, è pari.

Se partiamo da 1 e togliamo per 64 volte 1 fiammifero in più della volta precedente, togliamo la seguente serie:
1+2+3+4+5+...+64
La somma è:
64*(64+1)/2 = 2080

Se usiamo un discendente al posto k1, la somma diminuisce di un numero pari:
somma = 2080-2*(64-k1+1)

Se usiamo un altro discendente al posto k2>k1, la somma diminuisce ancora di un numero pari:
somma = 2080-2*(64-k1+1)-2*(64-k2+1)

E così via. Se usiamo n discendenti ai posti kn>...>k2>k1, la somma diminuisce sempre di un numero pari.

Da ciò deriva che partendo da 2080 non si può ottenere 2023 in 64 mosse.
Anzi, non si può ottenere in nessun numero pari di mosse.

Salvo errori & omissioni.

-----
AGGIUNTA
Per trovare la soluzione in 65 mosse con un discendente si può fare così.

1) In 65 mosse senza discendenti si toglierebbero:
somma = 65*(65+1)/2 = 2145 fiammiferi

2) Immaginiamo di usare un discendente al posto k. Allora la somma diventa:
somma = 65*(65+1)/2-2*(65-k+1)

3) Vorremmo che tale somma fosse uguale a 2023.
$\displaystyle \frac{65\, \left( 65+1\right) }{2}-2 \left( -k+65+1\right) =2023$
$\displaystyle 2k+2013 = 2023$
$\displaystyle k = 5$

Ciò significa che nella sequenza di 65 mosse si usa sempre +1 tranne nella quinta mossa in cui si usa -1.
La sequenza dei fiammiferi asportati ad ogni mossa è:
1, 2, 3, 4, 3, 4, 5, ..., 63

Il mio valore k = 5 è equivalente a m = 4 nel metodo usato da Maurizio.