Parti$\mathbb{Z}$ioni

[Gerald Lambeau]

È un po' che non postavo un bel problema e questo che ho provato a fare oggi mi sembrava carino, anche se forse molti lo conoscono già (in qual caso, vietato ucciderlo) e potrebbe essere già passato, ma vabbè.

Determinare tutte le coppie di interi positivi $(p, q)$ per cui è possibile partizionare $\mathbb{Z}$ in tre sottoinsiemi $A, B, C$ tali che per ogni intero $n$ i tre interi $n, n+p, n+q$ appartengono a insiemi differenti.

[Fenu]

Spero di averlo fatto giusto e di non aver sbagliato in qualche induzione, aspetto correzioni..

Testo nascosto:

Dato che non sappiamo quali elementi appartengo ad $A, B, C$, diremo semplicemente che tre elementi stanno negli insieme $i, i+1, i+2$, dove questi indici sono visti in modulo 3
Ho cominciato costruendo una tabella $3x3$ dove ho sistemato $n, n+p, n+q$ nella prima riga, $n+p, n+2p, n+p+q$ nella seconda, e (potete immaginare) $n+q, n+p+q, n+2q$ nella terza riga (questa roba qua mi è servita solo per intuire una cosa, è tralasciabile per lo sviluppo della dimostrazione, ma ho pensato di lasciarla).
Posto $n=0$ si ha WLOG che $0, p, q$ stanno nell insieme $1, 2, 3$.
Usando la tabella, ponendo $n=0, p, 2p, etc$ (ricordiamo che $0, p$ stanno in $1, 2$, serve mantenere la stessa numerazione) ed ampliandola ($4x4$, $5x5$ bastano), si può notare che i numeri della forma $n=h*p$ ($h$ positivo)stanno nell'insieme $(h+1)$-esimo (modulo 3). Per induzione è immediato verificare che questo è vero:
Passo base: la tripletta $0, p, q$ rispetta (stanno in $1, 2, 3$), e anche la tripletta $p, 2p, p+q$ (stanno in $2, bla, bla$). Supponiamo valga per tutti gli $h\leq h_0$.
Passo induttivo:
Vale anche per $h_0+1$ dato che $((h_0-1)*p, (h_0-1)*p+p, (h_0-1)*p +q)$ stanno in $h_0, h_0+1, h_0+2$ (per supposizione induttiva), inoltre $((h_0)*p, (h_0+1)*p, (h_0+1)*p+q)$ stanno in $h_0+1, X, Y$. Chiaramente $X\ne h_0+2$ altrimenti avremmo che gli elementi $(h_0-1)*p+p$ e $(h_0+1)*p$ starebbero nello stesso insieme (impossibile dato che differiscono di $p$). Segue che $(h_0+1)*p$ sta nel insieme $h_0+2$-esimo. E ciò termina questa induzione.
Facendo gli stessi identici passaggi otteniamo che se $n=h*b$ allora $n$ sta nell'insieme $2h+1$-esimo
Passo base: la tripletta $0, p, q$ rispetta, e $q, p+q, 2q$ pure. Supponiamo ora che valga per tutti gli $h\leq h_0$
La tripletta $((h_0-1)*q, (h_0-1)*q+p, (h_0)*q)$ sta in $2h_0-1, 2h_0, 2h_0+1$ per ipotesi induttiva. Inoltre la tripletta $((h_0)*q, (h_0)*q+p, (h_0+1)*q)$ sta in $(2h_0+1, X, Y)$, ma di sicuro $X\ne2h_0+3$ altrimenti i termini $(h_0)*q+p, (h_0-1)*q+p$ starebbero nello stesso insieme (impossibile perchè differiscono di $q$). Segue che $Y=2h_0+3=2h_0$ dato che stiamo guardando i nomi modulo $3$, e l' induzione è completa.
Consideriamo ora $n=pq$. Dai precedenti lemmi segue che $n$ sta nell'insieme $q+1$-esimo e nell'insieme $2p+1$-esimo. Dato però che $n$ sta in un solo insieme, segue che
$$2p+1\equiv q+1\pmod{3}\Rightarrow 2p=q\pmod{3}$$
e dunque $p, q$ alternativamente $+1, -1$ modulo $3$ è l'unica possibilità.
E' immediato (anzi, in realtà è proprio il pensiero che spinge a guardare modulo $3$) verificare che è possibile costruire questi sottonsiemi semplicemente prendendo le $3$ classi di resto di $\mathbb{Z}_3$.

[Gerald Lambeau]

Il ragionamento è giusto, solo che ad esempio $(p, q)=(3, 6)$ funziona benissimo - in generale, non puoi scartare a priori $p \equiv q \equiv 0 \pmod{3}$. Manca qualcosa in più, anche se ci sei molto vicino.

[Fenu]

Hai perfettamente ragione, ti ringrazio.
Se non sbaglio dovrei poter correggere semplicemente assumendo ad inizio della dimostrazione $p, q$ coprimi, altrimenti mi basterebbe considerare la stessa partizione però per gli interi multipli di $mcd(p, q)$.
Ciò mi porta alla concluzione che i $p, q$ validi sono della forma $p=d*p', q=d*q'$ con $(p', q')=1$ e tali che $3|p'+q'$. Aspetto correzioni.

[Gerald Lambeau]

Sì, ora dovrebbe andare!
Io ho caratterizzato $p$ e $q$ diversamente, ma in realtà dovrebbe venire la stessa cosa, ti scrivo quello che ho fatto per un doublecheck (dovrebbe essere una diversa formulazione per indicare le stesse coppie che indichi tu):

Testo nascosto:

$v_3(p+q)>v_3(p)=v_3(q)$ (alla fine tutto quello che conta è il fattore $3$).

[Gerald Lambeau]

Comunque adesso devi dimostrare che effettivamente $3 \mid p'+q'$.

Ci sta che volessi intendere di fare qualcosa del genere quando dicevi che:

altrimenti mi basterebbe considerare la stessa partizione però per gli interi multipli di $mcd(p, q)$.

ma ti dispiacerebbe essere più esplicito?

[Salvador]

.