Progressioni aritmetiche

[axpgn]

Sia $S$ l'insieme degli interi positivi dispari composti minori di $79$.

a) dimostrare che $S$ può essere scritto come l'unione di tre progressioni aritmetiche, non necessariamente disgiunte.

b) dimostrare che $S$ NON può essere scritto come l'unione di due progressioni aritmetiche.


Cordialmente, Alex

[Quinzio]

La prima parte e' facile da mostrare.
Questo e' l'insieme $S$:
9 15 21 25 27 33 35 39 45 49 51 55 57 63 65 69 75 77

La prima progressione inizia con 9 ed ha ragione 6.

Rimangono fuori:
25 35 45 55 65
e
49 77
che vengono "coperti" da 2 progressioni:
inizio 25, ragione 10
inizio 49 ragione 28.

La seconda parte non e' banale da dimostrare.
Chiaramente si puo' far vedere in modo esaustivo, mostrando tutte le combinazioni, che non esistono 2 progressioni che coprono $S$, ma ovviamente e' una dimostrazione deludente.
Un fatto che penso sia collegato ad una dimostrazione "vera" e' che i primi che sono in comune ai fattori di ogni numero di $S$ sono almeno 3 (e 2 non sono sufficienti).
Ovvero, si fattorizzano gli elementi $s_n$ di $S$. Per ogni elemento si forma l'insieme $SP_n$ dei fattori primi. Qual e' l'insieme $P$ minimo di primi tale per cui almeno un primo dell'insieme $P$ e' contenuto in ogni $SP_n$ ?
L'insieme minimo $P$ e' formato da 3 primi (3,5,7).
Ovvero,
il 9 ha 3 come fattore, 77 ha 7 come fattore, 25 ha 5 come fattore, cosi' via.
Con solo 2 primi non ci si riesce.
Penso che questo fatto e la dimostrazione del secondo punto siano collegate ma non so come.

[giammaria2]

Aggiungo la mia risposta
.

Punto a
Ogni elemento $x$ di S è il prodotto di due fattori maggiori di 1 e questi fattori sono o entrambi uguali a $sqrtx$ o uno maggiore ed uno minore di $sqrtx$: detto $d$ il minore di essi, ho quindi $d>1$ e $d<=sqrtx Per l'inizio della seconda e terza si può anche partire da numeri più bassi, ma già compresi nei casi precedenti; per la terza, la ragione 28 data da Quinzio esclude il 63, anch'esso già considerato.
Noto che queste progressioni coprono un insieme più ampio di S, che arriva fino a 119; nell'intervallo fra 79 e 119 può essere $d=9$, ma i multipli di 9 sono compresi fra quelli di 3.

Punto b
Se ci fossero due sole progressioni, due fra i numeri 49, 51, 55 dovrebbero appartenere ad una stessa progressione con le seguenti caratteristiche: la ragione deve essere un sottomultiplo della differenza fra i due numeri e deve essere pari (altrimenti ci sarebbero anche numeri pari); inoltre la progressione non deve contenere numeri primi. Esaminando i tre possibili accoppiamenti, si vede che questo non può verificarsi.

[axpgn]

Bene!

Due soluzioni più elaborate ...

a) Ogni elemento di $S$ può essere scritto come $(2m+1)(2m+1+2n)$ per opportuni interi $m>=1, n>=0$.
Prendendo $r=1,2,3$ abbiamo $S_1=9, 15, ..., 75$; $S_2=25, 35, ..., 75$ e $S_3=49, 63, 77$.
$S=S_1 uu S_2 uu S_3$

b) Supponiamo sia $S=P uu Q$ dove $P={a, a+b, ..., a+(m-1)b}$ e $Q={c, c+d, ..., c+(n-1)d}$
Senza perdere generalità assumiamo $a=9$ quindi $a+b=15$ o $c=15$.
Nel primo caso $P=S_1$ e perciò $c=25, c+d=35$ da cui $Q=S_2$.
Impossibile perché $49$ sarebbe escluso da entrambe.
Nel secondo caso avremmo $a+b=21$ o $c+d=21$.
Se $a+b=21$ allora $P=9,21,33,45,57,69$ e $c+d=27$ da cui $Q=15,27,39,51,63,75$.
Impossibile perché $49$ sarebbe escluso da entrambe.
Se $c+d=21$ allora $Q=S_1-{9}$ e $a+b=25$ da cui $P=9,25,41,...$ impossibile perché $41$ è primo.

Cordialmente, Alex