OliForum Matematico

Ciao a tutti! Allenandomi per febbraio, mi sono imbattuto nel problema numero 11 del Febbraio 2002. Ecco come recita il testo:

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!!

Gauss91 ha scritto:Ogni unione (di due singoli pezzi, di due gruppi, di un gruppo a un pezzo) conta una mossa.

I quattro pezzi disposti intorno a quello che vuoi inserire contano come gruppo? Allora, nel metterli a croce hai fatto 3 mosse per unirli (anche se non sono fisicamente attaccati), +1 per mettere il centrale, 4.
I quattro pezzi non contano come gruppo? Nell'inserire il pezzo centrale, lo unisci a quattro pezzi singoli, e quindi fai 4 mosse.

Ti faccio infine notare, che se si usa la tua tecnica e le tue regole, 250 è un risultato esageratamente grosso, si può fare con molto meno.
Disponi 500 pezzi a scacchiera, gli altri 500 anche loro a scacchiera, e unisci il tutto con una mossa sola.

beh un puzzle è classicamente formato da pezzi rettangolari che diconsi UNITI quando hanno un lato in comune, non un vertice (non ho mai visto puzzle così neanke nei problemi matematici)
Detto così, i pezzi del + non sono uniti fra loro se non fino a quando ci metto quello in mezzo, e quindi NON contano come gruppo (e l'esempio della scacchiera non funziona i pezzi attaccati per un vertice non sono uniti, quindi non si possono assolutamente unire tutti con una mossa sola). Anche se possono essere meno di 250, sicuramente non 999.
Invece sn d'accordo con il fatto che effetticamente anche se fisicamente faccio una mossa sola, ne faccio in realtà 4 perché unisco il pezzo ad altri 4 che sono accanto, però ciò si basa su una sottile interpretazione del testo che non dovrebbe esserci in quanto un buon requisito per un problema olimpico deve essere la chiarezza. O sbaglio su qualche punto?

A me il testo sembrava più che chiaro... Hanno anche scritto l'elenco dei casi fra parentesi che ho quotato prima per togliere ogni dubbio. Il caso "una mossa può anche essere il collegare un singolo pezzo a più gruppi contemporaneamente" non è in quell'elenco. Tutto ciò che era necessario era presente nel testo, per qualcosa di ancora più chiaro si poteva mettere solo un'impostazione assiomatica dell'esercizio, il che mi pare un po' eccessivo, no?

capisco... beh, se nn altro, ho imparato ancora di più a leggere il testo di un esercizio quindi in sostanza lo prendo cm un arricchimento!
Grazie della disponibilità, alla prossima!