[L02/03] Fede in the cage

[Gerald Lambeau]

Qualcuno, agendo in assoluta segretezza, ha aiutato Federico a risolvere il solitario di Marco, ma quest'ultimo non è contento: avrà la sua vendetta per tutte le gufate fattegli e anche per quelle che gli saranno fatte!
Marco decide quindi di rapire Federico e di rinchiuderlo in una gabbia speciale. Federico NON SA come funziona la gabbia (quindi non può risolvere il problema), ma voi sì (ve lo dico perché in fondo in fondo sono buono):
- la gabbia è un piano cartesiano ed è infinita (visto che attrezzatura?);
- all'inizio, solo sui punti $(0, 0), (1, 0), (0, 1)$ sono situate delle trappole mortali (molto, MOLTO atroci);
- dati due punti $A, B$, se sia su $A$ che su $B$ c'è una trappola, allora Marco piazza una trappola anche sul simmetrico di $A$ rispetto a $B$ (se ce n'è già una, ce la lascia). Per chi se lo stesse chiedendo, ebbene sì: l'ho fatto per tutto il piano (o almeno, per tutti i punti raggiungibili con questi vincoli);
- non vengono piazzate altre trappole se non si possono piazzare seguendo la regola del terzo punto.
Voi dovete (solo se volete salvare Federico, altrimenti fregatevene pure, non siete obbligati) scrivere due numeri interi su due foglietti e darli a Marco, lui li darà a Federico (potete constatare che gli siano pervenuti i numeri giusti, ma non potete comunicare con lui): Federico sarà costretto a mettersi nel punto le cui coordinate sono i due numeri. Gli è permesso di scegliere quale usare come ascissa e quale come ordinata, ma lui non sa con quale criterio deve farlo, quindi fate attenzione che vadano bene tutte le due possibilità! Una volta che Federico si trova nel punto prestabilito, Marco aziona le trappole mortali, poi, quando queste hanno finito il loro lavoro, fa uscire Federico (o quel che resta di lui...).
Per non farvi fare fesserie tirando a casaccio, Marco vi darà il permesso di scrivere i due interi sui due foglietti se e solo se gli direte qual'è l'insieme di tutti e soli i punti del piano che permettono a Federico di salvarsi (badate bene: per come funziona il gioco, il punto $(x, y)$ funziona se e solo se funziona anche il punto $(y, x)$).
Siete in grado di salvare Federico? Sbrigatevi: fra poco dovrà partire a rappresentare l'Italia alle IMO (sì, stesso acronimo dell'altro problema); se muore, ci sarà una medaglia d'oro in meno!

[Veritasium]

La formalizzazione non è il mio forte

Testo nascosto:

Federico si salva solo sui punti con entrambe le coordinate dispari (anche negative).
Intanto mostriamo che se un punto [tex]R[/tex] ha entrambe le coordinate dispari, allora è sicuro. Supponiamo Marco possa piazzarci un trappola, allora esisteranno [tex]P, Q[/tex] tali che [tex]R[/tex] è simmetrico di [tex]P[/tex] rispetto a [tex]Q.[/tex] Allora il punto [tex]P[/tex] avrà coordinate [tex]P(x_R \pm 2\delta_x, y_R \pm 2\delta_y)[/tex] dove [tex]\delta_x, \delta_y[/tex] sono rispettivamente la differenza in valore assoluto tra le coordinate [tex]x[/tex] e la differenza in valore assoluto tra le coordinate [tex]y[/tex] di [tex]Q, R[/tex]. Essendo per ognuna delle due coordinate di [tex]P[/tex] un addendo pari e uno dispari, notiamo che anche $P$ doveva avere entrambe le coordinate dispari. Ma i tre punti iniziali non hanno coordinate entrambe dispari, da cui l'assurdo (una specie di discesa infinita).
Mostriamo ora che gli altri punti sono tutti raggiungibili dalla pervasiva malvagità di Marco. È banale ricoprire completamente gli assi cartesiani, nonché la retta [tex]y = -x + 1.[/tex] Fatto ciò, possiamo disseminare trappole anche sulle rette [tex]y = x - 1[/tex] e [tex]y = x + 1,[/tex] rispettivamente la simmetrica rispetto all'asse delle ascisse e delle ordinate. Simmetrizzando (e quindi ricoprendo di trappole) quest'ultima rispetto all'asse delle ascisse otteniamo pure la retta [tex]y = -x - 1,[/tex] e la situazione è di nuovo simmetrica. Prendiamo le rette con [tex]m = 1/2,[/tex] e iniziamo a fare il simmetrico di una rispetto all'altra (è chiaro che i simmetrici sono tra punti e non tra rette, cioè quando dico che faccio il simmetrico della retta [tex]y = \pm 1/2x + q + 2[/tex] rispetto alla retta [tex]y = \pm 1/2x + q[/tex] ottenendo la retta [tex]y = \pm 1/2x + q - 2[/tex] intendo che faccio il simmetrico di ogni punto della prima retta rispetto al piede della perpendicolare da lui alla seconda retta, e vedo che così tutti i punti della prima vanno in tutti i punti della terza). Fatto ciò per [tex]m = \pm 1/2[/tex], dopo un tempo di [tex]\aleph_0[/tex] secondi, Marco ha piazzato su tutti i punti con coordinate (entrambe non nulle) che hanno somma dispari, perché ognuno di essi appartiene a una retta del tipo [tex]y = ±x ± d[/tex] per un intero positivo dispari [tex]d[/tex] (e abbiano appena visto come ricoprire tutte queste rette partendo dalle $4$ originali) e su tutti i punti con almeno una coordinata nulla. Rimane da mostrare che Marco può adesso piazzare su tutti i punti con entrambe le coordinate pari. Essendo la situazione simmetrica rispetto all'origine, basta far vedere he per tutte le ascisse positive pari [tex]2x,[/tex] Marco può piazzare su [tex](2x, 2y)[/tex] per ogni [tex]y[/tex] intero positivo. Notiamo che su [tex](2x, 1)[/tex] c'è una trappola perché la somma delle coordinate è dispari. È facile quindi mostrare che, se c'è una trappola su [tex](2x, i)[/tex] per [tex]0 \le i \le n[/tex], allora la si può piazzare anche su [tex](2x, n + 1),[/tex] infatti basta fare il simmetrico di [tex](2x, n)[/tex] rispetto a $(2x, n - 1)$. Essendo $(2x, 0), (2x, 1)$ piazzati, abbiamo concluso.

[Gerald Lambeau]

Che roba! Non sono stato a controllare tutte le simmetrie nel dettaglio, ma penso siano giuste. Ad ogni modo, il risultato è corretto. Una via più semplice è:
- mostro che da due punti con entrambi almeno una coordinata pari ottengo sempre un punto con almeno una coordinata pari (possiamo considerare la presenza di almeno una coordinata pari come una specie di invariante), all'inizio tutti i punti hanno coordinata pari, quindi quelli con entrambe le coordinate dispari non li posso ottenere;
- faccio gli assi; faccio il simmetrico di $(0, 1)$ rispetto a $(1, 0)$ che è $(2, -1)$; usando $(2, -1)$ e $(2, 0)$ mi faccio la retta $x=2$; faccio il simmetrico di $(0, 1)$ rispetto a $(-1, 0)$ che è $(-2, -1)$; usando $(-2, -1)$ e $(-2, 0)$ mi faccio la retta $x=-2$; per induzione avanti e indietro faccio tutte le rette verticali $x=2k$ per $k$ intero (ho una retta verticale, ho l'asse delle ascisse, vado in avanti facendo come ho fatto per ottenere $x=2$ e indietro facendo come ho fatto per ottenere $x=-2$); per simmetria (che so, tipo Marco si gira nel piano in modo da invertire gli assi) faccio tutte quelle orizzontali $y=2h$ per $h$ intero.
Va certamente formalizzata meglio, principalmente l'induzione che andrebbe fatta esplicitamente, ma anche la simmetria si potrebbe spiegare in un modo decisamente più chiaro di "Marco si gira nel piano", però è molto straightforward.