Pagina 1 di 1

l'uso del WLOG

MessaggioInviato: 28/02/2018, 14:56
da marcomila99
Qualcuno mi saprebbe spiegare quando/come posso dire WLOG $a\ge b\ge c$ o cose simili? per esempio perché qui $\sum_{cyc}^{ }a\left(a-b\right)\left(a-c\right)$ è corretto dire WLOG $a=\max\left(a,b,c\right)$ mentre è sbagliato dire WLOG $a\ge b\ge c$ ?? grazie $10^3$ in anticipo!

Re: l'uso del WLOG

MessaggioInviato: 01/03/2018, 0:17
da Lasker
La prima la puoi dire se il problema che stai facendo è simmetrico in $(a,b,c)$ (quindi se permuti le variabili in un modo qualsiasi il problema rimane lo stesso), mentre la seconda se è "ciclico"in $(a,b,c)$ (quindi se applichi una permutazione ciclica delle tre variabili il problema rimane lo stesso).
Mi sbaglierò, ma la somma che dici tu non è solo ciclica, ma anche simmetrica (anche se è meno evidente) e quindi puoi a tutti gli effetti porre $a\geq b\geq c$.

Ti spiego con l'esempio che stai facendo tu (Schur), sperando di riuscire ad essere più chiaro (lo stesso principio vale anche per altri problemi, non solo le sommatorie/disuguaglianze ma immagino si capisca di più con un esempio terra-terra).
Vogliamo mostrare che $\sum_{cyc}a(a-b)(a-c)\geq 0$ notiamo che è simmetrica perché una permutazione $(1 2 3)$ sulle variabili (mandare $a$ in $b$, $b$ in $c$, $c$ in $a$, il "ciclica" della somma fa sì che i tre addendi siano gli stessi solo ciclati dopo questa permutazione) non cambia la somma e lo stesso per $(2 3)$ (scambiare $b$ e $c$, i tre addendi rimangono fissati), ma $(1 2 3)$ e $(2 3)$ generano il gruppo $S_3$ delle permutazioni di $3$ elementi e quindi ogni permutazione delle tre variabili lascia fisso il valore della sommatoria fissati dei valori per $a$, $b$ e $c$; altro modo più contoso (ma più immediato probabilmente) è espandere tutto e verificare ad occhio che l'espressione risultante non cambia permutando le variabili. Ora Se dimostri Schur per $a\geq b \geq c$ in realtà hai fatto tutti i casi, perché?
Immagina di avere un altro dei $6$ possibili ordinamenti, ad esempio $c\geq a \geq b$, per cui Schur non è vera, ovvero esistono dei valori $a_0,b_0,c_0$ fissati per cui $\sum_{cyc}a_0(a_0-b_0)(a_0-c_0)\leq 0$, in quel caso cosa succede? Consideri $\sum_{cyc}c_0(c_0-a_0)(c_0-b_0)$ (che se espandi bovinamente è del tutto identico a $\sum_{cyc}a_0(a_0-b_0)(a_0-c_0)$), e applichi il caso dimostrato facendo finta che $c_0$ si chiami $a$, $a_0$ si chiami $b$, $b_0$ si chiami $c$ , ottenendo che è $\geq 0$ quindi il caso in cui Schur è falsa è assurdo.

Torna più o meno? Nessuno ha voglia di fare un discorso simile in una gara e quindi si liquida tutto con un "per simmetria assumo WLOG $a\geq b \geq c$", ma questo dovrebbe essere quello che si sottintende (spero almeno :mrgreen: ).