Roba da Mille e Una Notte

[Nemo]

È data una linea poligonale lunga $ 1001 $ in un quadrato di lato $ 1 $. Si dimostri che esiste una retta, parallela a un lato del quadrato, che interseca la poligonale in almeno $ 500 $ punti.

[machete]

Sia $ n $ il numero di segmenti di cui è composta la poligonale, ognuno lungo $ \ell_i $. Ognuno forma con la direzione di un certo lato del quadrato, che prenderemo come asse $ x $, un certo angolo $ \vartheta_i\in [0,\pi/2] $.
La somma delle proiezioni dei segmenti sull 'asse $ x $ vale:

$ \displaystyle X:=\sum_{i=1}^n \ell_i\, \cos \vartheta_i $

sull' asse $ y $ (cioè sul lato verticale):

$ \displaystyle Y:=\sum_{i=1}^n \ell_i\, \sin \vartheta_i $

Ricordando che: $ \sin \vartheta +\cos \vartheta\geq 1 $ per $ \vartheta \in [0,\pi/2] $, si ha:

$ \displaystyle X+Y=\sum_{i=1}^n \ell_i\, ( \sin \vartheta_i+\cos \vartheta_i)\geq \sum_{i=1}^n \ell_i=1001 $

quindi almeno uno fra $ X $ e $ Y $ è maggiore o uguale di $ 1001/2 $. Sia WLOG $ X $.

Siano $ P_0,\ldots, P_n $ i punti della poligonale e $ x_0,\ldots, x_n \in[0,1] $ le ascisse delle loro proiezioni. Ora se ci sono $ x_i $ e $ x_j $ uguali ($ i\neq j $) ne eliminiamo uno, e se $ x_i\in\{0,1\} $ per un qualche $ i $ lo eliminiamo. Essendo le $ \{x_k\} $ in numero finito queste operazioni terminano. Le $ \{\tilde{x}_k\} $ rimanenti partizionano $ [0,1] $ in un certo numero (eventualmente zero) di sotto-intervalli che hanno la proprietà di appartenere ad un numero intero di segmenti proiezione (quelli del tipo $ [{x_i,x{i+1}}] $, per intenderci). Se ora fosse vero che ognuno di questi intervalli appartiene ad un numero $ \leq 500 $ di proiezioni avrei che la lunghezza totale delle proiezioni è $ \leq 500 $ che è assurdo. Esiste dunque un intervallo $ [a,b] $che appartiene a $ \geq 501 $ proiezioni. La retta $ x=(a+b)/2 $ interseca quindi almeno $ 501 $ segmenti della poligonale (in realtà tutte le rette del tipo $ x=k $ con $ k\in (a,b) $ lo fanno).

So che l' ultima parte è un po' scritta sinteticamente ma spero si capisca! (e soprattutto che sia giusta:D)

[Gottinger95]

Posto la mia, che non so se è giusta! Chiamo \(n=500, 2n+1=1001\).
Prendiamo un segmento lungo \(l\) della spezzata. Allora la somma delle proiezioni orizzontali e verticali, diciamo \(x,y\), è al minimo \(l\): infatti, visto che
\( (x+y)^2 = l^2 +2xy\)
il minimo della somma si ottiene in corrispondenza del minimo del prodotto (ossia quando o \(x\) o \(y\) sono 0). Questo significa che la somma delle proiezioni è al minimo \(2n+1\): per pidgeonhole, esiste almeno un punto dei due lati in cui si sovrappongono almeno \((2n+1)/2 \ge n\) proiezioni (che è equivalente alla tesi).
Edit: in realtà è parecchio simile a quella di machete