[L06] Da oltre Adriatico con furore

[Federico II]

Il piano è suddiviso in quadratini unitari mediante due insiemi di rette parallele, formando una griglia infinita. Ogni quadratino è colorato con uno tra $1201$ colori, in maniera tale che nessun rettangolo con perimetro uguale a $100$ contenga due quadratini dello stesso colore.
Dimostrare che nessun rettangolo $1\times1201$ o $1201\times1$ contiene due quadratini dello stesso colore.
Nota: qui si assume che ogni rettangolo abbia i lati contenuti nelle rette della griglia.

[bern1-16-4-13]

Provo, anche se non sono sicuro che una parte della dimostrazione sia del tutto accettabile

Testo nascosto:

Innanzitutto definiamo un sistema di riferimento scegliendo un quadratino con coordinate $(0,0)$ e assegnando poi a ogni altro quadratino una coppia di coordinate $x,y$ nel modo usuale.
Definiamo $n$-elica una regione di piano con le seguenti caratteristiche:

1. è un poligono, più in particolare un insieme di quadratini (che non vengono tagliati dal contorno del poligono) senza buchi;
2. esiste un certo quadratino $j$ che chiameremo fulcro di quella $n$-elica tale che per ogni quadratino $l$ appartenente al bordo della $n$-elica si avrà che $\vert x_j-x_l\vert +\vert y_j-y_l\vert =n-2$.

So che è un po' pomposa come definizione, ma non mi andava di mandare immagini in allegato.
Definiamo rettangolo minimo di $a$ e $b$, che abbrevieremo $R_{a,b}$, (dove $a$ e $b$ sono due quadratini generici) il rettangolo tale che $a$ e $b$ si trovino in corrispondenza di vertici opposti di tale rettangolo. Se $p$ è la funzione perimetro allora è evidente che $p\left(R_{a,b}\right)=2\left(\vert x_a-x_b\vert +\vert y_a-y_b\vert +2\right)$.
Ma allora se $j$ è il fulcro di una $n$-elica si avrà che per ogni $l$ nell'$n$-elica $p\left(R_{j,l}\right)\le 2n$ con l'uguaglianza che vale sse $l$ si trova sul bordo (questo fatto diciamo che sarà il $LEMMA\ 0$)


$LEMMA\ 1$:
presi tre quadratini $a,b,c$ allora $p\left(R_{a,b}\right)\le p\left(R_{a,c}\right)+p\left(R_{b,c}\right)-4$. Infatti $\vert x_a-x_b\vert\le\vert x_a-x_c\vert +\vert x_b-x_c\vert$. Discorso analogo per le ordinate. Quindi $$p\left(R_{a,b}\right)=2\left(\vert x_a-x_b\vert +\vert y_a-y_b\vert +2\right)\le p\left(R_{a,b}\right)=2\left(\vert x_a-x_c\vert +\vert x_b-x_c\vert +\vert y_a-y_c\vert +\vert y_b-y_c\vert +2\right)$$$$=2\left(\vert x_a-x_c\vert +\vert y_a-y_c\vert +2\right)+2\left(\vert x_b-x_c\vert +\vert y_b-y_c\vert +2\right)-4=p\left(R_{a,c}\right)+p\left(R_{b,c}\right)-4.$$

$LEMMA\ 2$:
Se $S_i$ è l'insieme dei quadratini del piano colorati col colore $i$ e se $p\left(R_{a,b}\right)>4n\ \ \forall a,b\in S_i$ allora non esistono due $n+1$-eliche con fulcri in $S_i$ che abbiano qualche quadratino in comune.
Supponiamo che per assurdo esistano $a,b,c$ tali che $a,b\in S_i$ e $c$ appartiene alle due $n+1$-eliche di fulcro $a$ e $b$.
Ma allora $p\left(R_{a,c}\right)+p\left(R_{b,c}\right)\le 4\left(n+1\right)$ per il $LEMMA\ 0$. Quindi per il $LEMMA\ 1$ si ha che $p\left(R_{a,b}\right)\le 4n$. Assurdo.

Inoltre si calcola facilmente che l'area di una $n+1$-elica è $n^2+\left(n-1\right)^2$. Quindi se $T$ è la cardinalità dell'insieme dei quadratini del piano, allora $\vert S_i\vert \le \frac{T}{n^2+\left(n-1\right)^2}$ con l'uguale che vale sse le $n+1$-eliche con fulcri in $S_i$ coprono esattamente il piano. Adesso supponiamo di avere a disposizione esattamente $n^2+\left(n-1\right)^2$ colori per colorare interamente il piano. Allora poiché $\sum S_i=T$ deduciamo che per ogni colore $i$ si ha che $S_i=\frac{T}{n^2+\left(n-1\right)^2}$ quindi l'insieme delle $n+1$-eliche con fulcri in $S_i$ dovrà coprire esattamente il piano. Ma a meno di traslazioni e ribaltamenti esiste una sola tassellazione del piano con $n+1$-eliche e questa tassellazione, sempre a meno di ribaltamenti e traslazioni, sarà tale che i fulcri saranno della forma $((k-h)n-k),(k+h)n-h)$.
Per dimostrare la tesi è sufficiente far vedere che il quadratino $(0,0)$ dista almeno $n^2+(n-1)^2$ da ogni quadratino sulla riga a ordinata $0$. Quindi $(k+h)n-h=0\longrightarrow k=\frac{h}{n}-h\longrightarrow h=jn,\ k=j-j^2$ (ovviamente stiamo lavorando negli interi relativi). Quindi l'ascissa sarà $j(2n-2n^2-1)$ quindi la distanza da $0,0$ sarà il valore assoluto di quella cosa. I due punti di minimo interi e con $j\ne 0$ (poiché altrimenti ci ritroveremmo esattamente nel punto $(0,0)$) sono evidentemente $j=1$ e $j=-1$ quindi si ha che la distanza è almeno $2n^2-2n+1=n^2+(n-1)^2$ come volevasi dimostrare. Adesso si ottiene la dimostrazione del caso particolare richiesto se sostituiamo $n=25$.

[Federico II]

Non sono sicuro che tu possa fare quel ragionamento sulla cardinalità degli insiemi infiniti, c'è un modo per evitarlo (sta nella soluzione ufficiale).
Poi anche se non è difficile penso che in gara dovresti dimostrare che la tassellazione è unica.

[bern1-16-4-13]

Sì, era quello il mio dubbio infatti.

Per la tassellazione sì, penso proprio che sarebbe stato necessario dimostrare l'unicità.

[bern1-16-4-13]

Forse si dovrebbe poter aggiustare dicendo che la distanza massima tra due quadratini in una stessa $n+1$-elica è proprio $4n$, quindi una qualsiasi $n+1$-elica contiene tutti colori distinti.
A questo punto se uno prende una $n+1$-elica a caso la colora con una colorazione che non usi due volte uno stesso colore, allora le $n+1$-eliche ottenute traslando di vettori $(1,1)$, $(1,-1)$, $(-1,1)$, $(-1,-1)$ si vede abbastanza bene che sono tutte univocamente determinate. In particolare la colorazione è univocamente determinata e in questo modo uno si risparmia anche di mostrare l'unicità della tassellazione

[Federico II]

Ma direi proprio di no (per la parte sulle traslazioni).

[bern1-16-4-13]

ahahaha, hai ragione, come sono intelligente

[bern1-16-4-13]

Ritento un'altra (e spero l'ultima!) volta.
Consideriamo ancora una volta la tassellazione delle $n+1$-eliche di un certo colore $i$ fissato: al momento sappiamo solo che non contiene sovrapposizioni.
Supponiamo quindi che esista un quadratino non appartenente alla tassellazione: l'$n+1$-elica incentrata su questo quadratino dovrà contenere un quadratino $x$ di colore $i$ (per il discorso già fatto in precedenza). Ma allora la $n+1$-elica con fulcro $x$ dovrà a sua volta contenere il quadratino che avevamo detto non appartenere alla tassellazione: assurdo.

[Federico II]

Finalmente