Piccioni milanesi 2

[enomis_costa88]

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.

[darkcrystal]

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!

[edriv]

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.

[enomis_costa88]

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