Numeri Fattorizzati
La fattorizzazione in numeri primi di $r+1$ interi positivi ($r>=1$) conivolge in tutto solo $r$ primi. Provare che esiste un sottoinsieme di tali interi il cui prodotto sia un quadrato perfetto. 
Risposte
Riscriviamo il problema in questo modo: siano $p_1,..,p_r$ i primi.
- dati $r+1$ numeri, si associ ad ognuno di essi una stringa di 0 e 1 lunga r, ove l'ennesimo elemento della stringa rappresenta la parità dell'esponente del primo n_esimo nel numero dato. Si denoti con $k(x)$ il valore della stringa al posto x del numero k_esimo. La tesi equivale a dire che esistono $m_1,...,m_k$ t.c. $m_1(i)+...+m_k(i)$ è uguale a 0 modulo 2 per ogni $i=1...r$;
Supponiamo di avere scelto r numeri senza avere mai trovato il sottoinsieme il cui prodotto è un quadrato perfetto.
Oss: le stringhe possibili sono in ogni caso $2^r-1$ (visto che la stringa fatta di tutti 0 equivale ad avere un quadrato perfetto nell'insieme)... [è un fatto noto];
Quindi se noi riusciamo ad escludere almeno $2^r-1$ stringhe per la scelta del $r+1_(esimo)$ numero abbiamo finito, non essendoci più scelte possibili... Basta provare che:
Claim: le stringhe non più ammissibili si trovano prendendo un sottoinsieme qualsiasi dei primi $r$ elementi e le loro relative stringhe, sommandole (come vettori) è prendendo la stringa "complementare" (ovvero sostitudendo gli 0 con gli 1). Queste stringhe sono $2^r-1$, ovvero sono tutte diverse da loro.
dim: che quelle stringhe non siano ammissibili risulta direttamente da come sono state costruite. Il fatto che siano tutte diverse segue dal fatto che se ce ne fossero due uguali riferite a due insiemi di elementi diverse, anche le stringhe riferite agli stessi insiemi di elementi privati dell'intersezione comune sarebbero uguali, e sommando questi elementi con lestringhe uguali si avrebbe un quadrato perfetto, contro le ipotesi.
Mi rendo conto di essere stato incasinato... dite se ci sono errori et similia...
ciao ciao
- dati $r+1$ numeri, si associ ad ognuno di essi una stringa di 0 e 1 lunga r, ove l'ennesimo elemento della stringa rappresenta la parità dell'esponente del primo n_esimo nel numero dato. Si denoti con $k(x)$ il valore della stringa al posto x del numero k_esimo. La tesi equivale a dire che esistono $m_1,...,m_k$ t.c. $m_1(i)+...+m_k(i)$ è uguale a 0 modulo 2 per ogni $i=1...r$;
Supponiamo di avere scelto r numeri senza avere mai trovato il sottoinsieme il cui prodotto è un quadrato perfetto.
Oss: le stringhe possibili sono in ogni caso $2^r-1$ (visto che la stringa fatta di tutti 0 equivale ad avere un quadrato perfetto nell'insieme)... [è un fatto noto];
Quindi se noi riusciamo ad escludere almeno $2^r-1$ stringhe per la scelta del $r+1_(esimo)$ numero abbiamo finito, non essendoci più scelte possibili... Basta provare che:
Claim: le stringhe non più ammissibili si trovano prendendo un sottoinsieme qualsiasi dei primi $r$ elementi e le loro relative stringhe, sommandole (come vettori) è prendendo la stringa "complementare" (ovvero sostitudendo gli 0 con gli 1). Queste stringhe sono $2^r-1$, ovvero sono tutte diverse da loro.
dim: che quelle stringhe non siano ammissibili risulta direttamente da come sono state costruite. Il fatto che siano tutte diverse segue dal fatto che se ce ne fossero due uguali riferite a due insiemi di elementi diverse, anche le stringhe riferite agli stessi insiemi di elementi privati dell'intersezione comune sarebbero uguali, e sommando questi elementi con lestringhe uguali si avrebbe un quadrato perfetto, contro le ipotesi.
Mi rendo conto di essere stato incasinato... dite se ci sono errori et similia...
ciao ciao
Si può risolvere il problema anche con l'algebra lineare. I consideri la matrice A di dimensione $k\times (k+1)$ tale che $A(i,j)=0$ se il primo $p_i$ compare con esponente pari nella fattorizzazione di $r_j$, e $A(i,j)=1$ altrimenti. Questa è una matrice a coefficienti in un campo, il campo degli interi modulo 2. Poniamo ora $A=[F A_{k+1}]$, in cui $F$ è la matrice composta dalle prime $k$ colonne di $A$ e $A_{k+1}$ è la $(k+1)$-esima colonna di $A$. Se le colonne di $F$ sono linearmente dipendenti, allora esiste un vettore $x'!=0$ tale che $Fx'=0$, il che prova che esistono interi fra $r_1,...,r_k$ il cui prodotto è un quadrato perfetto. Se invece le colonne di $F$ sono linearmente indipendenti, allora $F$ è non singolare, dunque esiste un vettore $x'$ tale che $Fx'=A_{k+1}$ e dunque il vettore $[x' 1]$ è tale che $A[x' 1]^T=Fx'+A_{k+1}=A_{k+1}+A_{k+1}=0$, il che prova che esistono interi fra $r_1,...,r_{k+1}$ il cui prodotto è un quadrato perfetto.
Bella fields ... mi piace il tuo utilizzo delle matrici in Z[2] (si chiama così quel campo, o no? vabbè ci siamo capiti... non studio mica algebra 
) ...
guarderò sugli appunti di geometria se quanto hai usato funzia anche per i campi di caratteristica due, ma credo proprio di si... bello!!
... mi piace il tuo utilizzo delle matrici in Z[2] (si chiama così quel campo, o no? vabbè ci siamo capiti... non studio mica algebra ) ... guarderò sugli appunti di geometria se quanto hai usato funzia anche per i campi di caratteristica due, ma credo proprio di si... bello!!
"Thomas":
Bella fields
guarderò sugli appunti di geometria se quanto hai usato funzia anche per i campi di caratteristica due, ma credo proprio di si... bello!!
Grazie, in effetti la nostra soluzione è simile, io ho solo visto la struttura soggiacente.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo