[L07] Non è m$ICA$ $SODDISFACENTE$mente $VARIO$...

[bern1-16-4-13]

Definiamo $VARIO$ ogni insieme di punti nel piano tale che nessuna coppia di punti dell'insieme abbia la stessa ascissa o la stessa ordinata.

Sia $A$ un generico insieme $VARIO$ di $2016$ punti.
Definiamo rettangolo $SODDISFACENTE$ ogni rettangolo con lati paralleli agli assi cartesiani e tale che contenga almeno $2$ elementi di $A$. Definiamo inoltre $ICA$ (i.e. $I$nsieme che $C$opre $A$) ogni insieme di punti disgiunto da $A$, tale che $A$ unito tale insieme formi un insieme $VARIO$ e tale che non esista un rettangolo $SODDISFACENTE$ che non contenga elementi di questo insieme.

$f\left(A\right)$ sarà la cardinalità minima di un insieme $ICA$.


a) Trovare il minimo di $f\left(A\right)$ al variare di $A$.
b) Trovare il massimo di $f\left(A\right)$.

[Federico II]

a)

Testo nascosto:

Il minimo è $2015$.
Se $A=\{(1;1);(3;3);(5,5);\ldots;(4031;4031)\}$ esiste un $ICA$ di $2015$ punti, cioè $\{(2;2);(4;4);(6;6);\ldots;(4030;4030)\}$ (se un rettangolo $SODDISFACENTE$ contiene $(2a-1;2a-1)$ e $(2b-1;2b-1)$ con $a<b$ contiene anche $(2a;2a)$).
D'altra parte $2015$ punti sono sempre necessari, perché ordinando gli elementi di $A$ per ascissa crescente e chiamandoli $A_1,A_2,A_3,\ldots,A_{2016}$ in quest'ordine un $ICA$ deve contenere, per ogni $i$ con $1\leq i\leq2015$, almeno un elemento con ascissa compresa tra quella di $A_i$ e quella di $A_{i+1}$, altrimenti si ottiene un assurdo considerando il rettangolo $SODDISFACENTE$ avente tali punti come vertici opposti, quindi gli elementi dell'$ICA$ sono almeno $2015$ (le loro ascisse non possono coincidere con quelle degli $A_i$ perché altrimenti l'$ICA$ unito con $A$ non sarebbe un insieme $VARIO$).

b)

Testo nascosto:

Il massimo è $3942$.
Disponiamo gli elementi di $A$ sui vertici di una griglia quadrettata, in modo che siano disposti in $(\text{punteggio di bern alle IMO})$ righe e $(\text{punteggio di bern alle IMO}+\text{numero di ori di bern tra IMO e RMM})$ colonne (il prodotto di righe e colonne è $2016$). Disponiamo la griglia sul piano cartesiano leggermente ruotata in senso antiorario (in modo che il primo punto della seconda colonna abbia ascissa maggiore di quella dell'ultimo punto della prima colonna). Costruendo tutti i rettangoli $SODDISFACENTI$ che hanno per vertici opposti due elementi di $A$ che nella griglia sono vertici consecutivi dello stesso quadrato, si nota che tali rettangoli sono tutti disgiunti, quindi dato che ognuno di essi deve contenere almeno un elemento dell'$ICA$ gli elementi dell'$ICA$ devono essere almeno tanti quanti questi rettangoli, cioè almeno $$(\text{punteggio di bern alle IMO})(\text{punteggio di bern alle IMO}+\text{numero di ori di bern tra IMO e RMM}-1)+$$ $$+(\text{punteggio di bern alle IMO}+\text{numero di ori di bern tra IMO e RMM})(\text{punteggio di bern alle IMO}-1)=$$ $$=1974+1968=3942$$ (il primo addendo conta quelli orizzontali, il secondo quelli verticali). Quindi in questo caso $3942$ punti sono necessari.
Dimostriamo ora che $3942$ punti sono sempre sufficienti. Ordinando gli elementi di $A$ per ascissa crescente, sia $a$ la lunghezza della massima sequenza ad ordinata crescente, e $b$ la lunghezza della massima sequenza ad ordinata decrescente (le sequenze non contengono necessariamente tutti elementi di $A$ consecutivi). Per il teorema di Dilworth applicato sull'ordine parziale "un punto è minore di un altro se ha ascissa minore di quella dell'altro, ma ordinata maggiore" esiste una partizione di $A$ in $a$ sequenze ad ordinata decrescente. Inoltre per il teorema di Dilworth applicato sull'ordine parziale "un punto è minore di un altro se ha entrambe le coordinate minori di quelle dell'altro" esiste una partizione di $A$ in $b$ sequenze ad ordinata crescente, quindi visto che ognuna di esse è lunga al più $a$ in totale $A$ contiene al più $ab$ elementi, cioè vale $ab\geq2016$. Per $AM-GM$ vale $a+b\geq2\sqrt{ab}\geq2\sqrt{2016}=\sqrt{8064}>\sqrt{7921}=89$, quindi visto che $a+b$ è intero ciò implica $a+b\geq90$ e quindi $4032-a-b\leq3942$. Quindi se dimostriamo che sono sempre sufficienti $4032-a-b$ punti, possiamo concludere che ne sono sempre sufficienti $3942$, come voluto.
Sia $\epsilon$ un reale che vale al più $\frac{2}{5}$ per la minima differenza tra due coordinate di elementi di $A$. Per dimostrare che $4032-a-b$ punti sono sufficienti, notiamo che ogni rettangolo $SODDISFACENTE$ ne contiene almeno uno che ha come vertici opposti due elementi di $A$ (perché contiene i due elementi), quindi basta dimostrare che con $4032-a-b$ punti si può fare in modo che ognuno di tali rettangoli contenga almeno uno di tali punti. Dimostriamo che con $2016-b$ di essi si può fare in modo di soddisfare questa tesi per i rettangoli aventi come vertici opposti due elementi di $A$ che, presi nell'ordine che abbiamo dato (per ascissa crescente) hanno ordinata crescente, in modo analogo si potrà poi affermare che con $2016-a$ si può fare lo stesso per tutti i rettangoli in cui i due elementi, sempre ordinati per ascissa crescente, hanno ordinata decrescente, e giungere così alla tesi (se si utilizza, anziché $\epsilon$ come per la dimostrazione che segue, $\frac{\epsilon}{2}$ per questa dimostrazione analoga, l'$ICA$ ottenuto, unito con $A$, sarà un insieme $VARIO$, perché due coordinate di punti di tale unione differiranno di al più $\frac{\epsilon}{2}$).
Dette $C_1,C_2,\ldots C_b$ le sequenze ad ordinata crescente di cui abbiamo mostrato l'esistenza, e detta $D$ la sequenza ad ordinata decrescente lunga $b$, $D$ non può avere più di un elemento in comune con nessuna delle $C_i$, altrimenti se $D$ è ad ordinata decrescente $C_i$ non potrebbe essere ad ordinata crescente (conterrebbe due punti che, ordinati per ascissa crescente, hanno ordinata decrescente). Quindi, dato che $|D|=b$, $D$ deve avere esattamente un elemento in comune con ogni $C_i$, chiamiamo $e_i$ tale elemento (con $e_i\in C_i$). Per ogni $C_i$ mettiamo nell'$ICA$, per ogni elemento $X$ di $C_i$ che precede $e_i$, il punto $X'$ ottenuto traslandolo di un vettore $(\epsilon;\epsilon)$, e per ogni elemento $X$ di $C_i$ che segue $e_i$ il punto $X'$ ottenuto traslandolo di un vettore $(-\epsilon;-\epsilon)$. In tal modo, per ogni $C_i$ abbiamo aggiunto all'$ICA$ $|C_i|-1$ punti (uno per ogni elemento di $C_i$ diverso da $e_i$), quindi in totale ne abbiamo aggiunti $\sum_{i=1}^{b}{\left(|C_i|-1\right)}=\left(\sum_{i=1}^{b}{|C_i|}\right)-b=2016-b$. Resta da dimostrare soltanto che, per ogni rettangolo avente per vertici due punti $P,Q\in A$ con $x_P<x_Q$ e $y_P<y_Q$, esiste un punto tra quelli inseriti che è interno al rettangolo.
Se esiste un $i$ (con $1\leq i\leq b$) tale che $P,Q\in C_i$, se $P$ viene prima di $e_i$ il rettangolo contiene $P'$, altrimenti $P$ è $e_i$ oppure viene dopo, quindi $Q$ viene dopo $e_i$ e il rettangolo contiene $Q'$. Possiamo quindi supporre che esistano due indici distinti $i,j$ tali che $P\in C_i$ e $Q\in C_j$. Se $P$ viene prima di $e_i$ il rettangolo contiene $P'$. Se $Q$ viene dopo $e_j$ il rettangolo contiene $Q'$. Dimostriamo che il caso in cui $P$ coincide con $e_i$ o viene dopo e $Q$ coincide con $e_j$ o viene prima è assurdo. Se $e_i$ nella sequenza ad ordinata decrescente $D$ viene prima di $e_j$, vale $y_{e_i}>y_{e_j}$, quindi $y_P\geq y_{e_i}>y_{e_j}\geq y_Q$, assurdo perché $y_P<y_Q$. Se invece $e_i$ nella sequenza ad ordinata decrescente $D$ viene dopo $e_j$, vale $x_{e_i}>x_{e_j}$, quindi $x_P\geq x_{e_i}>x_{e_j}\geq x_Q$, assurdo perché $x_P<x_Q$. Questo conclude la dimostrazione.

Commento:

Testo nascosto:

L'avevo provato appena è uscito, avevo fatto a) e trovato il claim per b) dimostrando il lower bound, ma l'upper bound non mi veniva nonostante avessi avuto l'idea delle sequenze ad ordinata crescente e decrescente perché non conoscevo Dilworth... ora che l'hai messo sono andato a vedere Dilworth e ho portato a compimento l'opera

PS: Certo che a scrivere in gara la soluzione di un problema del genere ci si mette una vita...
PPS: ma perché hai scritto "insieme $ICA$"? Significa "insieme $I$nsieme che $C$opre $A$"?

[bern1-16-4-13]

Ok, dovrebbe andare, anche se la ricontrollerò meglio quando avrò un po' di tempo..

Commento:

Testo nascosto:

L'avevo provato appena è uscito, avevo fatto a) e trovato il claim per b) dimostrando il lower bound, ma l'upper bound non mi veniva nonostante avessi avuto l'idea delle sequenze ad ordinata crescente e decrescente perché non conoscevo Dilworth... ora che l'hai messo sono andato a vedere Dilworth e ho portato a compimento l'opera

Infatti ho visto che sul topic di AoPS eri intervenuto!

PS: Certo che a scrivere in gara la soluzione di un problema del genere ci si mette una vita...

Sì, ci ho pensato anch'io, per di più la mia soluzione del punto b) che ho postato su AoPS (metto il link sotto) è ancora più brutta da scrivere per bene .

http://www.artofproblemsolving.com/comm ... 91p7346081

PPS: ma perché hai scritto "insieme $ICA$"? Significa "insieme $I$nsieme che $C$opre $A$"?

Ebbene, evidentemente le epizeusi non vengono usate solo in poesia ma anche nei testi di problemi di matematica, per dare maggior forza a una parola chiave...

[Federico II]

Bene, bern ha detto che la soluzione è corretta.
Ora, sia $x$ il suo punteggio alle IMO, e sia $y$ il numero degli ori che prenderà tra IMO e RMM. Dalla soluzione si evince che $x(x+y-1)=1974$ e $(x+y)(x-1)=1968$. Ponendo $z:=x+y$ si ottiene $x(z-1)=1974$ e $z(x-1)=1968$. Se $z=1$ la prima non è verificata perché il LHS si annulla, quindi si può supporre $z\neq1$ e dividere entrambi i membri per $z-1$ ottenendo $x=\frac{1974}{z-1}$. Sostituendo nella seconda si ottiene $z\left(\frac{1974}{z-1}-1\right)=1968$, da cui $\frac{z(1975-z)}{z-1}=1968$, ovvero $1975z-z^2=1968z-1968$, che equivale a $z^2-7z-1968=0$. Dalla formula risolutiva delle equazioni di secondo grado $z=\frac{7\pm\sqrt{7^2+4\cdot1968}}{2}=\frac{7\pm\sqrt{49+7872}}{2}=\frac{7\pm\sqrt{7921}}{2}=\frac{7\pm89}{2}$, ovvero $z=\frac{7+89}{2}=48$ oppure $z=\frac{7-89}{2}=-41$. La seconda soluzione non è accettabile perché $x\geq0$ essendo un punteggio alle IMO e $y\geq0$ essendo un numero di ori vinti, quindi $z=x+y\geq0$. Ne segue che $z=48$, quindi $x=\frac{1974}{z-1}=\frac{1974}{47}=42$ e inoltre da $z=x+y$ si ottiene $y=z-x=48-42=6$. Dunque abbiamo dimostrato che bern farà $42$ punti alle IMO e che prenderà $6$ ori tra IMO e RMM, il che significa che, essendo lui già in terza e non avendo ancora vinto ori alle IMO o alle RMM, dovrà necessariamente vincerlo ad entrambe le competizioni nel 2017, nel 2018 e nel 2019.

[bern1-16-4-13]

Bene, bern ha detto che la soluzione è corretta.

Be' no, ho detto che l'avrei ricontrollata per bene poi, e in effetti noto adesso che in quella parte c'è qualche errore di battitura, forse volevi dire Viola invece di bern, ma ti capisco, in effetti "Viola e bern sono (molto) vicini sulla tastiera"