OliForum Matematico

Prendiamo gli interi da 1 a 20 e li scriviamo su una lavagna. Presi due di essi, detti a e b, tali che a-b>1, li sostituiamo con a-1 e b+1. Quante volte al massimo possiamo fare questa sostituzione?
(Yudi Satria,Jakarta)

jordan ha scritto:Prendiamo gli interi da 1 a 20 e li scriviamo su una lavagna. Presi due di essi, detti a e b, tali che a-b>1, li sostituiamo con a-1 e b+1. Quante volte al massimo possiamo fare questa sostituzione?
(Yudi Satria,Jakarta)

Ad occhio direi che se prendiamo $ a=20 $ e $ b=1 $,il passaggio sarà stato fatto $ $8 $ volte.

Ok quindi volendo hai visto che il massimo numero di volte che puoi farlo è almeno 8. Ma questo non dimostra che è il massimo, e infatti non lo è.

Proviam.

Non è più possibile fare mosse quando presi (a,b) qualunque non vale mai (a-b)>1; e questo succede quando tutti i numeri sono uguali, oppure quando tutti i numeri sono pari a due interi consecutivi.

Notato che la somma di tutti i numeri è un invariante del problema (qui è ½(20)(21) = 210), si vede che a) non possiamo arrivare ad avere tutti numeri uguali, dato che 20 non divide 210 b) la configurazione finale che preserva la somma totale e presenta solo due numeri consecutivi è quella con 10 dieci e 10 undici.

Per massimizzare le mosse portiamo ad 11 tutti i numeri minori o uguali a 10, e viceversa. Per l'1 ed il 20 servono 10 mosse, per il 2 ed il 19 ne servono 9, ecc...

Il numero massimo di mosse è quindi pari a 10+9+8+...+1 = 55

Cosi non dimostri che è il massimo , ma come karlosson solo che è almeno 55 (sebbene almeno tu hai trovato un invariante ). E infatti si può fare ancora meglio..

Per spezzare una lancia a favore di karlosson, dico che secondo me lui ha interpretato il testo come se a e b non potessero cambiare da una mossa all'altra...

Tibor Gallai ha scritto:Per spezzare una lancia a favore di karlosson, dico che secondo me lui ha interpretato il testo come se a e b non potessero cambiare da una mossa all'altra...

Infatti ho interpretato cosi.

Eh, ha interpretato male

Quando lo risolvete, generalizzate astraendo dal 20.
Se capite come dev'essere la sequenza massima, generalizzate facilmente.

Per caso sono 1368 volte?

Ricordo solo le idee della dimostrazione.. sentiamo la tua intanto

No, ho sbagliato. Sono di meno. Però alla fine ho trovato la soluzione. Credo che siano 444 perché avendo 20 e 1 sono 8, 20 e 2 sono 8, 20 e 3 sono 7, 20 e 4 sono 7, 20 e 5 sono 6... 19 e 1 sono 8, 19 e 2 sono 7, 19 e 3 sono 7... fino a dire che 5 e 1 sono 1. Alla fine scriveremo che, avendo $ a=20 $, le possibilità sono 16+14+12+10+8+6+4+2, con $ a=19 $, le possibilità sono 8+14+12+10+8+6+4+2, con $ a=18 $ sono 14+12+10+8+6+4+2, con $ a=17 $ sono 7+12+10+8+6+4+2, fino ad arrivare a dire che con $ a=7 $ le possibilità sono 2+2, con $ a=6 $ sono 2 e con $ a=5 $ sono solo 1. Facendo la somma viene 444, credo. Correggetemi se ho sbagliato qualcosa

Scusami, ma non ho capito l'idea che sta dietro ai tuoi calcoli, perché se fai una mossa con il 20 e l'1 poi non puoi più fare quella con il 20 e il 2 (il 20 è irrimediabilmente scomparso).

Provo a scrivere la mia soluzione. Definiamo entropia del sistema di numeri la somma dei quadrati di tutti i numeri scritti. Dimostriamo che l'entropia, diversamente da quanto avviene in termodinamica, diminuisce sempre. Se a>b+1 e opero una mossa su a e b, ottengo una variazione di entropia $ (a-1)^2+(b+1)^2-a^2-b^2=2b+2-2a\leq -2 $. Poichè l'entropia iniziale è $ \sum_{i=1}^20 i^2 =\frac{20\cdot 21\cdot 41}{6}=2870 $ mentre l'entropia finale è $ 10\cdot 10^2+10\cdot 11^2=2210 $, abbiamo una variazione di entropia tra la fine e l'inizio di $ -660 $, e siccome ad ogni mossa l'entropia diminuisce almeno di 2, possiamo concludere che si possono fare al massimo 330 mosse. Purtroppo ci si accorge presto che 330 sono ancora troppe! Forse con un'altra entropia si riesce a concludere.