OliForum Matematico

Siano dati 81 interi positivi, nessuno dei quali ha un divisore primo maggiore di 5. Mostrare che possiamo sceglierne 4 il cui prodotto è una potenza quarta.

Beh, molto ad occhio... Ci sono tre divisori primi permessi, e cioè 2, 3 e 5, e 81 è proprio 3 alla quarta..........

Quello infatti è il testo.. mò?

Eh, ma appunto, poiché ho $ 3^4 $ numeri a disposizione, il mio sesto senso mi dice che la tesi è vera... In realtà non so come si dimostra, anche se, per mia parziale soddisfazione, ho pensato che deve c'entrare la combinatoria più che l'aritmetica, senza prima vedere in quale sezione del forum ci troviamo...

jordan ha scritto:Siano dati 81 interi positivi, nessuno dei quali ha un divisore primo maggiore di 5. Mostrare che possiamo sceglierne 4 il cui prodotto è una potenza quarta.

Dunque, i numeri che ci interessano conterranno, con gli indici modulo 4, i fattori: 2, 2², 2³, 3, 3², 3³, 5, 5², 5³, e le loro possibili combinazioni, che sono 9+27+27 < 81 se saranno tutti diversi. In questo caso basta prendere 2³, 3³, 5³ e 2x3x5, oppure un loro qualsiasi prodotto per una potenza quarta. Qualora venissero usate ripetizioni modulo 4, basta prendere i prodotti sommando i valori modulo 4 in modo che diano 0 (mod 4). Lo so, come dimostrazione vale meno di zero, però almeno ci ho provato.

@Enrico Leon, tranquillo era ironico comunque a me a prima vista avrebbe ispirato più un 82..

@sasha, si quello che ci interessa è come contano gli indici modulo 4; ciò che non capisco è: perchè le combinazioni sono 9+27+27? E perchè solo 2³, 3³, 5³ e 2x3x5 quando ce ne servono 4?
ps. dove hai trovato la tabella dei caratteri unicode, li hai salvati su un file?
ps2. questo problema è tratto da un'olimpiade molto recente di una nazione molto vicina

jordan ha scritto:@Enrico Leon, tranquillo era ironico comunque a me a prima vista avrebbe ispirato più un 82..

@sasha, si quello che ci interessa è come contano gli indici modulo 4; ciò che non capisco è: perchè le combinazioni sono 9+27+27? E perchè solo 2³, 3³, 5³ e 2x3x5 quando ce ne servono 4?
ps. dove hai trovato la tabella dei caratteri unicode, li hai salvati su un file?
ps2. questo problema è tratto da un'olimpiade molto recente di una nazione molto vicina

Era un esempio come un altro, se moltiplichi quei fattori ottieni 30^4. Comunque so anch'io che la mia non era una dimostrazione, volevo fornire qualche spunto a qualcuno più esperto. Per le combinazioni, erano 9 combinazioni con un unico fattore, 27 con una coppia e 27 con tutti e tre, senza contare i relativi indici. Non so se mi spiego.

Ps. No, i caratteri li faccio con AbcTajpu.

sasha™ ha scritto:Per le combinazioni, erano 9 combinazioni con un unico fattore, 27 con una coppia e 27 con tutti e tre, senza contare i relativi indici.

Tipo 2^4 dov'è?
(Cos'è AbcTajpu?che li inserisci colla tastiera numerica?)

jordan ha scritto:

sasha™ ha scritto:Per le combinazioni, erano 9 combinazioni con un unico fattore, 27 con una coppia e 27 con tutti e tre, senza contare i relativi indici.

Tipo 2^4 dov'è?
(Cos'è AbcTajpu?che li inserisci colla tastiera numerica?)

Sto considerando gli indici in modulo 4, se moltiplico 2^4 o 1, al fine di ottenere una potenza quarta è ininfluente.

Ps. AbcTajpu è un'applicazione aggiuntiva per Firefox

Allora ci potresti rispiegare tutto con calma? in particolar modo che sono quei 27?e dove consideri che il prodotto è di 4 numeri?

cmq se consideriamo anche il caso in cui tutti e 3 gli indici siano 0, $ ~(9+27+27)+1=64=4^3 $
e infatti abbiamo 3 indici che possono essere scelti tra 4 valori
domanda: quante coppie di numeri con la stessa notazione abbiamo?

Ci provo, ma con le spiegazioni sono una frana. Dunque, se quei numeri hanno come fattori solo 2, 3 e 5, e noi dobbiamo scegliere 4 di quei numeri e moltiplicarli per ottenere una quarta potenza, agiamo così:
Caso 1) Non ci sono numeri con la stessa fattorizzazione considerando gli indici in modulo 4. Ovvero, considerando 2^4 congruo 2^8, 2^3 congruo 2^7 e così via. Tutti i possibili fattori (gli indici sono sempre modulo 4) sono 2, 2², 2³, 3, 3², 3³, 5, 5², 5³ e le relative combinazioni, che sono in totale 63 (ovviamente senza combinare basi uguali). Siccome 63 < 81, e sapendo che con quei fattori in nostro possesso possiamo moltiplicare tra loro (ad esempio) 2³, 3³, 5³ e 2x3x5, con questo prodotto possiamo ottenere una quarta potenza, cvd. Un'alternativa sarebbero 2², 3², 2²x5², 3²x5². Il prodotto è comunque una quarta potenza.
Caso 2) Sono presenti numeri con la stessa fattorizzazione (sempre con gli indici modulo 4). Se vi sono almeno 4 fattori con indice congruo a 0 modulo 4, la tesi è dimostrata (basta moltiplicarli). Se non sono presenti, ma sono presenti almeno sette fattorizzazioni che contengono un solo primo (o più primi con esponenti uguali, a patto che siano gli stessi primi in tutti e sette i casi), potrò sempre sommare gli indici di quattro di loro in modo che siano congrui a 0 modulo 4, e ottenere una quarta potenza. Resta da dimostrare che ci sono almeno sette prodotti di primi uguali e con lo stesso indice modulo 4 (es. 2x3 e 2³x3³, ma anche 2³x3³¹) su 81 numeri. Non dovrebbe essere difficile, ma non so come si fa.

Sono stato chiaro? (No.)

EDIT: Ringrazio SkZ per aver dato una base a quello che ho detto. In effetti era semplice, stupido io a non averci pensato.

sasha ti consiglio di leggere la domanda che ho aggiunto sopra.
il tuo ragionamento si avvicina.

SkZ ha scritto:sasha ti consiglio di leggere la domanda che ho aggiunto sopra.
il tuo ragionamento si avvicina.

In che senso "coppie di numeri con la stessa notazione"?

in questo caso 2 numeri del tipo $ ~a^\alpha b^\beta c^\gamma $ hanno la stessa notazione se
$ ~\alpha_1\equiv\alpha_2\pmod{4}\quad\beta_1\equiv\beta_2\pmod{4}\quad\gamma_1\equiv\gamma_2\pmod{4} $
per pigeon hole so che ho almeno 1 coppia.
da considerare che se ho 4 numeri con la stessa notazione, essi formano 2 coppie.
Si puo' dimostrare che abbiamo almeno # coppie di numeri con la stessa notazione.