Monete e quadrati - generalizzazione
Inviato: 12 lug 2009, 21:53
Propongo una specie di generalizzazione di un shortlist IMO del 1996, che è stato discusso qui.
Abbiamo un insieme $ $C $ di caselle (anche infinito), e su ogni casella abbiamo piazzato un certo numero di monete (anche 0).
Sono definite due funzioni: $ $f: C\rightarrow \mathbb N $ e $ $g: C^2\rightarrow \mathbb N $, con $ $g(c,c)=0 $.
Una mossa consiste nello scegliere una casella $ $c\in C $ contenente almeno $ $f(c) $ monete, togliere da essa $ $f(c) $ monete, ed aggiungere $ $g(c,c') $ monete ad ogni casella $ $c'\in C $.
Una partita è una sequenza massimale di mosse (ovvero una sequenza di mosse che non può essere "continuata").
Dimostrare che, fissata la configurazione di monete iniziale, o tutte le partite sono infinite, oppure sono tutte finite, hanno tutte la stessa lunghezza (in numero di mosse), e terminano tutte nella stessa configurazione finale.
Bonus: determinare qualche condizione non banale su f, g e sulla configurazione iniziale, affinché le partite terminino. Possibilmente, che estenda la condizione del problema IMO originario.
Sul bonus vedete voi, io non ci ho ancora pensato.
Abbiamo un insieme $ $C $ di caselle (anche infinito), e su ogni casella abbiamo piazzato un certo numero di monete (anche 0).
Sono definite due funzioni: $ $f: C\rightarrow \mathbb N $ e $ $g: C^2\rightarrow \mathbb N $, con $ $g(c,c)=0 $.
Una mossa consiste nello scegliere una casella $ $c\in C $ contenente almeno $ $f(c) $ monete, togliere da essa $ $f(c) $ monete, ed aggiungere $ $g(c,c') $ monete ad ogni casella $ $c'\in C $.
Una partita è una sequenza massimale di mosse (ovvero una sequenza di mosse che non può essere "continuata").
Dimostrare che, fissata la configurazione di monete iniziale, o tutte le partite sono infinite, oppure sono tutte finite, hanno tutte la stessa lunghezza (in numero di mosse), e terminano tutte nella stessa configurazione finale.
Bonus: determinare qualche condizione non banale su f, g e sulla configurazione iniziale, affinché le partite terminino. Possibilmente, che estenda la condizione del problema IMO originario.
Sul bonus vedete voi, io non ci ho ancora pensato.