Problema
Si ha una sequenza di interi positivi $ x_1,\dots,x_n $. Si può fare un'unica mossa, cioè prendere al più $ k $ numeri e trasformarli nella loro media aritmetica. Determinare, in funzione di $ n $, il più piccolo $ k $ che rende possibile rendere tutti i numeri uguali in un numero finito di mosse.
Medie, ma non stiamo parlando di Algebra
-
MindFlyer
Proviamo così:
siano $ k_1 \geq k_2... \geq k_m $i divisori primi di n .Se $ k=k_1 $ è possibile ottenere tutti gli $ x_i $ tutti uguali prendendoli a gruppi di k alla volta;a questo punto abbiamo $ \frac{n}{k} $ gruppi di k numeri uguali tra loro;a questo punto,prendendone $ k_i $ alla volta,prima o poi si riesce a fare in modo che siano tutti uguali,poichè da ogni mossa si otterrà sempre un numero minore di gruppi,il cui numero di elementi sarà sempre maggiore.Dunque alla fine tutti saranno uguali(l'ultima parte è spiegata maluccio).
Per dimostrare che k non può essere più piccolo,si consideri ogni singolo $ x_i $ dopo ogni mossa,scritto come frazione;ovviamente si potrà avere il prodotto dei vari $ k_i $ usati come denominatore;poichè k è minore del più grande divisore primo di n,questo non dividerà mai tale denominatore,essendo appunto primo.Tutti gli $ x_i $ finali,però,dovranno essere scritti come frazioni con al denominatore n,e quindi il più grande divisore primo di n dovrà dividerlo:per questo è impossibile ottenere alla fine tutti gli $ a_i $ uguali(anche qui avrei potuto fare di meglio^^)
Al solito dimentico il caso banale n=1,dove non ha senso parlare di divisori primi...
siano $ k_1 \geq k_2... \geq k_m $i divisori primi di n .Se $ k=k_1 $ è possibile ottenere tutti gli $ x_i $ tutti uguali prendendoli a gruppi di k alla volta;a questo punto abbiamo $ \frac{n}{k} $ gruppi di k numeri uguali tra loro;a questo punto,prendendone $ k_i $ alla volta,prima o poi si riesce a fare in modo che siano tutti uguali,poichè da ogni mossa si otterrà sempre un numero minore di gruppi,il cui numero di elementi sarà sempre maggiore.Dunque alla fine tutti saranno uguali(l'ultima parte è spiegata maluccio).
Per dimostrare che k non può essere più piccolo,si consideri ogni singolo $ x_i $ dopo ogni mossa,scritto come frazione;ovviamente si potrà avere il prodotto dei vari $ k_i $ usati come denominatore;poichè k è minore del più grande divisore primo di n,questo non dividerà mai tale denominatore,essendo appunto primo.Tutti gli $ x_i $ finali,però,dovranno essere scritti come frazioni con al denominatore n,e quindi il più grande divisore primo di n dovrà dividerlo:per questo è impossibile ottenere alla fine tutti gli $ a_i $ uguali(anche qui avrei potuto fare di meglio^^)
Al solito dimentico il caso banale n=1,dove non ha senso parlare di divisori primi...
Sunshine or rain, it's all the same, life isn't gray
oh Mary-Lou.
(Mary-Lou --- Sonata Arctica)
oh Mary-Lou.
(Mary-Lou --- Sonata Arctica)
come al solito, chiedo spiegazioni a coloro che sono + bravi di mè 
... non prendetevela troppo se sono de 'coccio, raga! 
E poi stò prob NON mi piace!
per la cond suff ci sono (e c'ero dai primi 3 minuti post-lettura)!
per quella necessaria nn ancora no..
... Forse è Avril Lavigne che stò ascoltando che impedisce una mia comprensione 
...
E' vero che k non dividerà il denominatore, ma questa non mi pare una condizione necessaria per arrivare alla fine:
ES:
1-5-9-8-12
(1+8+12)/3-(1+8+12)/3-(1+8+12)/3-(5+9)/2-(5+9)/2
7-7-7-7-7
il 5 non compare in nessuna divisione, sebbene alla fine tutti i numeri siano uguali a (1+5+9+8+12)/5...
-------------
come vengono considerati i casi sopra?... per quanto ho capito, la condizione necessaria non si può fare come caso generale (nel senso che non tutte le serie abbisognano di quel divisore, basti pensare a quelle degeneri), ma bisogna trovare una particolare sequenza che esprima quel fattore come necessario... ma anche così al momento ho qualche problema (non mi raccapezzo bene con i numeri non naturali)... boh! Vedremo... ora è mejo che studi per la matura (del resto devo approfittare del momento guadagnato per gli stage di fisica persi
)..
... non prendetevela troppo se sono de 'coccio, raga! E poi stò prob NON mi piace!per la cond suff ci sono (e c'ero dai primi 3 minuti post-lettura)!
per quella necessaria nn ancora no..
... Forse è Avril Lavigne che stò ascoltando che impedisce una mia comprensione ...E' vero che k non dividerà il denominatore, ma questa non mi pare una condizione necessaria per arrivare alla fine:
ES:
1-5-9-8-12
(1+8+12)/3-(1+8+12)/3-(1+8+12)/3-(5+9)/2-(5+9)/2
7-7-7-7-7
il 5 non compare in nessuna divisione, sebbene alla fine tutti i numeri siano uguali a (1+5+9+8+12)/5...
-------------
come vengono considerati i casi sopra?... per quanto ho capito, la condizione necessaria non si può fare come caso generale (nel senso che non tutte le serie abbisognano di quel divisore, basti pensare a quelle degeneri), ma bisogna trovare una particolare sequenza che esprima quel fattore come necessario... ma anche così al momento ho qualche problema (non mi raccapezzo bene con i numeri non naturali)... boh! Vedremo... ora è mejo che studi per la matura (del resto devo approfittare del momento guadagnato per gli stage di fisica persi
)..Forse ci sono:alla fine tutti i numeri saranno nella forma $ \frac{S}{n} $,con S somma di tutti gli $ x_i $;dopo ogni passaggio,però,i nuovi $ x_i $ ottenuti si potranno scrivere come frazioni,con al numeratore la somma degli $ x_i $ considerati,e al denominatore un numero primo con k,per le ragioni "spiegate"sopra.Quindi non si arriverà mai a frazioni come quella richiesta.
Ho paura che non cambi molto così...
Ho paura che non cambi molto così...
Sunshine or rain, it's all the same, life isn't gray
oh Mary-Lou.
(Mary-Lou --- Sonata Arctica)
oh Mary-Lou.
(Mary-Lou --- Sonata Arctica)
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Forse CON CALMA ci sono arrivato...
prendo come esempio il caso n=5... non ho ancora generalizzato, ma spero venga uguale...
Ogni numero ottenibile si scrive come combinazione lineare di gruppi dei 5 elementi diviso un denominatore determinato dal prodotto dei k utilizzati. Bastano questa caratteristiche (che NON credo "metabolizzino" tutti i dati) per trovare una stringa che porti all'assurdo? Credo di si! Basta posizionare i 5 elementi di modo che qualsiasi sottoinsieme sia divisibile per 5 ma non lo sia la loro media, ovverosia tutti devono essere un multiplo di 5 ma la loro somma non un multiplo di 25.
5-10-15-20-30
--> la media è 16;
--> un qualsiasi sottoinsieme è divisibile per 5, quindi lo sarà anche la combinazione lineare--> deve esistere un 5 al denominatore...
prendo come esempio il caso n=5... non ho ancora generalizzato, ma spero venga uguale...
Ogni numero ottenibile si scrive come combinazione lineare di gruppi dei 5 elementi diviso un denominatore determinato dal prodotto dei k utilizzati. Bastano questa caratteristiche (che NON credo "metabolizzino" tutti i dati) per trovare una stringa che porti all'assurdo? Credo di si! Basta posizionare i 5 elementi di modo che qualsiasi sottoinsieme sia divisibile per 5 ma non lo sia la loro media, ovverosia tutti devono essere un multiplo di 5 ma la loro somma non un multiplo di 25.
5-10-15-20-30
--> la media è 16;
--> un qualsiasi sottoinsieme è divisibile per 5, quindi lo sarà anche la combinazione lineare--> deve esistere un 5 al denominatore...