Potete minimizzare la media aritmetica?
Permettere $n$essere un numero intero positivo. Ci sono$2n$ $1$s scritto sulla lavagna. John ripete la seguente procedura$3n$ volte, come segue:
Scegli due numeri $x,y$ sulla lavagna, quindi sostituisci ciascuno di essi con $2x+y, 2y+x$ rispettivamente.
Il suo obiettivo è ridurre il più possibile la media aritmetica dei numeri. Qual è la sua migliore strategia e qual è la migliore media aritmetica?
Problema nel lavoro di classe dell'addestramento alle Olimpiadi della matematica, con alcune modifiche.
Suggerimento:
Usa una disuguaglianza comunemente usata nei problemi IMO.
Risposte
Nota che questo non è così ovvio come potrebbe sembrare a prima vista. Ad esempio, il presupposto pigro
più piccolo è, meglio è
non è corretto. Esempio$n=2$. Già dopo il primo passaggio che porta a$1,1,3,3$ il passo successivo ottimale è
$1,1$ o $3,3$
ma no
$1,3$ anche se è più piccolo di $3,3$.
Prima di entrare negli aspetti tecnici della dimostrazione effettiva, lasciatemi prima affermare qual è il trucco :
Il trucco sta nel monitoraggio: non pensare $x\mapsto 2x+y$, pensa $x\mapsto x+2y$!
Prova formale (grazie @bobble per aver corretto la mia formattazione orrbile):
Notazione: sarà conveniente mantenere lo stesso insieme di etichette $\alpha,\beta,\gamma,...$ sui numeri in evoluzione, quindi molto formale abbiamo uno stato $X(k) = X_\alpha(k),X_\beta(k),...$ dove $k$è il conteggio dei passi. Lo abbreveremo drasticamente scrivendo$a = X_\alpha(k),b = X_\beta(k)$ ecc. Poiché le etichette non hanno alcuna influenza sulla media, abbiamo una scelta in ogni fase, vale a dire. $S^\times_{\alpha\beta}:a,b \mapsto a+2b,b+2a$ vs. $S^=_{\alpha\beta}:a,b \mapsto 2a+b,2b+a$. (Resteremo fedeli alla prima opzione e non utilizzeremo affatto la seconda). Ovviamente, i numeri non referenziati rimangono invariati. Dovremo anche essere in grado di scambiare senza elaborare effettivamente:$\times_{\alpha\beta}: a,b \mapsto b,a$. Poiché si tratta di pura contabilità, è chiaro che questo tipo di passaggio non conta$k$.
Affermiamo che l'avido strat, "prendi sempre i due numeri più piccoli" è ottimale. Questo è ovvio nell'ultimo passaggio. Supponiamo che avido si sia dimostrato ottimale per l'ultimo$k$ passi indipendentemente dallo stato ma esiste uno stato $X(3n-(k+1))$in cui prendere i due più piccoli non è ottimale. Lascia che sia il passo ottimale$S^\times_{\alpha\beta}$. Presumendo che il passo successivo ottimale possa essere scelto come quello goloso$S^\times_{\gamma\delta}$. Tre casi:
1)$\alpha=\gamma,\beta=\delta$: Non può essere perché pensavamo che il primo passo fosse non avidi.
2)$\alpha\ne\gamma,\beta\ne\gamma,\alpha\ne\delta,\beta\ne\delta$ Non può essere perché ovviamente
$S^\times_{\alpha\beta} \circ S^\times_{\gamma\delta}=S^\times_{\gamma\delta} \circ S^\times_{\alpha\beta}$e abbiamo ipotizzato che avido non fosse ottimale nel primo passaggio.
Prima di risolvere l'ultimo caso, introduciamo l'ordine parziale$X(k)<X'(k)$ dove $<$ si intende $X_\psi(k)\le X'_\psi(k)$ per tutti $\psi \in \{\alpha,\beta,...\}$e almeno una delle disuguaglianze è rigorosa. Ovviamente, se$X(k)<X'(k)$ ed entrambi sono quindi sottoposti allo stesso passaggio $X(k+1)<X'(k+1)$.
3)$\alpha\ne\gamma,\beta=\delta$ Quindi per ipotesi $c<a$. Elaborazione diretta$X(3n-(k-1))$ rendimenti
$S^\times_{\beta\gamma} \circ S^\times_{\alpha\beta}: a,b,c \mapsto a+2b,b+2a+2c,4a+2b+c$
se usiamo i due passaggi originali che si presumeva fossero ottimali.
Se li scambiamo e poi cambiamo anche le etichette$\alpha$ e $\gamma$ noi abbiamo
$\times_{\alpha\gamma}\circ S^\times_{\alpha\beta} \circ S^\times_{\beta\gamma}: a,b,c \mapsto c+2b,b+2a+2c,4c+2b+a$
Poiché questo stato è per componenti migliore o uguale a quello ottenuto dalla procedura presumibilmente ottimale, questa è una contraddizione. $\square$
Quasi dimenticavo: il minimo è, ovviamente,
27
Disclaimer: questa è una risposta sfacciata.
Poiché la funzione è strettamente crescente per tutti gli interi positivi, la risposta semplice è fornire alla funzione i numeri più piccoli in ogni fase. Questo risulta in$n$ applicazioni che prendono da (1,1) a (3,3), un altro $n$ operazioni che prendono da (3,3) a (9,9) e l'ultima $n$ operazioni portando da (9,9) a (27,27), con una media di 27.
Tuttavia, la risposta sconcertante è che dovremmo scegliere la definizione di media con maggiore attenzione. Invece di scegliere la media , dovremmo scegliere la modalità (la mediana funziona altrettanto bene in questo caso). Quindi, a parte per$n=2$ (per il quale useremmo l'algoritmo "semplice" sopra), applica la funzione $3n$volte alla stessa coppia di numeri. Questi numeri crescono$3^{3n}$, ma tutto il resto rimane 1.
La media per $n=1$ e $n=2$ ha ancora 27 anni, ma per $n>2$, la media (mediana o modalità) ora è solo 1.
Possiamo spazzare le 2 anomalie sotto il tappeto? Ebbene, sì, se spingiamo ulteriormente l'angolo di Puzzling . Ecco la dichiarazione del problema:
Il suo obiettivo è ridurre il più possibile la media dei numeri. Qual è la sua migliore strategia e qual è la migliore media?
Non è indicato a quali "numeri" si riferiscono, quindi scegliamo la sequenza di mediane (media?) Come numeri: 27, 27, 1, 1, 1, .... La mediana o il modo di questa sequenza infinita è, ovviamente, 1.
Quindi la media migliore è 1, usando la strategia sfacciata (o 27, usando la strategia semplice).
Ogni passo aumenta la somma di 2 * (x + y). È ovvio che l'aumento minimo della somma in un particolare passaggio è se prendi i due numeri più bassi disponibili. Ma questo non è abbastanza per dimostrare che l'algo avido è il migliore.
Prendi y = x + de riscrivi i numeri dopo la trasformazione in 3x + d, 3x + 2d. Ora introduci un altro numero w, w = x + e; e <d (ed e> = 0). Un'altra operazione successiva, ti ritroverai con 3x + 2d, 5x + 2e + d, 7x + e + 2d. Confronta questi numeri con 3x + 2e, 5x + e + 2d, 7x + 2e + d - prima mescolando x e w, quindi aggiungendo y al mix. Le differenze sono 2 * (de); - (de); (de); e la somma chiaramente favorisce l'algoritmo avido. Anche se si presume che d sia enorme, quindi il 2 ° termine sarebbe effettivamente il più piccolo in caso di non avido, le differenze sono ancora 2x + d, - (2x + e), de - quindi mentre il 2 ° termine è di nuovo più piccolo in non avido caso, la somma dei 2 termini più piccoli ancora una volta favorisce l'algoritmo avido.
Non riesco a trovare un'operazione che abbia TUTTI i numeri più piccoli dall'algoritmo avido rispetto a quello non avido in ogni caso, ma quanto sopra mostra che la somma dei 2 più piccoli già favorisce l'algoritmo avido e lo considero abbastanza buono.