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.
Giuro che questa non è spam ma in realtà questa lo è
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: Giuro che questa non è spam ma in realtà questa lo è
Meh.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.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
Re: Giuro che questa non è spam ma in realtà questa lo è
Quest'utima moda di pure spam inizia a diventare fastidiosa L'esercizio è facile, chi lo risolve?karlosson_sul_tetto ha scritto:Meh.
The only goal of science is the honor of the human spirit.
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Giuro che questa non è spam ma in realtà questa lo è
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
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
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: Giuro che questa non è spam ma in realtà questa lo è
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).
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).
Re: Giuro che questa non è spam ma in realtà questa lo è
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 $.npick ha scritto:Restano però ancora da definire i quadrati perfetti buoni (ad esempio 16).
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).
"Qual é 'l geomètra che tutto s'affige
per misurar lo cerchio, e non ritrova,
pensando, quel principio ond'elli indige,
tal era io a quella vista nova:
veder voleva come si convenne
l'imago al cerchio e come vi s'indova"
per misurar lo cerchio, e non ritrova,
pensando, quel principio ond'elli indige,
tal era io a quella vista nova:
veder voleva come si convenne
l'imago al cerchio e come vi s'indova"
Re: Giuro che questa non è spam ma in realtà questa lo è
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)
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)
"We' Inge!"
LTE4LYF
LTE4LYF
Re: Giuro che questa non è spam ma in realtà questa lo è
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...
Però adesso ho dimostrato che devono essere anche potenze quarte...