Coloriamo i numeri :)

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Colorate i numeri \( 1,2,3,4,5,6,7,8 \) con due colori in modo tale che non ci sono \(3\) numeri in progressione aritmetica colorati con lo stesso colore. E' possibile colorare i numeri \(1,2,3,4,5,\ldots,32,33,34 \) con due colori in modo tale che non ci sono \(4\) numeri in progressione aritmetica colorati con lo stesso colore?

[axpgn]

$1,3,6,8$ e $2,4,5,7$

[Quinzio]

Ci sono tutte queste piu' quelle a "colori invertiti", 0 al posto di 1 e viceversa.
Si trovano con un programmino software .
Comunque in tutte le sequenze c'e' sempre lo stesso motivo ricorrente, che sarebbe:
1 1 1 0 1 0 0 1 0 0 0
con tutte le riflessioni, inversioni, ecc...
Con 35 numeri non se ne trova nessuna.

0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 1 
0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 0 
0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 1 
0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 0 
0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 1 
0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 0 
0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 1 
0 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 
0 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 
0 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1 
0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 
0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 
0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 
0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1 

Se qualcuno e' interessato al programmino in C++:

#include <iostream>

using namespace std;

#define LEN 34

int cell     [LEN];
int warn  [2][LEN][50];
int warn_n[2][LEN];
int deny  [2][LEN];
int debug;

void run(int n_run) {
    if (n_run >= LEN) {
        //cout << "Trovata\n";
        for (int x = 0; x < n_run; x++) {
            printf("%d ", cell[x]);
        }
        printf("\n");
        return;
    }
    for (int color = 0; color < 2; color++) {
        if (deny[color][n_run] > 0) continue;
        cell[n_run] = color;
        for (int cell_before = max(0, (3*n_run -(LEN - 1)) / 2); cell_before < n_run; cell_before++) {
            if (cell[cell_before] == color) {
                warn[color][2*n_run - cell_before][warn_n[color][2*n_run - cell_before]] = 3*n_run - 2*cell_before;
                warn_n[color][2*n_run - cell_before]++;
            }
        }
        for (int denial = 0; denial < warn_n[color][n_run]; denial++) {
            deny[ color ][ warn[ color ][ n_run ][ denial ]]++;
        }
        run(n_run+1);
        for (int denial = 0; denial < warn_n[color][n_run]; denial++) {
            deny[ color ][ warn[ color ][ n_run ][ denial ]]--;
        }
        for (int cell_before = max(0, (3*n_run -(LEN - 1)) / 2); cell_before < n_run; cell_before++) {
            if (cell[cell_before] == color) {
                warn_n[color][2*n_run - cell_before]--;
                warn[color][2*n_run - cell_before][warn_n[color][2*n_run - cell_before]] = 0;
            }
        }
        if ((n_run == 0) && (color == 0)) {
            debug++;
        }
    }
    cell[n_run] = -1;
#if 0
    if ((deny[0][n_run] > 0) && (deny[1][n_run] > 0)) {
        printf("Dead end at %d\n", n_run);
        for (int x = 0; x < n_run; x++) {
            printf("%d ", cell[x]);
        }
        printf("\n\n");
    }
#endif
}


int main()
{
    cout<<"Hello World\n";
    for (int x = 0; x < LEN; x++) {
        cell[x] = -1;
    }
    for (int x = 0; x < 2; x++) {
        for (int y = 0; y < LEN; y++) {
            for (int z = 0; z < 50; z++) {
                warn[x][y][z] = 0;
            }
        }
    }
    for (int x = 0; x < 2; x++) {
        for (int y = 0; y < LEN; y++) {
            warn_n[x][y]= 0;
            deny[x][y]= 0;
        }
    }
    run(0);

    return 0;
}

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

ad entrambi!

Ecco provate questo: Colorare \( \mathbb{N} \) con due colori in modo tale che non esiste una progressione aritmetica infinita colorata tutta con lo stesso colore.


[ot]Se volete potete fidarvi, altrimenti dimostratelo, ma c'è un teorema che afferma quanto segue: Dato \(k \in \mathbb{N}\), allora esiste \(N=W(k,m)\) tale per cui se \( \{1,\ldots, N\} \) è colorato con al più \(m\) colori allora ci sono almeno \(k\) numeri in progressione aritmetica colorati tutti con lo stesso colore.
A parte i casi banali, i valori conosciuti sono solo \(7\) e \( W(3,2) = 9\), \(W(4,2)=35\) sono tra questi. E' interessante notare che "all'infinito" non è più vero.[/ot]

[Quinzio]

"3m0o":
Ecco provate questo: Colorare \( \mathbb{N} \) con due colori in modo tale che non esiste una progressione aritmetica infinita colorata tutta con lo stesso colore.

Le distanze tra due interi di uno dei due colori potrebbero essere cosi:
$${2,2,3,3,3,4,4,4,4, ..., \underbrace{n,n,...,n}_{\text{n volte}}, ...}$$
Per essere ancora piu' chiari l'inizio della sequenza sarebbe

A*A*A**A**A**A***A***A***A***A...

Dove A e' un colore e * l'altro colore.

E' immediato vedere come una progressione aritmetica di ragione $n$ e colore A non puo' esistere nella zona $n+1$ (dove gli interi di uno dei due colori sono distanziati di $n+1$).
Anche una ipotetica progressione aritmetica di ragione $n$ e colore * e' incompatibile con la zona $n+1$, zona in cui la progressione finirebbe per incontrare un intero di colore A.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Anche se

Non è necessario ripete così tante volte la distanza. Basterebbe colorare così
R, B, R,R,B,B, R,R,R,B,B,B,R,R,R,R,B,B,B,B, ...

[Quinzio]

Giusto.