OliForum Matematico

Ancora piccioni, stavolta dalla telematica dell'unimi (il primo quesito).

Sono dati n+1 numeri tali che siano scomponibili usano solo n numeri primi.

Dimostrare che posso sceglierne alcuni in modo tale che il prodotto di questi (ogni numero usato al più una volta) sia un quadrato perfetto.

Niente piccioni per me, ma ci provo lo stesso...
Per n=2 è facile verificare che è vero: si tratta di considerare, infatti, solo la congruenza modulo 2 degli esponenti.
Ora, supponiamo che sia vero per n e proviamolo per n+1.
Scegliamo un primo della scomposizione come "nuovo primo"
Tra gli (n+2) numeri, scegliamone a caso (n+1). Tra questi, ne possiamo scegliere alcuni tali che il loro prodotto sia un quadratto perfetto, a meno dell'ultimo primo.
Ora, scartiamo uno dei numeri che abbiamo moltiplicato e aggiungiamo quello che non avevamo preso in considerazione: nuovamente, possiamo trovarne alcuni con la stessa caratteristica di prima (ma distinto da esso, poichè uno dei fattori è stato escluso).
Ora, o uno di questi due è un quadrato, e allora siamo a posto, oppure il loro prodotto è un quadrato perfetto (perchè l'esponente del "nuovo primo" era dispari in entrambi): inoltre, abbiamo usato ogni numero o una volta sola, o due volte. Ma se l'abbiamo usato due volte, il prodotto è un quadrato perfetto anche escludendo quelli usati due volte (perchè sono quadrati anch'essi)

Ciao!

Mia soluzione:

Ad ogni multiplo dei primi $ \displaystyle p_1,\ldots,p_n $ associamo la stringa binaria di lunghezza n in cui il k-esimo carattere è parità dell'esponente dell'k-esimo primo.
Questo insieme di stringhe è chiaramente lo spazio vettoriale $ \displaystyle \mathbb{Z}_2^n $, dove la somma di stringhe binarie (mod 2) equivale a trovare il prodotto di due numeri. Questo spazio vettoriale ha dimensione n.
Noi abbiamo n+1 numeri (distinti, se ce ne sono due uguali ottengo subito il quadrato), a cui associamo n+1 stringhe binarie. Per il teorema della dimensione dello spazio vettoriale, queste sono linearmente dipendenti e quindi una loro combinazione lineare (a coefficienti 0 e 1) dà (0,0,...) ovvero, il prodotto di alcuni numeri ha tutti gli esponenti pari.

Ho usato un po' di parolone che non avrei dovuto usare , bastava dire che se tutti i loro prodotti fossero distinti trovo 2^{n+1} stringhe diverse, troppe. Se ne trovo due uguali, la loro differenza è 0.
Però secondo me è utile tenere a mente il teorema della dimensione dello spazio vettoriale in certi problemi di combinatoria.

edriv ha scritto: bastava dire che se tutti i loro prodotti fossero distinti trovo 2^{n+1} stringhe diverse, troppe.

questa era la mia soluzione (due stringhe nello stesso cassetto)..comunque sempre interessanti gli approfondimenti.

Caspiterina..non mi ero accorto della bella soluzione di darkcrystal