preIMO c5

[ledzep92]

Indichiamo con V1, V2, . . . , Vn i vertici di un n-agono regolare. Inizialmente in ogni
vertice Vk c’`e una pila di k monete. Successivamente, ad ogni passo `e possibile scegliere
2 qualunque monete (nella stessa pila oppure in pile diverse) e spostarle in un vertice
adiacente a quello in cui si trovano, una in senso orario, ed una in senso antiorario.
Determinare per quali valori di n `e possibile giungere alla configurazione in cui in ogni
vertice Vk ci sono esattamente (n + 1 − k) monete.

Qualcuno che l'abbia risolto mi spiega ,quando stiamo cercando di trovare il caso che verifica l'invariante, perche la moneta che si muove in senso antiorario finisce al posto giusto? grazie

[Tibor Gallai]

Qualcuno che l'abbia risolto mi spiega ,quando stiamo cercando di trovare il caso che verifica l'invariante, perche la moneta che si muove in senso antiorario finisce al posto giusto? grazie

Eh? Ho l'impressione che tu faccia riferimento a del materiale che non stai citando. Ad esempio un video/articolo/thread con una soluzione che non riesci a capire.

Allora le cose sono due: o linki quel materiale, o esponi umanamente la tua domanda.

[Tibor Gallai]

Ok, ho trovato il video, per la cronaca era questo:
http://olimpiadi.dm.unibo.it/videolezio ... _10_CP.avi

Allora, posto che non sei obbligato a risolverlo copiando spudoratamente dal video, ma puoi anche metterci del tuo... Ed anzi sei incoraggiato a farlo (assumendo che ti stia preparando per il prossimo stage)... Provo a metterti sulla strada giusta per capire la storia dell'invariante senza sbrodolarti la dimostrazione, onde evitare che la scopiazzi pari pari.

Suppongo che l'invariante in sé sia chiaro: cioè, fissato n, quella somma modulo n non varia tra una mossa e l'altra. Adesso immagina questo: conosci la posizione iniziale delle monete, e ti è data una posizione finale dopo un certo numero di mosse, in cui però c'è una moneta "invisibile", che non sai dove sia. Riesci ad indovinare la posizione della moneta invisibile? Sì, come? Nota che, variando la posizione della moneta invisibile negli n modi possibili, ottieni una ed una sola volta tutti i resti modulo n. Poiché questo contributo va sommato al contributo delle altre monete della configurazione finale per ottenere l'invariante finale, segue che c'è uno ed un solo modo di piazzare questa moneta per far sì che il valore dell'invariante sia lo stesso di quello iniziale, modulo n.
Osserva ora che questo "lemma" implica che la monetina che va in senso antiorario si ritroverà alla fine nella posizione giusta, grazie al modo in cui hai scelto n.

[ledzep92]

scusa ma ero via e non ho potuto rispondere!
Ebbene si mi sto preparando per lo stage come era facilmente prevedibile.. Ora è tutto chiaro! grazie della spiegazione cerchero di non scopiazzare troppo!