IMO 2015 - 6

[Nemo]

La successione di interi $(a_1,a_2,\dots)$ soddisfa le seguenti condizioni:
(I) $1\le a_j\le 2015$ per qualsiasi $j\ge1$,
(II) $k+a_k\neq \ell +a_\ell$ per qualsiasi $1\le k<\ell$.

Dimostrare che esistono due interi positivi $b$ e $N$ per i quali
$$\left \vert \sum_{j=m+1}^n (a_j-b)\right \vert \le 1007^2 $$
per tutti gli interi $m$ ed $n$ tali che $n>m\ge N$.

[fph]

Non ho visto la soluzione, ma ho notato ora alcune interessanti connessioni con

Testo nascosto:

una notazione usata per la giocolieria (siteswap)...

a questo punto scommetterei una birra che chi l'ha proposto è

Testo nascosto:

un giocoliere.

EDIT: ho scritto qualcosa di più su questo argomento su AOPS.

[Federico II]

Rispolveriamo questo topic con la mia soluzione:

Testo nascosto:

Immaginiamo di avere una scala con $2015$ gradini numerati da $1$ a $2015$ dal più basso al più alto. Sui gradini della scala rimbalzano alcuni palloni, scendendo tutti alla velocità di un gradino al secondo e rimbalzando tutti su un gradino ogni volta nello stesso istante. I palloni che scendono dal gradino $1$ non verranno più considerati (sono fuori dalla scala). Ogni secondo al momento in cui i palloni rimbalzano un erogatore automatico getta un pallone sul gradino $2015$ (che prima era vuoto perché i palloni sono tutti scesi di un gradino dalla posizione precedente, quindi nessuno può trovarsi sul gradino più alto) e un giocatore toglie dalla scala un pallone a sua scelta (eventualmente anche quello appena aggiunto dall'erogatore automatico). All'inizio tutti i gradini contengono un pallone. Dimostriamo che comunque sia data una sequenza $a_1,a_2,\ldots$ che rispetta le ipotesi essa corrisponde ad una sequenza di mosse del giocatore, ovvero che il giocatore può effettuare mosse in modo tale che per ogni $i\in\mathbb{Z^+}$ il pallone che toglie dalla scala $i$ secondi dopo l'istante iniziale si trovava sul gradino $a_i$. Dimostriamolo per induzione su $i$. Per $i=1$ (passo base) basta notare che al secondo $1$ prima che il giocatore tolga il pallone a sua scelta ogni gradino contiene un pallone, perché i palloni che all'inizio erano in $2,3,\ldots,2015$ ora sono in $1,2,\ldots,2014$, e l'erogatore automatico ha aggiunto un pallone in $2015$. Quindi il gradino $a_1$ contiene un pallone (per ipotesi $1\leq a_1\leq2015$, in seguito nella dimostrazione daremo per scontato questo fatto) e il giocatore può togliere tale pallone dalla scala. Per il passo induttivo, supponiamo che il giocatore abbia fatto le prime $i-1$ mosse ($i\geq2$) in modo tale da togliere il pallone che si trovava sul gradino $a_r$ per ogni intero $r$ con $1\leq r<i$, e dimostriamo che al secondo $i$ si trova un pallone sul gradino $a_i$, così il giocatore può togliere tale pallone. Se $2015-a_i<i$, notiamo che al secondo $i-2015+a_i$ un pallone si trovava sul gradino $2015$ (perché ce l'ha messo l'erogatore automatico). Dal secondo $i-2015+a_i$ al secondo $i$ sono passati $i-\left(i-2015+a_i\right)=2015-a_i$ secondi. Pertanto il pallone che si trovava in $2015$ ora si trova in $2015-\left(2015-a_i\right)=a_i$, quindi il gradino $a_i$ contiene un pallone, come volevamo, a meno che tale pallone non sia stato tolto in precedenza dal giocatore. Se però al secondo $s$ con $i-2015+a_i\leq s<i$ il giocatore ha tolto il pallone, visto che in tale istante si trovava sul gradino $2015-\left(s-i+2015-a_i\right)=a_i+i-s$ e il giocatore in tutti i secondi $r<i$ ha tolto il pallone che si trovava in $a_r$, ponendo $r=s$ si ottiene che $a_s=a_i+i-s$, quindi $a_s+s=a_i+i$, il che contraddice la seconda ipotesi, quindi il pallone non era mai stato tolto e al secondo $i$ si trova proprio in $a_i$, come voluto. Se $a_i=2015$ questa dimostrazione non funziona, ma la presenza di un pallone in $2015$ ci è assicurata dall'erogatore automatico. Resta però il caso $2015-a_i\geq i$, ovvero $a_i+i\leq2015$. In questo caso osserviamo che all'istante iniziale c'era un pallone in $a_i+i$ (che è compreso tra $1$ e $2015$). Al secondo $i$ tale pallone si trova in $a_i+i-i=a_i$, quindi il giocatore può toglierlo, a meno che quel pallone non sia già stato tolto in precedenza dal giocatore. Come per il caso precedente, se al secondo $s<i$ il giocatore lo aveva tolto ne segue che $a_s=a_i+i-s$ (al secondo $s$ il pallone si trovava sul gradino $a_i+i-s$), quindi $a_s+s=a_i+i$, contro la seconda ipotesi. Quindi il pallone non era stato tolto, e questo conclude la dimostrazione del passo induttivo. Possiamo dunque affermare con certezza che comunque sia data una sequenza $a_1,a_2,\ldots$ che rispetta le ipotesi essa corrisponde ad una sequenza di mosse del giocatore, ovvero che il giocatore può effettuare mosse in modo tale che per ogni $i\in\mathbb{Z^+}$ il pallone che toglie dalla scala $i$ secondi dopo l'istante iniziale si trovava sul gradino $a_i$. Esaminiamo un gioco infinito che si svolga in questo modo (abbiamo dimostrato che esiste). Osserviamo che il numero $P$ di palloni sulla scala subito dopo la mossa del giocatore non può mai diminuire, perché ogni secondo si aggiunge uno e un solo pallone (dall'erogatore automatico) e se ne toglie almeno uno (sicuramente quello che toglie il giocatore, più eventualmente un pallone che cade dal gradino $1$. $P$ al secondo $1$ vale $2014$ (un pallone per gradino, meno quello tolto dal giocatore al secondo $1$). Ovviamente $P$ non può mai essere negativo. Visto che il gioco si protrae all'infinito e $P$ parte da $2014$, non aumenta mai e non scende mai sotto lo $0$, da un certo punto in poi deve assumere sempre lo stesso valore. Sia $c$ questo valore, per quanto abbiamo detto $0\leq c\leq2014$. Scegliamo $b=2015-c$ e definiamo $N$ come il primo istante di tempo (in secondi) in cui $P=c$. Per ogni scelta degli interi $m,n$ con $n>m\geq N$ dimostriamo quindi la tesi, ovvero che
$$\left\vert\sum_{j=m+1}^{n}{\left(a_j-b\right)}\right\vert\leq1007^2.$$
Per ogni $d\geq N$, sia $Q_d$ la somma delle posizioni dei $c$ palloni dopo $d$ secondi e dopo la mossa del giocatore. Dimostriamo, per induzione su $n$, che
$$\sum_{j=m+1}^{n}{\left(a_j-b\right)}=Q_m-Q_n.$$
Il passo base ($n=m$) è banale perché la sommatoria è vuota e vale $0$ e $Q_m-Q_n=Q_m-Q_m=0$. Per il passo induttivo supponiamo vera l'uguaglianza per un certo valore di $n$ e dimostriamola per $n+1$. Abbiamo:
$$\sum_{j=m+1}^{n+1}{\left(a_j-b\right)}=\sum_{j=m+1}^{n}{\left(a_j-b\right)}+a_{n+1}-b=Q_m-Q_n+a_{n+1}-2015+c=Q_m-Q_{n+1},$$
come voluto. La seconda uguaglianza si giustifica con i seguenti fatti: $\sum_{j=m+1}^{n}{\left(a_j-b\right)}=Q_m-Q_n$ per ipotesi induttiva, $b=2015-c$ per come l'abbiamo definito. La terza uguaglianza si giustifica con il fatto che $Q_{n+1}=Q_n-a_{n+1}+2015-c$ perché dal secondo $n$ al secondo $n+1$ i $c$ palloni scendono di un gradino, quindi la somma delle posizioni diminuisce di $c$, l'erogatore automatico aggiunge un pallone sul gradino $2015$, quindi la somma aumenta di $2015$, e il gocatore toglie il pallone sul gradino $a_{n-1}$, quindi la somma diminuisce di $a_{n-1}$. Nessun pallone cade dal gradino $1$ erché altrimenti il numero $P$ di palloni diminuirebbe, mentre invece resta costante. Da ciò che abbiamo dimostrato segue quindi che
$$\left\vert\sum_{j=m+1}^{n}{\left(a_j-b\right)}\right\vert=\left\vert Q_m-Q_n\right\vert.$$
La tesi si riduce quindi a $\left\vert Q_m-Q_n\right\vert\leq1007^2$. Senza perdita di generalità possiamo supporre $Q_m\geq Q_n$ (nell'altro caso la dimostrazione è analoga). La tesi si riduce allora a $Q_m-Q_n\leq1007^2$. Visto che ci può essere al massimo un pallone per ogni gradino, il valore di $Q_m$ non può superare $\sum_{i=1}^{c}{\left(2016-i\right)}$ e il valore di $Q_n$ non può essere minore di $\sum_{i=1}^{c}{\left(i+1\right)}$, dal momento che il gradino $1$ deve essere vuoto perché altrimenti il pallone cadrebbe dalla scala e $P$ diminuirebbe. Ne segue che:
$$Q_m-Q_n\leq\sum_{i=1}^{c}{\left(2016-i\right)}-\sum_{i=1}^{c}{\left(i+1\right)}=\sum_{i=1}^{c}{\left(2015-2i\right)}=2015c-2\sum_{i=1}^{c}{i}=2015c-c\left(c+1\right)=c\left(2014-c\right)\leq1007^2,$$
dove l'ultima disuguaglianza segue da $AM-GM$ su $\left(c,2014-c\right)$: si ha $\sqrt{c\left(2014-c\right)}\leq\frac{c+2014-c}{2}=\frac{2014}{2}=1007$, da cui $c\left(2014-c\right)\leq1007^2$. La tesi è dimostrata.

Carina? (e soprattutto, corretta?)
PS:

Testo nascosto:

Quanto è lecito in gara presentare una dimostrazione del genere, con palloni che rimbalzano giù da una scala?

PPS: Perché in TdN?

[fph]

Quanto è lecito in gara presentare una dimostrazione del genere, con palloni che rimbalzano giù da una scala?

È lecito; anche perché il problema sembrava chiamare un'interpretazione del genere, è qualcosa di simile a quello che ho fatto io e l'ho vista fare anche ad altre persone. Se vuoi renderla più formale (ma secondo me va bene anche così), un modo che mi viene in mente (ma non ho provato a portarlo fino in fondo) è

Testo nascosto:

definire una funzione "energia potenziale" di un possibile stato dei palloni in funzione delle loro altezze, vedere come varia lungo il tempo e quali sono il suo minimo e massimo. A questo punto probabilmente si possono spazzare via i palloni sotto il tappeto e vedere tutto come manipolazione formale di questa funzione E().

[Federico II]

Testo nascosto:

La tua $E$ mi sembra corrisponda alla mia $Q$, non capisco bene come la definiresti senza introdurre i palloni e il tempo, comunque penso che ogni soluzione corretta debba dare il massimo, poi non so se e perché la giuria potrebbe non considerarla formale...

[fph]

Uhm sì hai ragione, sorry, a un certo punto ho scorso tutto solo di fretta e mi è sfuggito che già lo introduci. :/

Testo nascosto:

Sì, alla fine per definire questa energia alla fine quello che ti serve è avere uno stato, che è un sottoinsieme di $b$ elementi di 1...2015, e dire come evolve nel tempo. Puoi chiamarlo "posizioni occupate dai palloni", oppure se vuoi offuscare le cose puoi solo chiamarlo "stato" e manipolarlo formalmente, ma mi rendo conto che è solo un esercizio di stile.

In ogni caso, il problema di scrivere le cose affidandosi a queste metafore è che si rischia di lasciare non dimostrato qualcosa che magari sembra intuitivo nella nostra interpretazione ma che è fondamentale avere chiaro in testa e scrivere per bene, perché è quello che i correttori cercano per darti il -1, o magari anche il -2 o -3 se è davvero un punto cruciale e meno banale. Nel tuo caso mi sembra che tu abbia scritto tutto; punti che avresti potuto dimenticare sono cose del tipo

Testo nascosto:

"perché il numero di palloni è costante" (è un punto delicato perché potrebbe diminuire all'inizio), o "perché i palloni non cozzano mai l'uno con l'altro" (è importante perché è il punto dove usi un'ipotesi --- un ottimo check mentale è che se non stai usando mai un'ipotesi c'è qualcosa che non va). Oppure un altro problema possibile poteva essere nel dimostrare la disuguaglianza finale fare magari qualche ragionamento che smette di funzionare se 2015-2i diventa negativo -- la tua versione mi sembra pulita però.

. Non ero in Tailandia a correggere questo esercizio, ma ad occhio quelle che ti ho scritto mi sembrano le cause più probabili per un -1.

(Incidentalmente: chiedersi "come valuterei questo esercizio se fossi il correttore" è un buon esercizio per abituarsi a capire quali sono i punti sottili ma che rischiano di valere un -1. Per vedere degli esempi, i marking schemes dei dimostrativi di Febbraio, per esempio, sono pubblicati insieme alle soluzioni.)

[Federico II]

Testo nascosto:

Il numero di palloni non è costante, ma non aumenta mai, può solo diminuire e non diventa mai negativo, quindi da un certo punto in poi è costante. I palloni non cozzano mai l'uno contro l'altro perché ho specificato all'inizio che scendono tutti alla velocità costante di un gradino al secondo e ho dimostrato che al momento in cui ne viene sputato uno dall'erogatore automatico il gradino più alto è vuoto. Per quanto mi riguarda $2015-2i$ può anche diventare negativo (e in effetti in alcuni casi lo diventa), semplicemente sommo qualcosa di negativo. Poi potrei anche tradurre lo stato dei palloni in un sottoinsieme che varia, ma sicuramente richiederebbe molto più tempo e attenzione scrivere la soluzione, cose che uno di solito non ha quando alle IMO il tempo sta per finire (sempre se non è già finito con gli altri due problemi, quest'anno il 5 era molto rognoso, quindi forse nemmeno avrei avuto il tempo di iniziare a pensarci a questo). Comunque se fossi un correttore non vedo un motivo per mettere il -1, tu lo vedi?

[fph]

Sìsì mi è chiaro che tu hai capito, e secondo me la tua soluzione è da 7. Ti sto solo elencando quali sono i dettagli dove si possono perdere punti, in generale. Secondo me è utile avere un'idea di come lavora la mente del correttore e cosa va a cercare che sia scritto bene in una soluzione.