Non allontanarsi troppo

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Siete stati rapiti da un docente di matematica crudele. Egli vi mette sulla retta dei numeri interi, precisamente sullo $0$. E vi chiede di dargli una successione $(n_k)_k$ infinita di mosse, i cui valori possono essere +1 oppure -1. In seguito il docente vi muove sulla retta degli interi seguendo la successione che gli avete fornito. Se raggiungente il numero 3 oppure il numero -3 seguendo la vostra successione il docente vi boccia. Però una volta consegnata la successione di mosse il docente può scegliere di farvi fare le mosse seguendo una sotto-successione $(n_{k_j})_j$ della successione di mosse da voi consegnata, a condizione che gli indici scelti seguono una certa progressione aritmetica di sua scelta, i.e. $k_1$ è arbitrario di sua scelta, inoltre $k_j = k_1 + d (j-1)$, con $d$ di sua scelta. Potete evitare la bocciatura?

[2e543318e6a8602051219b452505a7c0b11de594]

Non credo sia molto appropriato parlare di "retta degli interi", semmai "retta dei reali". Oltretutto, a ogni salto su un intero diverso da quello di partenza si supera un baratro che ha cardinalità pari a quella dell'insieme delle parti della cardinalità stessa dei numeri interi.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Suvvia, credo si capisca cosa intendessi

[hydro1]

Ovviamente la risposta è una conseguenza immediata del

Teorema di Van der Waerden.

Altrettanto ovviamente, questo è un caso facile (e anche più debole) del suddetto teorema, quindi dovrebbe esistere una prova facile. Ci ho pensato un po’ e non ho potuto fare meglio di così, sono curioso di sapere se esista una soluzione più elegante.

Non si può evitare la bocciatura. Per dimostrarlo, basta mostrare che data una colorazione degli interi con $0$ e $1$, esiste sempre o una successione aritmetica monocromatica di lunghezza $3$ (cosa che segue dal teorema di sopra) oppure $5$ interi consecutivi la cui somma è minore o uguale ad $1$ o maggiore o uguale a $4$. Supponiamo che questa condizione sia falsa. Allora ci sono sempre due interi consecutivi colorati uguale, perché altrimenti sarebbero tutti alternati e $1,3,5$ sarebbe monocromatica. Wlog, supponiamo che siano colorati di $0$. Allora quello prima e quello dopo devono essere colorati di $1$, che altrimenti ne ho 3 consecutivi colorati uguale. Quindi ho trovato $1001$ ad una certa. Il blocco di due interi precedenti e consecutivi non può essere $11$, che altrimenti trovo una terna consecutiva monocromatica, ma neanche $00$, perché altrimenti ho $5$ interi consecutivi a somma $1$. Se il blocco precedente è $10$, quello successivo non può essere $10$ anche lui, perché altrimenti le posizioni $2,5,8$ sono una terna monocromatica. Similmente, se il blocco precedente e’ $01$, quello successivo non può essere $01$ anche lui perché altrimenti le posizioni $1,4,7$ sono una successione monocromatica. Quindi deve esistere un blocco della forma $10100101$ oppure $01100110$. Adesso si tratta solo di notare con pazienza che in fondo a questi blocchi non posso mettere ne’ $0$ né $1$ senza creare una terna monocromatica.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Una più elegante non so. Forse la soluzione 2 nello spoiler è più elegante. Ma l'eleganza è anche soggettiva.

In effetti a parte una manciata di casi, moltissimi numeri di van der Waerden sono sconosciuti. Per numero di van der Waerden intendo il naturale minimale $W(c,k)$ tale che che se coloriamo $\{1,2,\ldots, W(c,k) \}$ con $c$ colori allora abbiamo una progressione aritmetica di lunghezza $k$ monocromatica. Noi dobbiamo dimostrare che $W(2,3)=9$. In realtà basterebbe dimostrare che $W(2,3) \leq N$ per un qualunque $N$ opportuno ed esplicito, o dimostrarne l'esistenza. Nel seguito con \(a\) indico il colore associato alla mossa \(+1\) e con \(b\) indico il colore associato alla mossa \(-1\). Coloriamo l'intero \(k \) del colore corrispondente alla mossa \(n_k\) dello studente.

SOLUZIONE 1:

Questa è fondamentalmente la stessa della tua. E alla fine è un po' come giocare ad un sudoku.
Sicuramente almeno due tra $4,5,6$ hanno lo stesso colore per il principio dei cassetti. Se tutti e tre hanno lo stesso colore abbiamo finito. Dobbiamo quindi divedere in 3 casi.
Caso 1) $4,5$ colorati dello stesso colore e $6$ diverso.
Caso 2) $4,6$ colorati dello stesso colore e $5$ diverso.
Caso 3) $5,6$ colorati dello stesso colore e $4$ diverso.

Notiamo subito che il caso 3) è simmetrico al caso 1).

Caso 1) Supponiamo $4,5$ siano colorati $a$. Allora $3,6$ sono colorati $b$. Dunque $9$ è colorato con $a$. Deduciamo che $1,7$ sono colorati con $b$. Il $2$ quindi è colorato con $a$ sennò avremmo $1,2,3$ colorati di $b$. Ma ora indipendentemente dal colore di $8$ otteniamo una progressione aritmetica dello stesso colore.

Caso 2) Supponiamo che $4,6$ abbiano lo stesso colore, diciamo $a$. Allora per evitare una progressione aritmetica di lunghezza $3$ di colore $a$ dobbiamo per forza colorare $2,5,8$ con $b$.

Questo dimostra che $W(2,3) \leq 9$. Per dimostrare che $W(2,3)=9$ bisognerebbe esibire anche una colorazione di $\{ 1,2,\ldots,8\}$ senza $3-AP$ monocromatiche e quelle che hai fornito te (hydro) per esempio vanno bene. Per questo indovinello non è necessario dimostrare l'uguaglianza. Infatti con questo sappiamo che nelle prime 9 mosse consegnate dallo studente al docente, il docente potrà bocciarlo selezionando la progressione aritmetica monocromatica.

SOLUZIONE 2:

Quando dicevo che va bene $W(2,3) \leq N$. Ad esempio a noi ci basta che il docente possa sicuramente trovare una progressione aritmetica di lunghezza 3 monocromatica al interno della successione infinita di mosse. Ad esempio tempo fa lessi la seguente dimostrazione su wikipedia che è molto carina secondo me e forse più elegante di un analisi dei casi! Dimostriamo che $W(2,3) \leq 325$. Una volta fatto questo il docente potrà bocciarlo selezionando come prime 3 mosse la progressione aritmetica monocromatica esistente nelle prime 325 mosse dello studente.

Scriviamo $\{1,2,\ldots,325\}$ come unione di $65$ insiemi disgiunti nel seguente modo \[ \{1,\ldots,5\} \cup \{ 6,\ldots,10\} \cup \{11,\ldots,15\} \cup \{321,\ldots,325\} \]
\[ \{1,2,\ldots,325\} = A_0 \cup A_1 \cup \ldots \cup A_{64}\]
dove \( A_j= \{ 5j +1,\ldots 5j+5 \} \) e \(0 \leq j \leq 64\). Siccome per ogni \(j \) abbiamo che ci sono \(2^5=32\) colorazioni distinte usando \(a,b \) di \(A_j\) abbiamo per il principio dei cassetti che esistono \(0 \leq i < j \leq 32 \) tale che \(A_i \) e \(A_j \) sono colorati nello stesso modo. Sempre per il principio dei cassetti abbiamo che due tra \(5i+1,5i+2,5i+3\) hanno lo stesso colore, diciamo il colore \(a\). Diciamo che sono \(5i+x \) e \(5i+y\) con \(x,y\in \{1,2,3\}\) e \(x < y\). Sia \( z = 2y-x \leq 5 \). Abbiamo dunque \(5i+z \in A_i\). Se \(5i+z\) è colorato con \(a\) abbiamo finito. Se \(5i+z\) è colorato con \(b\) allora anche \(5j+z \in A_j\) è colorato con \( b\). Sia \(k=2j-i \leq 64\), \(A_k \subseteq \{1,\ldots 325 \}\).
Se \(5k+z \in A_k \) è colorato con \(a\) allora \( 5i+x,5j+y,5k+z \) è una progressione aritmetica monocromatica di lunghezza \(3\) con differenza comune \(5(j-i)+(y-x)\). Se invece \(5k+z \) è colorato con \(b\) allora \(5i+z, 5j+z,5k+z \) è una progressione aritmetica monocromatica di lunghezza \(3\) con differenza comune \(5(j-i) \).