l'uso del WLOG
-
- Messaggi: 17
- Iscritto il: 24/11/2016, 14:30
l'uso del WLOG
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
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
).
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
![Mr. Green :mrgreen:](./images/smilies/icon_mrgreen.gif)
Cur enim scribere tre numeri quando se ne abbisogna di due? Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani.
PRIMA FILA TUTTI SBIRRI!
#FREELEPORI
PRIMA FILA TUTTI SBIRRI!
#FREELEPORI