un puzzle da 1000 pezzi può essere montato incastrando i pezzi uno dopo l'altro, in modo da inserire ciascun nuovo pezzo nella porzione di puzzle già composta, oppure costruendo diversi gruppi di pezzi e poi unendo questi tra loro. Ogni unione (di due singoli pezzi, di due gruppi, di un gruppo a un pezzo) conta una mossa. Qual è il numero minimo di mosse necessarie per completare il puzzle?
La soluzione "ufficiale" dice che sono 999, dato che si dimostra per induzione che per costruire un gruppo da n pezzi servono n-1 mosse. Tuttavia io ho trovato 250, ecco come.
Non essendo posta alcuna condizione sulla forma del puzzle, si immagini un gruppo costituito da una croce a "+" composta da 5 pezzi (4 laterali e uno centrale). Per costruire questo gruppo occorre solo 1 mossa: basta infatti mettere prima quelli laterali (che, non essendo uniti, non contano come mossa) e poi unirli in un colpo solo con quello centrale. costruendo poi altri 3 "+" ad un lato di quello iniziale in modo da formare un "+ gigante", e unendo poi questi 4 "+" con un pezzo, si ha che al gruppo originario se n'è aggiunto un altro di 16 pezzi con 4 mosse.
Continuando con lo stesso procedimento (16 pezzi in 4 mosse) dopo 248 mosse saranno stati assemblati 992 pezzi. I cinque della mossa iniziale portano i pezzi a 997 e le mosse a 249. A questo punto, è facile vedere che una mossa sola basta per assemblare i 3 finali. Totale: 250 mosse.
Siccome la soluzione ufficiale è di 999, presumo che abbia sbagliato, ma non riesco a capire dove. Se riusciste a darmi una spiegazione, ve ne sarei molto grato!
Ciao!!
