OliForum Matematico

Sia $n$ un intero positivo e sia $S$ l'insieme dei suoi divisori positivi. $n$ è detto buono se è possibile scindere $S$ in due insiemi nonnulli tali che il prodotto degli elementi dei due insiemi sia equivalente.

Trovare (definirli, per l'amor del cielo) tutti i numeri buoni.

Troleito br00tal ha scritto: $n$ è detto buono se è possibile scindere $S$ in due insiemi nonnulli tali che il prodotto degli elementi dei due insiemi sia equivalente.

Meh.

karlosson_sul_tetto ha scritto:Meh.

Quest'utima moda di pure spam inizia a diventare fastidiosa L'esercizio è facile, chi lo risolve?

Lemma della-pulce-dei-provinciali: una pulce su un asse fa \(n\) salti di lunghezza \(1, \ldots, n\), qualcuno a destra, qualcuno a sinistra. Per quali \(n\) potrebbe finire nel punto di partenza?

E' necessario che la somma dei salti sia pari, visto che 0 a quanto dicono lo è. Sfruttando il fatto che \(a \equiv -a \pmod 2 \), la somma dei salti che fa è equivalente modulo 2 a \(\sum_{i=1}^n{i} = \frac{n(n+1)}{2} \pmod 2\). Perchè il vincolo di parità sia soddisfatto, si deve avere \(n(n+1) \equiv 0 \pmod 4\), ossia \(n \equiv 0,3 \pmod 4\).

E' sufficiente che \(n \equiv 0,3 \pmod 4\). Infatti notiamo che, presi 4 numeri consecutivi e appioppandogli i segni + - - +, si annullano, e questo sistema il caso \( n \equiv 0 \pmod 4\). Notando poi che (altra osservazione arguta) 1+2-3 = 0, abbiamo sistemato anche il caso \(n \equiv 3 \pmod 4\).

DIMOSTRAZIONE
Sia \(n = \prod_{i=1}^k{p_i^{\alpha_i}}\), con i \(p_i\) primi. Identifichiamo un divisore \(d(\beta_1, \ldots, \beta_k)\), con \(0 \leq \beta_i \leq \alpha_i\) in modo tale che \(d(\beta_1, \ldots, \beta_k) = \prod_{i=1}^k{p_i^{\beta_i}}\).

Siano \(S,T\) i due insiemi dei divisori, e definiamo \(S_j\) (e similmente \(T_j\) ), la somma degli esponenti \(\beta_j\) di tutti i divisori in \(S\).
Noi vorremmo che \(\prod_{i=1}^k{p_i^{S_i}} = \prod_{i=1}^k{p_i^{T_i}} \), che per motivi di divisibilità (o mille altri) è equivalente a
\( S_i = T_i\), per \(i=1, \ldots, k\). La scriviamo come \(S_i - T_i = 0 \).

Adesso ci chiediamo che numeri ci sono dentro \(S_i \cup T_i \), che nell'equazione compaiono qualcuno con il -, qualcuno con il +. Ci sono di certo i numeri da 1 a \(\alpha_i\), e ognuno di essi compare tante volte quante sono le combinazioni degli altri esponenti tra di loro. Purtroppo però, se vogliamo occuparci di sistemare localmente la situazione, dobbiamo prendere ogni numero una volta sola, fissando la combinazione degli altri esponenti.

Da questo, per il Lemma della-pulce-dei-provinciali, si conclude che \(n\) è buono se e solo se \(\alpha_i \equiv 0,3 \pmod 4 \) per \(i=1, \ldots, k\).

Scusate se l'ho scritto da capra, ma sto un po' di fretta

Non ho ben capito la dimostrazione ma credo ci sia un errore perchè se prendo ad esempio 24=3*2^3 in cui l'esponente di 3 è congruo a 1 mod4, posso comunque dividere i suoi divisori positivi (1,2,3,4,6,8,12,24) in due insiemi in cui il prodotto degli elementi è equivalente (1*2*12*24=576) e (3*4*6*8=576).
Credo che siano buoni tutti i numeri con un numero di divisori multiplo di 4. Infatti si possono dividere i divisori di n in coppie il cui prodotto fa fa n (se non è un quadrato perfetto) e, se posso dividere queste coppie in due insiemi che ne contengono lo stesso numero, in entrambi gli insiemi il prodotto degli elementi sarà uguale.
Restano però ancora da definire i quadrati perfetti buoni (ad esempio 16).

npick ha scritto:Restano però ancora da definire i quadrati perfetti buoni (ad esempio 16).

Ma, se non ho letto male il problema, non è richiesto che gli insiemi contengano lo stesso numero di elementi... quindi, i divisori di 16 $ d={1, 2, 4, 8, 16} $ possono essere divisi in $ {1, 2, 16}=32 $ e $ {4, 8}=32 $.
Lo stesso non si può fare per 64, per esempio.
In generale (indipendentemente se la dimostrazione che c'è sopra comprende i miei casi, dato che non credo di averla compresa appieno...) affermo che un quadrato perfetto è buono se l'esponente della sua base è 4n (con n>0).

Visto che ci provano tutti ci provo anche io
Dunque, come è già stato fatto notare, ogni primo che divide n deve comparire un numero pari di volte nel prodotto fra i divisori.
Quante volte compare ogni primo?
Sia $ n=p_1^{a_1}...p_n^{a_n} $
Fra i divisori di n, p con esponente esattamente 1 compare in $ (a_2+1)(a_3+1)...(a_n+1) $ divisori
Anche p con esponente esattamente 2 compare in $ (a_2+1)...(a_n+1) $ divisori . Quindi nel prodotto totale fra i divisori in cui compare esattamente p^2, abbiamo $ 2\cdot (a_2+1)...(a_n+1) $ volte il fattore p
Più in generale, nel prodotto fra i divisori in cui compare $ p^i, $ il fattore p compare $ i\cdot (a_2+1)...(a_n+1) $
Quindi nel nostro caso, nel prodotto dei divisori di n, p compare $ (a_1)(a_1+1)(a_2+1)...(a_n+1)\cdot \tfrac {1}{2}=\tfrac {1}{2}(a_1)\cdot d(n) $ con d(n) il numero di divisori di n.
Questa quantità deve essere pari, quindi $ (a_1)d(n) $ deve essere multipla di 4
Ciò deve valere per ogni primo, quindi la quantità $ (a_i)d(n) $ deve essere multipla di 4 per ogni i.
Ora ci sarebbe da mostrare i casi in cui questa avviene e mostrare che è condizione sufficiente (sempre che lo sia)

Si, intendevo che ho definito tutti gli n non quadrati perfetti buoni, ma non ho definito i quadrati buoni (come 16).
Però adesso ho dimostrato che devono essere anche potenze quarte...