Tavola rotonda

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Tavola rotonda

Messaggio da Euler » 09 gen 2011, 11:13

Ad una tavola rotonda sono seduti $n$ stagisti. Maria, che è la capitana del gruppo, ha $n$ medaglie e vuole distribuirle secondo la regola seguente: ad ogni turno sceglie uno stagista (eventualmente anche se stessa) che ha almeno due medaglie e gli dice di darne una a ciascuno dei suoi vicini.
Determinare per quali valori di $n$ è possibile arrivare alla situazione in cui ogni stagista ha una medaglia.

staffo
Messaggi: 305
Iscritto il: 01 mar 2010, 15:34

Re: Tavola rotonda

Messaggio da staffo » 09 gen 2011, 13:31

Una domanda, ma all'inizio ci sono $ n $ stagisti seduti e, a parte Maria che ha $ n $ medaglie, gli altri non ne hanno nemmeno una?
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]

amatrix92
Messaggi: 818
Iscritto il: 21 nov 2008, 17:19
Località: Firenze

Re: Tavola rotonda

Messaggio da amatrix92 » 09 gen 2011, 13:33

staffo ha scritto:Una domanda, ma all'inizio ci sono $ n $ stagisti seduti e, a parte Maria che ha $ n $ medaglie, gli altri non ne hanno nemmeno una?
A quanto ho capito io no, a me viene per ogni valore dispari di $ n $
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.

staffo
Messaggi: 305
Iscritto il: 01 mar 2010, 15:34

Re: Tavola rotonda

Messaggio da staffo » 09 gen 2011, 13:47

a quanto ho capito io invece sì, e mi viene anche a me $ n $ dispari.

Quando ricevo una conferma riguardo al testo del problema provo a dimostrarlo.
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]

amatrix92
Messaggi: 818
Iscritto il: 21 nov 2008, 17:19
Località: Firenze

Re: Tavola rotonda

Messaggio da amatrix92 » 09 gen 2011, 13:49

Alt, mi sa che ci siamo fraintesi; io intendo che "No, nessun altro stagista possiede inizialemente altre medeglie"
Le parole non colgono il significato segreto, tutto appare un po' diverso quando lo si esprime, un po' falsato, un po' sciocco, sì, e anche questo è bene e mi piace moltissimo, anche con questo sono perfettamente d'accordo, che ciò che è tesoro e saggezza d'un uomo suoni sempre un po' sciocco alle orecchie degli altri.

Claudio.
Messaggi: 695
Iscritto il: 29 nov 2009, 21:34

Re: Tavola rotonda

Messaggio da Claudio. » 09 gen 2011, 13:50

Il testo è chiarissimo, l'unica ad avere medaglie all'inizio è Maria.

staffo
Messaggi: 305
Iscritto il: 01 mar 2010, 15:34

Re: Tavola rotonda

Messaggio da staffo » 09 gen 2011, 14:38

ok amatrix, dicevamo la stessa cosa, il testo in effetti era abbastanza chiaro, dato che se non fosse come è stato detto, non si potrebbe arrivare mai ad avere una medaglia a testa. Però ciò non era detto, e quindi bisognava precisarlo.

Comunque è chiaro che la risposta è le configurazioni dispari.

Se le persone sono pari, partendo da Maria accadrà che, togliendo la persona di fronte a lei, gli altri alla sua destra e quelli alla sua sinistra avranno sempre lo stesso numero di medaglie. Ne consegue che la mossa che dovrebbe chiudere l'assegnazione delle medaglie, dando una e una sola medaglia a Maria, non possa essere fatta; infatti, chiamando A e B le persone a destra e a sinistra di Maria, esse avranno o entrambi 2 o più medaglie, consegnando così due medaglie a Maria, o 1 o 0 medaglie, non consegnando medaglie a Maria (che arriva sempre dopo k mosse a possederne 0).

Se le configurazioni sono dispari, invece, Maria non avrà di fronte nessuno, ma le persone alla sua destra e alla sua sinistra si potranno dividere in due gruppi. Questi due gruppi avranno sempre lo stesso numero di medaglie. Si può notare come in k passi si può sempre fare in modo che tutti abbiano una medaglia. A Maria però, alla fine, rimarrà sempre e solo una medaglia, dato che possedeva un $ n $ dispari di medaglie, e quindi tutti potranno avere una medaglia a testa.

Va bene?
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]

Claudio.
Messaggi: 695
Iscritto il: 29 nov 2009, 21:34

Re: Tavola rotonda

Messaggio da Claudio. » 09 gen 2011, 17:03

No...
Se le persone sono pari, partendo da Maria accadrà che, togliendo la persona di fronte a lei, gli altri alla sua destra e quelli alla sua sinistra avranno sempre lo stesso numero di medaglie
, non è vero.

staffo
Messaggi: 305
Iscritto il: 01 mar 2010, 15:34

Re: Tavola rotonda

Messaggio da staffo » 09 gen 2011, 17:15

come fai a dire che non è vero, io intendo per "avranno sempre lo stesso numero di medaglie" che il primo a destra di Maria avrà lo stesso numero di medaglie del primo a sinistra di Maria, il secondo a destra di Maria avrà lo stesso numero di medaglie del secondo alla sua sinistra, .....

e questo è vero per forza, se no andrebbe contro la regola che lo stagista selezionato dia una medaglia contemporaneamente a quello alla sua destra e a quello alla sua sinistra.
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Re: Tavola rotonda

Messaggio da Euler » 09 gen 2011, 17:35

La soluzione è chiaramente giusta, ma il procedimento è sbagliato. Quando hai detto che quelli a destra hanno lo stesso numero di quelli a sinistra penso che non hai considerato le mosse oltre a quelle di Maria, almeno da quello che ho capito...non potresti spiegare meglio, che magari mi è sfuggito qualcosa?
Nel caso dispari invece dovresti esplicitare l'algoritmo, ma visto che hai usato lo stesso lemma penso sia sbagliato.

paga92aren
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: Tavola rotonda

Messaggio da paga92aren » 09 gen 2011, 17:39

Sul risultato ci siamo ora scrivo la mia dimostrazione (la nascondo se qualcuno vuole provare per conto suo:
1) non è possibile per $n$ pari:
Testo nascosto:
Cerco l'invariante: il peso delle monete
Numerando i posti da $0$ a $n-1$ partendo da Maria in senso orario il peso di una moneta è il numero associato al posto in cui si trova.
Il peso totale non cambia (modulo $n$) facendo la mossa, infatti se una moneta scende di 1 un'altra aumenta di 1 (caso particolare se passo dal vertice $0$ al vertice $n-1$, in cui il peso aumenta di $n$).
Scrivo il valore del peso delle monete all'inizio e alla fine: $P_i=0\cdot n=0$ e $P_f=1+2+\dots+(n-1)=\frac{n(n-1)}{2}$ e li impongo uguali modulo $n$
Il peso finale è congruo a zero se e solo se $\frac{n-1}{2}$ è intero quindi per $n$ dispari.
2) trovo un esempio per $n$ dispari:
Testo nascosto:
Prendo in esame una serie di posti consecutivi tali che il posto centrale ha tante medaglie, $k$ posti a destra e a sinistra hanno una sola medaglia e tutti gli altri non hanno medaglie.
Voglio dimostrare che è possibile riottenere la stessa configurazione con due medaglie in meno nel vertice centrale e con $k+1$ al posto di $k$.

COMBO 1: dalla situazione sopra descritta scambia lo zero e l'uno vicini (es ...-1-1-0-0-0... diventa ...-1-0-1-0-0-...) e funziona così:
Applico la mossa al posto centrale in modo tale da avere nei posti laterali due medaglie, poi applico la mossa sui posti laterali e ottengo un posto vuoto seguito da uno da due monete. Riapplicando la mossa sulla pila da due ho l'effetto di spostare la serie 0-2 sempre più ai lati fino all'ultimo posto, rimane ai lati la sequenza ...-1-1-0-1con l'ultimo uno nella posizione $k+1$.

COMBO 2: Dalla situazione sopra citata applico $k$ volte la combo 1 scambiando due zeri con gli uno più interni fino a quando i due zeri non sono vicini al posto centrale (0-0-1-1..-1-0-M-0-1-...-1-1-0-0). Infine applico la mossa al posto centrale e ottengo la situazione iniziale con $k+1$ al posto di $k$.

Nella nostra tavola di $n=2a+1$ persone prendo come posto centrale quello di Maria e applicando la combo 2 $a$ volte (la prima con $k=0$ poi con $k=1$ e così via) riesco a distribuire una medaglia per persona (eccetto a Maria). Quante medaglie rimangono a Maria? dato che $2a$ medaglie sono in giro allora le rimane una sola medaglia.
Spero di essere stato chiaro e di non aver fatto errori.

Claudio.
Messaggi: 695
Iscritto il: 29 nov 2009, 21:34

Re: Tavola rotonda

Messaggio da Claudio. » 09 gen 2011, 17:52

Figo...però un piccolo errore l'hai fatto, il non aver considerato a parte il caso n=2, che è effettivamente soluzione :P

staffo
Messaggi: 305
Iscritto il: 01 mar 2010, 15:34

Re: Tavola rotonda

Messaggio da staffo » 09 gen 2011, 18:17

il caso n=2 non è soluzione, perchè io do due monete all'altro (che si trova sia a sinistra che a destra di me).

per le mosse sì, ho commesso un errore, perchè consideravo due mosse in contemporanea, quindi ho sbagliato.
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Re: Tavola rotonda

Messaggio da Euler » 09 gen 2011, 18:18

Io, a differenza di paga92aren, mi sono costruito l'algoritmo al contrario, cioè dalla situazione di tutti uni a quella con n e zeri (quindi ad ogni mossa prendo 2 che distano 2 e, se hanno entrambi medaglie, le danno a quello al centro) e continuavo a fare la mossa a partire da uno e andando sempre in senso antiorario finchè potevo, e poi ricominciando il giro. Alla fine dovrei ottenere sempre una cosa simmetrica con gli estremi che diminuiscono strettamente ogni volta, fino a quella centrale. Perdonate la mancanza di chiarezza :oops: , comunque da quello che ho capito è proprio la soluzione di paga al contrario :lol:
Se n era congruo a 2 mod 4 si poteva colorare con 2 colori in modo che vicini avessero colori diversi, da cui si trovava un assurdo mod 4

Claudio.
Messaggi: 695
Iscritto il: 29 nov 2009, 21:34

Re: Tavola rotonda

Messaggio da Claudio. » 09 gen 2011, 18:24

staffo ha scritto:il caso n=2 non è soluzione, perchè io do due monete all'altro (che si trova sia a sinistra che a destra di me).

per le mosse sì, ho commesso un errore, perchè consideravo due mosse in contemporanea, quindi ho sbagliato.
Se magari leggessi il testo c'è scritto che deve dare UNA moneta alle persone sedute accanto a lei, non dice una a destra e una a sinistra o cose del genere, n=2 è una banalissima soluzione.

Rispondi