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)
20 numeri sulla lavagna
20 numeri sulla lavagna
The only goal of science is the honor of the human spirit.
-
karlosson_sul_tetto
- Messaggi: 1459
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: 20 numeri sulla lavagna
Ad occhio direi che se prendiamo $ a=20 $ e $ b=1 $,il passaggio sarà stato fatto $ $8 $ volte.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)
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
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
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
[i]
Mathematical proofs are like diamonds: hard and clear.
[/i]
Mathematical proofs are like diamonds: hard and clear.
[/i]
). E infatti si può fare ancora meglio..-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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...
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
-
karlosson_sul_tetto
- Messaggi: 1459
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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.
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.
Sono il cuoco della nazionale!