ti dividerò per sempre!

[salva90]

Invocavate problemi facili ed io vi accontento...

Determinare il più piccolo n tale che $ abc|(a+b+c)^n $ per ogni scelta di tre interi positivi a, b, c tali che $ a|b^3,~b|c^3,~c|a^3 $

Pregherei chi ha già partecipato ad uno stage, chi non l'ha mai fatto ma si reputa 'esperto', gabriel, e soprattutto chi non ha più l'età di olimpiadi di non rispondere a questo problema

[Bellaz]

Scusate la mia ignoranza, ma $ | $ vuol dire "divisibile"??

[EUCLA]

a $ \vert $ b = a divide b

[angus89]

Scusate la mia ignoranza, ma $ | $ vuol dire "divisibile"??

vuol dire propriamente "divide"...
se a|b allora b è multiplo di a

Tipo è giusto dire che 2|8

[Bellaz]

ok grazie dell'informazione...

[Bellaz]

Sicuramente è sbagliato, ma per caso la risposta è 3??

[salva90]

Sicuramente è sbagliato, ma per caso la risposta è 3??

prova a cercare un controesempio

[Agi_90]

Sicuramente è sbagliato, ma per caso la risposta è 3??

be' se provi con $ 2\cdot 3 \cdot 5^2, 2^2\cdot 3^2 \cdot 5^2, 2\cdot 3^2 \cdot 5^2 $ vedi che non va .

Io ho risolto così:

[EDIT] dimostrazione riscritta[/EDIT]
Definiamo $ P_i $ l'insieme dei numeri primi che dividono $ i $.
dalle tre relazioni abbiamo che $ P_A \subseteq P_B \land P_B \subseteq P_A \land P_C \subseteq P_A $ $ \Rightarrow P_A = P_B = P_C $.
quindi possiamo scrivere $ a, b, c $ come:

$ a = p_1^{a_1}\cdot p_2^{a_2}\cdot \ldots \cdot p_k^{a_k} $
$ b = p_1^{b_1}\cdot p_2^{b_2}\cdot \ldots \cdot p_k^{b_k} $
$ c = p_1^{c_1}\cdot p_2^{c_2}\cdot \ldots \cdot p_k^{c_k} $

sempre dalle relazioni otteniamo che $ a_i \le 3b_i \land b_i \le 3c_i \land c_i \le 3a_i $
da cui $ \displaystyle \frac{max\{a_i,b_i,c_i\}}{min\{a_i,b_i,c_i\}} \le 3 $ (basta notare che il sistema è simmetrico rispetto a a_i,b_i,c_i e poi sostituire a una n e a un'altra 3n+1 e vedere che non va bene.)

detto $ x_i := min\{a_i, b_i, c_i\} $
sappiamo che nel prodotto $ abc $, l'esponente di $ p_i $ potrà essere massimo $ 7x_i $. Ma quindi ci troveremo un fattore $ p_i^{7x_i} $ a sinistra, e un $ p_i^{x_in} $ a destra, da cui $ n \geq 7 $ (credo )

ok così ho dimostrato che con $ n \geq 7 $ va bene... ma non che sia il minimo.

be' facciamola così:

$ a = 2, b = 2^3, c = 2^3 $

così viene: $ 2^7 | 2^n(2^3+1) $ Il secondo termine a destra è chiaramente dispari, quindi $ 2^7|2^n $ da cui si vede che $ n \le 6 $ non puo' andare (vale quindi da controesempio per i valori di n minori.
quindi $ n = 7 $ è il minimo.[]

(che belle le due quadre alla fine )

[Sesshoumaru]

sempre dalle relazioni otteniamo che $ a_i \le 3b_i \land b_i \le 3c_i \land c_i \le 3a_i $

[...]

detto $ x_i := min\{a_i, b_i, c_i\} $
sappiamo che nel prodotto $ abc $, l'esponente di $ p_i $ potrà essere massimo $ 7x_i $. Ma quindi ci troveremo un fattore $ p_i^{7x_i} $ a sinistra, e un $ p_i^{x_in} $ a destra, da cui $ n \geq 7 $ (credo )

Premetto che di TdN non so un'acca, ma non mi torna molto questa cosa
Se io prendo (come esponenti) a = 1, b = 9, c = 3, la relazione torna, il minimo è 1, ma il prodotto è ben più di 7 (questa cosa può valere per tutti gli a_i, b_i, c_i se metti per esempio come numeri $ a = 2 \cdot 3, b = 2^9 \cdot 3^9, c = 2^3 \cdot 3^3 $)

Sbaglio qualcosa?

[Agi_90]

Sbaglio qualcosa?

no sono io che ho sbagliato i calcoli

[Bellaz]

detto $ x_i := min\{a_i, b_i, c_i\} $
sappiamo che nel prodotto $ abc $, l'esponente di $ p_i $ potrà essere massimo $ 7x_i $.

Non mi è chiaro questo passaggio. Scusate ma devo imparare a fare le dimostrazioni.. Ho scoperto che mi manca molta teoria (quest'estate mi metterò a studiare seriamente).. Colpa anche della scuola, in cui non si fa il calcolo combinatorio né nient'altro di olimpico..

Difatti io lo avevo dimostrato solo se $ a=b=c $ e non me ne ero accorto. Comunque io avevo seguito un'altra strada. Avevo dimostrato se $ a=b=c $ e poi, ma mi sono scordato, se $ a<>b<>c $.
<> diverso

[Agi_90]

Definiamo $ P_i $ l'insieme dei numeri primi che dividono $ i $.
dalle tre relazioni abbiamo che $ P_A \subseteq P_B \land P_B \subseteq P_A \land P_C \subseteq P_A $ $ \Rightarrow P_A = P_B = P_C $.
quindi possiamo scrivere $ a, b, c $ come:

$ a = p_1^{a_1}\cdot p_2^{a_2}\cdot \ldots \cdot p_k^{a_k} $
$ b = p_1^{b_1}\cdot p_2^{b_2}\cdot \ldots \cdot p_k^{b_k} $
$ c = p_1^{c_1}\cdot p_2^{c_2}\cdot \ldots \cdot p_k^{c_k} $

sempre dalle relazioni otteniamo che $ a_i \le 3b_i \land b_i \le 3c_i \land c_i \le 3a_i $
da cui $ ai \le 3b_i \le 3^2c_i \le 3^3a_i \le 3^4 b_i \le 3^5 c_i $.
detto $ x_i := min\{a_i, b_i, c_i\} $
Ponendo a turno $ a_i, b_i, c_i $ come esponente minimo, si vede che il massimo che puo' raggiungere uno dei due esponenti è $ 9x_i $ e per l'altro $ 3x_i $
(sta volta dovrebbe funzionare)


sappiamo che nel prodotto $ abc $, l'esponente di $ p_i $ potrà essere massimo $ 13x_i $. Ma quindi ci troveremo un fattore $ p_i^{13x_i} $ a sinistra, e un $ p_i^{x_in} $ a destra, da cui $ n \geq 13 $ (credo )

ok così ho dimostrato che con $ n \geq 13 $ va bene... ma non che sia il minimo.

poniamo:

$ a = 2, b = 2^9, c = 2^3 $

così viene: $ 2^{13} | 2^n(1+2^8+2^2) $ Il secondo termine a destra è chiaramente dispari, quindi $ 2^{13}|2^n $ da cui si vede che $ n \le 12 $ non puo' andare (vale quindi da controesempio per i valori di n minori.
quindi $ n = 13 $ è il minimo.[]

[Agi_90]

detto $ x_i := min\{a_i, b_i, c_i\} $
sappiamo che nel prodotto $ abc $, l'esponente di $ p_i $ potrà essere massimo $ 7x_i $.

Non mi è chiaro questo passaggio. Scusate ma devo imparare a fare le dimostrazioni.. Ho scoperto che mi manca molta teoria (quest'estate mi metterò a studiare seriamente).. Colpa anche della scuola, in cui non si fa il calcolo combinatorio né nient'altro di olimpico..

Difatti io lo avevo dimostrato solo se $ a=b=c $ e non me ne ero accorto. Comunque io avevo seguito un'altra strada. Avevo dimostrato se $ a=b=c $ e poi, ma mi sono scordato, se $ a<>b<>c $.
<> diverso

Be' in realtà lì avevo sbagliato i conti.
Comunque ho ragionato così: sappiamo che a,b e c hanno la stessa fattorizzazione a meno degli esponenti, e risolvendo il sistema di disequazioni sappiamo che al massimo un esponente (di un primo) in uno tra a, b e c puo' valere 9 volte quello più piccolo e che l'altro (quello che rimane) puo' valere massimo 3 volte quello minimo; quindi un singolo primo, nel prodotto abc avrà un esponente che sarà al più 3+9+1=13 volte superiore a quello minimo. Dall'altro lato ($ (a+b+c)^n $), se poniamo x_i come esponente minimo di p_i, sappiamo che sicuramente potremo raccogliere $ p_i^{x_i} $. Da questo n>=13 che funziona sicuro ( a meno di errori nella dimostrazione)

[Sesshoumaru]

Forse ce l'ho: $ n= 13 $

Vediamo se torna:

Innanzitutto dobbiamo avere che $ abc | a^n \land abc | b^n \land abc | c^n $

wlog consideriamo solo $ abc | a^n $, gli altri sono simmetrici

Possiamo subito semplificare e otteniamo $ b|a^{n-4} $
Da $ c|a^3 $ abbiamo che $ c^3 | a^9 $, ma poichè $ b|c^3 $ allora $ b|a^9 $. (1)
Dunque $ b|a^9 $ e $ b|a^{n-4} $, segue $ n = 13 $.

Che $ a^9 $ sia la potenza minima di a divisibile per ogni b lo vediamo dalla relazione di Agi_90: $ a_i \le 3b_i \land b_i \le 3c_i \land c_i \le 3a_i $
Il caso limite di questa relazione è che $ c_i = 3a_i $ e $ b_i=9a_i $, dunque in questo caso la prima potenza di a divisibile per b è proprio $ a^9 $.

Ci rimane quindi da controllare che 13 "vada bene" anche per gli altri termini del polinomio.

Ovviamente i termini in cui compaiono sia a che b che c sono sempre divisibili per abc. Dobbiamo quindi analizzare i termini del tipo $ a^kb^{13-k} $, $ a^kc^{13-k} $,$ b^kc^{13-k} $.

Wlog consideriamo solo $ a^kb^{13-k} $, sempre per simmetria.
Per $ k= 0 $ abbiamo già visto che va bene.
Per $ k>4 $, il termine in b lo dividiamo per b, mentre il termine in a lo dividiamo per ac, poichè se $ c|a^3 $ allora $ ac|a^4 $ (e maggiori).
Per $ 0<k<4 $ il termine in a lo dividiamo sempre per a, il termine in b per b, e ci rimane $ c|a^{k-1}b^{12-k} $.
L'esponente di b varia dunque tra 11 e 9, ma con calcoli simili a queli fatti nella (1), otteniamo che $ c |b^9 $, e dunque è tutto verificato.


Edit: vedo che Agi mi ha preceduto
I miei calcoli sono effettivamente un po' caserecci, forse la sua dimostrazione è più rigorosa