Mio Problema di Natale 2006

[Mistral2]

Determinare il più piccolo valore del numero naturale $n>3$ con la proprietà che comunque si partizioni in due sottoinsiemi l'insieme $S_{n}={3,4,...,n}$, almeno uno dei due sottoinsiemi contiene tre numeri $a,b,c$ non necessariamente distinti tali che $ab=c$.

Saluti e Auguroni

Mistral

PS. Attenzione è meno semplice di quello che sembra.

[Sk_Anonymous]

"Mistral":Determinare il più piccolo valore del numero naturale $n>3$ con la proprietà che comunque si partizioni in due sottoinsiemi l'insieme $S_{n}={3,4,...,n}$, almeno uno dei due sottoinsiemi contiene tre numeri $a,b,c$ non necessariamente distinti tali che $ab=c$.

PS. Attenzione è meno semplice di quello che sembra.

Se $a, b, c$ non devono essere necessariamente a due a due distinti, allora la risposta, in effetti, non è semplice - è a dir poco evidente (n = 4)!

Se invece, come presumo che sia, gli interi $a, b, c$ debbono essere a due a due distinti, allora è chiaro che $n \le 12$. Sia infatti {A, B} una qualunque partizione dell'insieme $S_{12}$. Se $0 \le |A| \le 2$, almeno una delle coppie (3,6), (3,9), (3,12), (6,12), (4,8) appartiene a B. Sia dunque $|A| \ge 3$. Poniamo $A = \{a_1, a_2, ...\}$ e ammettiamo, senza perdita di generalità, $a_1 = 3$. Se $a_2 \in \{6, 9, 12\}$, abbiamo finito. Diversamente $6, 12 \in B$. In entrambi i casi, $\{A, B\}$ verifica la proprietà postulata dalla consegna del problema.

D'altronde, se $n < 12$, allora gli insiemi $A = S_n \cap \{3, 7, 8, 10, 11\}$ e $B = S_n \cap \{4, 5, 6\}$ determinano una partizione di $S_n$ che non soddisfa la proprietà alla mano. La risposta al quesito proposto è pertanto $n = 12$, senza neppure troppo sforzo.

[Aethelmyth]

Non seguo il ragionamento...
Nel caso non debbano essere necessariamente a due a due distinti come fa ad essere $n=4$? Le partizioni sono ${3}$, ${4}$ o ${3,4}$, ${0}$; ed in ogni caso non mi sembra corretto scrivere $3*3=3$ o $4*4=4$. La domanda richiedeva "comunque presi due sottoinsiemi...". Se fosse stato possibile prendere $n=3$ allora sarebbe stato la soluzione ma c'è una condizione per $n>3$

Mi sembra valga lo stesso discorso per la tua seconda soluzione.

[Sk_Anonymous]

Ooops... Soltanto adesso mi rendo conto di aver risolto un ALTRO problema! E cioè "determinare il minimo n intero > 3 tale che, comunque scelta una partizione {A, B} dell'insieme $S_n = {3, 4, ..., n}$, esistono due elementi $a, b$ entrambi appartenenti ad $A$ oppure a $B$ tali che $a = bc$, per qualche $c \in NN$." Ehm... Non chiedetemi come sia potuto succedere, non lo so - forse lo spumante era scaduto!?

[Sk_Anonymous]

"Mistral":Determinare il più piccolo valore del numero naturale $n>3$ con la proprietà che comunque si partizioni in due sottoinsiemi l'insieme $S_{n}={3,4,...,n}$, almeno uno dei due sottoinsiemi contiene tre numeri $a,b,c$ non necessariamente distinti tali che $ab=c$.

Vediamo di rimediare alla disattenzione, mostrando che dev'essere $n = 243$. Per assurdo, sia determinata una partizione {A, B} di $S_{243}$ tale che non esistano elementi (a due a due non necessariamente distinti) $a, b, c$ appartenenti tutti ad A o tutti a B per cui $ab = c$. Wlog, possiamo ammettere $3 \in A$. Allora necessariamente $9 \in B$ e $81 \in A$, e di conseguenza $27, 243 \in B$, i.e. ${3, 81} \subseteq A$ e ${9, 27, 243} \subseteq B$. Senonché $243 = 9 \cdot 27$, assurdo! Ne risulta $n \le 243$.

Supposto d'altro canto $n < 243$ e detto $P$ l'insieme dei numeri primi naturali $\ge 3$, osserviamo che un qualsiasi intero $q \in [3, n]$ possiede necessariamente non più di tre divisori primi distinti $\in P$, salvo altrimenti dedurne $q \ge 3 \cdot 5 \cdot 7 \cdot 11 > 243$. Pertanto $q$ è a forza del tipo $2^k p_1^a p_2^b p_3^c$, dove $a, b, c, k \in NN$ sono opportuni interi non negativi e $p_1, p_2, p_3$ primi di $P$ a due a due distinti. Sia dunque {C, D} la coppia di $NN$-sottoinsiemi definita assumendo che

i) $2^2, 2^3, 2^7 \in C$ e $2^4, 2^5, 2^6 \in D$;

ii) $p, 2p, 2^6 p \in C$ e $2^2 p, 2^3 p, 2^4 p, 2^5 p \in D$, al variare di $p \in P$;

iii) $2^4 p^2 \in C$ e $p^2, 2p^2, 2^2 p^2, 2^3 p^2 \in D$, al variare di $p \in P$;

iv) $2^2 p^3, 2^3 p^3 \in C$ e $p^3, 2p^3 \in D$, al variare di $p \in P$;

v) $p^4, 2p^4 \in C$ , al variare di $p \in P$;

vi) $2^3 pq, 2^4 pq \in C$ e $pq, 2pq, 2^2 pq \in D$, al variare di $p, q \in P$, dato $p \ne q$;

vii) $2^2 p^2 q \in C$ e $p^2 q, 2p^2 q \in D$, al variare di $p, q \in P$, dato $p \ne q$;

viii) $p^3 q, p^2 q^2 \in C$, al variare di $p, q \in P$, dato $p \ne q$;

ix) $pqr, 2pqr \in C$, al variare di $p, q, r \in P$, dato $p \ne q \ne r \ne p$.

A questo punto, considerando che, dati $a, b, c, k \in NN$ e $p_1, p_2, p_3 \in P$ a due a due distinti:

1) $2^k \in S_n$ solo se $2 \le k \le 7$;

2) $2^k p_1^a \in S_n$ solo se $a \le 4$ e $k \le 6$, e anzi più precisamente - trascurando i casi già compresi al punto precedenti - solo se $(a,k)$ è del tipo $(1,k)$, con $0 \le k \le 6$; oppure $(2,k)$, con $0 \le k \le 4$; o $(3, k)$, con $0 \le k \le 3$; o ancora $(4,k)$, con $k = 0, 1$;

3) $2^k p_1^a p_2^b \in S_n$ solo se - trascurando i casi già compresi ai punti precedenti - $(a,b,k)$ è del tipo $(1,1,k)$, con $0 \le k \le 4$; oppure $(2,1,k)$, con $0 \le k \le 2$; o ancora $(3,1,1)$ o $(2,2,1)$;

4) $2^k p_1^a p_2^b p_3^c \in S_n$ solo se $a= b = c = 1$ e $k = 0$ oppure $k = 1$;

è immediato stabilire (per quanto assai noioso, visto il numero esorbitante di casi da considerare) che $A = C \cap S_n$ e $B = D \cap S_n$ determinano una partizione dell'insieme $S_n$ in cui, comunque scelti $a, b, c \in A$ (risp., $\in B$): $ab \ne c$. Per dedurne effettivamente che $n = 243$ è la risposta al quesito proposto.

[Mistral2]

"DavidHilbert":

.....Ne risulta $n \le 243$.

Ok questa parte.

"DavidHilbert":
Supposto d'altro canto $n < 243$ e detto $P$ l'insieme dei numeri primi naturali $\ge 3$, osserviamo che un qualsiasi intero $q \in [3, n]$ possiede necessariamente non più di tre divisori primi distinti $\in P$, salvo altrimenti dedurne $q \ge 3 \cdot 5 \cdot 7 \cdot 11 > 243$. Pertanto $q$ è a forza del tipo $2^k p_1^a p_2^b p_3^c$, dove $a, b, c, k \in NN$ sono opportuni interi non negativi e $p_1, p_2, p_3$ primi di $P$ a due a due distinti. Sia dunque {C, D} la coppia di $NN$-sottoinsiemi definita assumendo che

i) $2^2, 2^3, 2^7 \in C$ e $2^4, 2^5, 2^6 \in D$;

ii) $p, 2p, 2^6 p \in C$ e $2^2 p, 2^3 p, 2^4 p, 2^5 p \in D$, al variare di $p \in P$;

iii) $2^4 p^2 \in C$ e $p^2, 2p^2, 2^2 p^2, 2^3 p^2 \in D$, al variare di $p \in P$;

iv) $2^2 p^3, 2^3 p^3 \in C$ e $p^3, 2p^3 \in D$, al variare di $p \in P$;

v) $p^4, 2p^4 \in C$ , al variare di $p \in P$;

vi) $2^3 pq, 2^4 pq \in C$ e $pq, 2pq, 2^2 pq \in D$, al variare di $p, q \in P$, dato $p \ne q$;

vii) $2^2 p^2 q \in C$ e $p^2 q, 2p^2 q \in D$, al variare di $p, q \in P$, dato $p \ne q$;

viii) $p^3 q, p^2 q^2 \in C$, al variare di $p, q \in P$, dato $p \ne q$;

ix) $pqr, 2pqr \in C$, al variare di $p, q, r \in P$, dato $p \ne q \ne r \ne p$.

A questo punto, considerando che, dati $a, b, c, k \in NN$ e $p_1, p_2, p_3 \in P$ a due a due distinti:

1) $2^k \in S_n$ solo se $2 \le k \le 7$;

2) $2^k p_1^a \in S_n$ solo se $a \le 4$ e $k \le 6$, e anzi più precisamente - trascurando i casi già compresi al punto precedenti - solo se $(a,k)$ è del tipo $(1,k)$, con $0 \le k \le 6$; oppure $(2,k)$, con $0 \le k \le 4$; o $(3, k)$, con $0 \le k \le 3$; o ancora $(4,k)$, con $k = 0, 1$;

3) $2^k p_1^a p_2^b \in S_n$ solo se - trascurando i casi già compresi ai punti precedenti - $(a,b,k)$ è del tipo $(1,1,k)$, con $0 \le k \le 4$; oppure $(2,1,k)$, con $0 \le k \le 2$; o ancora $(3,1,1)$ o $(2,2,1)$;

4) $2^k p_1^a p_2^b p_3^c \in S_n$ solo se $a= b = c = 1$ e $k = 0$ oppure $k = 1$;

è immediato stabilire (per quanto assai noioso, visto il numero esorbitante di casi da considerare) che $A = C \cap S_n$ e $B = D \cap S_n$ determinano una partizione dell'insieme $S_n$ in cui, comunque scelti $a, b, c \in A$ (risp., $\in B$): $ab \ne c$. Per dedurne effettivamente che $n = 243$ è la risposta al quesito proposto.

Questa parte può essere migliorata. Infatti basta dimostrare che $S_{242}$ ammette una partizione ${A,B}$ che non soddisfa l'asserto chiaramente per $3
Sia $C$ l'insieme degli elementi di $S_{242}$ che non sono prodotto di elementi di $S_{242}$, allora $C$ è costituito da $4$ $8$, $p$, $2p$ dove $p$ è un primo dispari con $p<242$. Siccome il primo più piccolo in $S_{242}$ è $3$, nessun numero in $S_{242}$ è il prodotto di più di 4 elementi di $C$ eventualmente ripetuti. Definiamo quindi $A$ come l'insieme degli elementi di $S_{242}$ che sono il prodotto di 4 elementi di $C$ non necessariamente distinti più gli elementi di $C$. Poniamo $B=S_{242}-A$.
Segue che nessun prodotto di elementi di $B$ è in $B$, dato che il loro prodotto ha almeno 4 elementi di $C$. Infine considerando prodotti tra due elmenti di $C\subset A$, cioè del tipo $4$ $8$, $p$, $2p$ ($p$ primo dispari con $p<242$) nessuno di essi è esprimibile come il prodotto di 4 elementi di $C$. Risulta quindi costruita la partizione.

Auguroni a tutti e Complimenti a DavidHilbert

Mistral

[Sk_Anonymous]

"Mistral":
Questa parte può essere migliorata. Infatti basta dimostrare che $S_{242}$ ammette una partizione ${A,B}$ che non soddisfa l'asserto [...] Sia $C$ l'insieme degli elementi di $S_{242}$ che non sono prodotto di elementi di $S_{242}$, allora $C$ è costituito da $4$ $8$, $p$, $2p$ dove $p$ è un primo dispari con $p<242$. Siccome il primo più piccolo in $S_{242}$ è $3$, nessun numero in $S_{242}$ è il prodotto di più di 4 elementi di $C$ eventualmente ripetuti. Definiamo quindi $A$ come l'insieme degli elementi di $S_{242}$ che sono il prodotto di 4 elementi di $C$ non necessariamente distinti più gli elementi di $C$. Poniamo $B=S_{242}-A$. [...]

Molto meglio, sì. E auguroni anche a te, Mistral.