Stage Senior 2012

[scambret]

@Anér grazie mille

[Elzaralian]

Colgo l'occasione per fare un paio di domande anch'io. Riguardano l'esercizio C8.
Prima una curiosità:
Per chi ha visto il video (o ha assistito alla lezione), come si chiama realmente il teorema di "Tizio Caio Sempronio"?
Ho dato un' occhiata veloce a Wikipedia, ma non conoscendo il nome vero non è facile trovare un teorema partendo dal suo enunciato!

Adesso la domanda vera:
alla fine si chiede di dimostrare la disuguaglianza:
$ (2d-n)(\alpha + \beta - n) \leq (n-\alpha)(n- d ) $
Nel video viene detto (in modo poco incoraggiante):

Teoricamente si può fare in diversi modi: o vi fate casi, e funziona, oppure fissate uno fra $ \alpha $ e $ \beta $, e vedete che è lineare nell'altro, e quindi vi beccate massimi... minimi... via così: sotituite... voi avete delle stime su $ \alpha $ e $ \beta $, quanto sono al massimo, quanto sono al minimo, andate a vedere quanto viene e verificate le disuguaglianze del caso. Comunque sono un po' di conti che dovrebbero portarvi, alla fine, a dimostrare ...

Io non l'avrei fatta così difficile, considerando che tutte le variabili che compaiono sono numeri naturali, valgono:
$ n-2d \leq n-d \label{1} $
$ n-\alpha - \beta \leq n-\alpha \label{2} $
Ora posso moltiplicare membro a membro, visto che dei $ LHS $ solo uno (ovvero $ (n-\alpha - \beta) $) può essere negativo, ottenendo così:
$ (n-2d)(n-\alpha - \beta) \leq (n-\alpha)(n- d ) $
Che è quello che stavo cercando.

Visto che mi era anche stato detto che la disuguaglianza finale non era poi così intuitiva... non capisco: il mio metodo funziona veramente o c'è una fregatura che non ho visto?
Mi sembra troppo semplice!
Grazie in anticipo

[Astersh]

Visto che ci sono, anche io ho delle incertezze su C8.

Alla fine si giunge a dover dimostrare $ (2d-n)(\alpha + \beta -n) \leq (n- \alpha)(n-d) $ ma il RHS dovrebbe figurare i collegamenti di $ m(A/X,B/Y) $.

$ m(A/X,B/Y) = (n- \alpha)(n-d- \beta +c) $ dove $ c $ sono gli elementi di$ B $ che hanno già qualche amico in $ A $ e che stanno in $ Y $.
Non dovrebbe essere così? Se si poi il minimo , considerando WLOG $ \beta \leq \alpha $, è dato da $ (n-\beta)(n-\alpha -d +e) $ , dove $ e $ sono gli elementi di$ A $ che hanno già qualche amico in $ B $ e che stanno in $ X $.

[Kfp]

Domanda di tipo organizzativo, il Test Iniziale si svolge il giorno stesso dell'arrivo (2 settembre) oppure il giorno successivo?

[Sir Yussen]

Domanda di tipo organizzativo, il Test Iniziale si svolge il giorno stesso dell'arrivo (2 settembre) oppure il giorno successivo?

Il giorno stesso, dopo una lezione introduttiva di circa 2 ore.

[Anér]

Visto che ci sono, anche io ho delle incertezze su C8.

Alla fine si giunge a dover dimostrare $ (2d-n)(\alpha + \beta -n) \leq (n- \alpha)(n-d) $ ma il RHS dovrebbe figurare i collegamenti di $ m(A/X,B/Y) $.

$ m(A/X,B/Y) = (n- \alpha)(n-d- \beta +c) $ dove $ c $ sono gli elementi di$ B $ che hanno già qualche amico in $ A $ e che stanno in $ Y $.
Non dovrebbe essere così? Se si poi il minimo , considerando WLOG $ \beta \leq \alpha $, è dato da $ (n-\beta)(n-\alpha -d +e) $ , dove $ e $ sono gli elementi di$ A $ che hanno già qualche amico in $ B $ e che stanno in $ X $.

Spero di aver capito abbastanza dal pdf. Dati $C\subseteq A,D\subseteq B$, chiamo $m(C,D)$ il numero di archi tra C e D non ancora occupati da un'amicizia (e dunque disponibili per nuove amicizie).
Il problema si riconduce a dimostrare che per ogni coppia $X\subseteq A, Y\subseteq B$ vale la disuguaglianza
$$(n-2d)(n-\alpha -\beta)\leq m(A\setminus X ,B\setminus Y)$$
ove $\alpha =|X|$ e $\beta =|Y|$.
Innanzitutto notiamo che la disuguaglianza è simmetrica nei ragazzi e nelle ragazze: stiamo prendendo un sottoinsieme da una parte e uno dall'altra e stiamo facendo operazioni senza privilegiare una delle due parti. Dunque potremmo distinguere due casi ($\alpha \geq \beta$ e $\beta \geq \alpha$), ma senza perdita di generalità supporremo $\alpha \geq \beta$ (o se preferite faremo il caso $\alpha \geq \beta$ e l'altro si farà in maniera del tutto analoga). Notiamo anche che se $\alpha +\beta >n$ allora la disuguaglianza sussiste (perché?). In generale è bene eliminare più casi possibiili prima di fare stime (aggiungere pezzi intermedi nelle disuguaglianze), semplicemente perché le stime che si fanno funzionano più facilmente se sono rimasti pochi casi da controllare. Dunque supponiamo anche $\alpha+\beta \leq n$, da cui anche $2\beta\leq n$.
Prendiamo un ragazzo $x_i$ contenuto in $A\setminus X$; per l'ipotesi inziale egli ha $a_i$ amiche e perciò $m(\{x_i\},B)=n-a_i$, ovvero ci sono $n-a_i$ ragazze che possono stringere una nuova amicizia con $x_i$. Ora al più $\beta$ di queste sono dentro Y, dunque $m(\{x_i\},B\setminus Y)\geq n-a_i-\beta\geq n-d-\beta$. si noti che quest'ultimo termine non dipende più da $x_i$(contiene soltanto $n$, $\beta$ e $d$), da cui sommando su $x_i \in X$ si ottiene finalmente (giustificare il significato di questo passaggio) $m(A\setminus X, B\setminus Y)\geq (n-\alpha)(n-\beta -d)$. @ Astersh: prima di sommare su $x_i$ in $A\setminus X$ moltiplicando per $n-\alpha$ è opportuno che tutti i termini da sommare siano uguali: nel tuo conto credo che la tua $c$ sia in realtà una $c_i$ associata al ragazzo $x_i$ che conta quante amiche ha il ragazzo in $Y$, da cui gli archi disponibili in $Y$ sono al più $\beta- c_i$; il modo più semplice per avere addendi tutti uguali è trascurare tale $c_i$, dopo aver verificato che sta dalla parte giusta della disuguaglianza.
Nel pdf c'è un'altra stima che non saprei come dimostrare in questo momento, comunque il conto di Elzaralian per dimostrare la disuguaglianza che ne viene fuori mi sembra valido.
Adesso abbiamo la disuguaglianza
$$(n-2d)(n-\alpha-\beta)\leq (n-\alpha)(n-d-\beta)$$
in cui n,d,$\alpha$ e $\beta$ sono numeri naturali con le varie condizioni $n\geq 2d$,$\alpha\geq \beta$,$n\geq \alpha+\beta$; il modo più semplice per dimostrare la disuguaglianza è quello di fissare $\alpha$ e notare che a quel punto i termini sono di primo grado in $\beta$ (oppure si può fissare $\beta$ e studiare il comportamento in $\alpha$). Adesso si porta tutto al primo membro ottenendo una disuguaglianza del tipo $mostro(\beta)\leq 0$, ove mostro è un polinomio di primo grado che dipende anche da $\alpha$, che in questo momento trattiamo come parametro; mostro è convesso perché è di primo grado, le funzioni convesse su un intervallo chiuso hanno massimo in uno degli estremi (perché?), dunque basta sostituire uno dei due valori estremali di $\beta$ (quali valori può assumere $\beta$ una volta fissato $\alpha$?), verificare che in quei casi mostro è minore o uguale a 0 e concludere che lo è sempre (dunque valeva anche la disuguaglianza originale). Questo è ciò che credo suggeriscono di fare anche nel video, secondo la citazione di Elzaralian; fate un po' di verifiche (che poi sono 2) e avete finito.
@Elzaralian: puoi enunciare ipotesi e tesi del teorema citato nel video?

[nassus95]

Nell'esercizio A1 ad un certo punto si trova che x può essere (-1,-2,3) ed in base a quale si sceglie y può essere (-2,3), oppure può essere (-1,3), .... e così via anche con z, ma le terne (x,y,z) che ricavo non sono altro che le permutazioni dei tre valori di x che avevo trovato all'inizio e penso che ciò sia dovuto al fatto che il sistema sia simmetrico.

Non c'è un modo per dimostrarlo o dirlo più velocemente senza fare tutti i casi ?

Questo discorso vale per tutti i sistemi simmetrici oppure ci sono casi in cui non funziona?

[scambret]

Nell'esercizio A1 ad un certo punto si trova che x può essere (-1,-2,3) ed in base a quale si sceglie y può essere (-2,3), oppure può essere (-1,3), .... e così via anche con z, ma le terne (x,y,z) che ricavo non sono altro che le permutazioni dei tre valori di x che avevo trovato all'inizio e penso che ciò sia dovuto al fatto che il sistema sia simmetrico.

Non c'è un modo per dimostrarlo o dirlo più velocemente senza fare tutti i casi ?

Questo discorso vale per tutti i sistemi simmetrici oppure ci sono casi in cui non funziona?

Il sistema di partenza è simmetrico perchè scambiando tra di loro le incognite, le equazioni non cambiano. Essendo simmetrico se tu trovi una n-upla non ordinata che è soluzione del sistema, una qualunque permutazione della n-upla è soluzione.. Cioè se $ (X_1 $, $ X_2 $, $ \cdots $, $ X_n) $ è soluzione di un sistema simmetrico puoi fare qualunque permutazione, e troverai sempre soluzioni che vanno bene!

Dalle mie magre conoscenze, penso che il discorso vale per tutti i sistemi!

[Astersh]

@Anér : grazie mille per la risposta. Anche io faccio casi: 1) $ \alpha +\beta > n $ allora ok, LHS minore di 0 va tutto bene. 2) $ \alpha +\beta = n $ il Lhs si annulla, quindi mi resta da considerare 3) $ \alpha +\beta < n $. Effettivamente quel $ e $ non c'entrava nulla, scusa. Svolgendo i calcoli e semplificando si giunge a

$ \beta(\alpha -2d) +d(n-\alpha) \geq 0 $

ho che $ \alpha + \beta \leq n-1 $ da cui $ \alpha \leq n- \beta-1 $
A questo punto noto che $ \alpha-2d $ non so bene che segno abbia ( se negativo o positivo) , quindi per rendere la disuguaglianza la peggiore possibile allora cerco di farlo rimanere negativo, $ n-\alpha \geq 0 $ in ogni caso. Ora l'idea è di rendere $ n-\alpha $ la più piccola possibile facendo restare $ \alpha + 2d <0 $.
Scelgo $ \alpha=2d -1 $ e minimizzo anche $ n $ ponendo $ n=2d+1 $ ( intanto per rendere $ \alpha-2d $ negativo implica $ \alpha < 2d $) da cui ottengo che $ \beta=1 $ e mi riduco a $ 2d-\beta \geq 0 $ cioè $ 2d \geq 1 $ che è vera.
Più in generale $ \alpha=2d-k $ quindi mantenendo $ n $ minimo a $ 2d+1 $ ottengo $ \beta \leq k $ e per rendere le cose il peggiore possibile pongo $ \beta=k $ e ottengo:

$ -k^2 +d(k+1) \geq 0 $

solo che a questo punto ho a sistema due condizioni: 1) $ k \leq 2d $ e 2) $ k \leq \frac {d+\sqrt {d^2 +4d}}{2} $ che implica $ d^2 +4d \geq 9d^2 $. A questo punto mi blocco perchè non ottengo $ d $ che soddisfano le ipotesi iniziali del problema, cioè $ d \geq 1 $. Sono convinto di sbagliare da qualche parte, ma non riesco a trovare l'errore.

[nassus95]

Nell'esercizio A1 ad un certo punto si trova che x può essere (-1,-2,3) ed in base a quale si sceglie y può essere (-2,3), oppure può essere (-1,3), .... e così via anche con z, ma le terne (x,y,z) che ricavo non sono altro che le permutazioni dei tre valori di x che avevo trovato all'inizio e penso che ciò sia dovuto al fatto che il sistema sia simmetrico.

Non c'è un modo per dimostrarlo o dirlo più velocemente senza fare tutti i casi ?

Questo discorso vale per tutti i sistemi simmetrici oppure ci sono casi in cui non funziona?

Il sistema di partenza è simmetrico perchè scambiando tra di loro le incognite, le equazioni non cambiano. Essendo simmetrico se tu trovi una n-upla non ordinata che è soluzione del sistema, una qualunque permutazione della n-upla è soluzione.. Cioè se $ (X_1 $, $ X_2 $, $ \cdots $, $ X_n) $ è soluzione di un sistema simmetrico puoi fare qualunque permutazione, e troverai sempre soluzioni che vanno bene!

Dalle mie magre conoscenze, penso che il discorso vale per tutti i sistemi!

Quello lo sapevo anch'io (ho posto male la domanda) ma mi chiedevo un'altra cosa che è ovvia ma non so dimostrare.
Se per esempio in un sistema simmetrico trovo che x (quindi anche y e z) può essere (1,2,3) e scelgo di prendere x=1, allora y può essere solo 2 o 3, ma perchè non 1 di nuovo? Mi servirebbero giusto due parole per capire come mai la soluzione non si può ripetersi, anche se è ovvio che non può.

Come posso scrivere questo concetto in una dimostrazione?

[scambret]

Nell'esercizio A1 ad un certo punto si trova che x può essere (-1,-2,3) ed in base a quale si sceglie y può essere (-2,3), oppure può essere (-1,3), .... e così via anche con z, ma le terne (x,y,z) che ricavo non sono altro che le permutazioni dei tre valori di x che avevo trovato all'inizio e penso che ciò sia dovuto al fatto che il sistema sia simmetrico.

Non c'è un modo per dimostrarlo o dirlo più velocemente senza fare tutti i casi ?

Questo discorso vale per tutti i sistemi simmetrici oppure ci sono casi in cui non funziona?

Il sistema di partenza è simmetrico perchè scambiando tra di loro le incognite, le equazioni non cambiano. Essendo simmetrico se tu trovi una n-upla non ordinata che è soluzione del sistema, una qualunque permutazione della n-upla è soluzione.. Cioè se $ (X_1 $, $ X_2 $, $ \cdots $, $ X_n) $ è soluzione di un sistema simmetrico puoi fare qualunque permutazione, e troverai sempre soluzioni che vanno bene!

Dalle mie magre conoscenze, penso che il discorso vale per tutti i sistemi!

Quello lo sapevo anch'io (ho posto male la domanda) ma mi chiedevo un'altra cosa che è ovvia ma non so dimostrare.
Se per esempio in un sistema simmetrico trovo che x (quindi anche y e z) può essere (1,2,3) e scelgo di prendere x=1, allora y può essere solo 2 o 3, ma perchè non 1 di nuovo? Mi servirebbero giusto due parole per capire come mai la soluzione non si può ripetersi, anche se è ovvio che non può.

Come posso scrivere questo concetto in una dimostrazione?

Penso che sia abbastanza scontato.. Dato che le soluzioni sono (1,2,3) se scegli una volta 1, non lo puoi più scegliere, perchè la terna ha solo un 1

[Anér]

@nassus95: se ti basta un controesempio con 2 incognite, considera il sistema
$(x+y)(x+y-2)=0$
$x^6-2x^3y^3+y^6=0$
Questo è simmetrico in x e y e le soluzioni sono (0,0) e (1,1), almeno se ti limiti alle soluzioni reali, e non si possono ottenere le une dalle altre per permutazioni.
Se hai voglia di fare conti (non meno che nella soluzione ufficiale) senza fare tutti i casi, puoi usare i polinomi simmetrici elementari
S=x+y+z
Q=xy+yz+zx
P=xyz
Le tre equazioni si possono scrivere in funzione di questi (visto che sono simmetriche), in particolare la prima ti dice che S=0, nella seconda puoi isolare un P di primo grado e sostituirlo quindi nella terza che diventa un polinomio non so quanto brutto, ma penso di secondo grado, nella variabile Q (P e S le hai sostituite già). Ora trovi le radici in Q di questo polinomio (e queste possono essere zero, una o due) e a quel punto per ogni scelta di Q hai un polinomio $t^3-St^2+Qt-P$ le cui radici, prese in un qualche ordine, sono una soluzione (x,y,z) del sistema, purché siano tutte reali. Potendo avere più valori di Q puoi avere più soluzioni che non si ottengono le une dalle altre per permutazioni.
In generale se hai un sistema in n equazioni simmetriche in n variabili $x_1,\cdots,x_n$, puoi ridurti a un sistema in cui le variabili sono i polinomi simmetrici elementari; una volta trovate le soluzioni di questo (se ci si riesce), le soluzioni dell'originale sono le n-uple che, soddisfando le uguaglianze dei polinomi simmetrici elementari, sono costituite in qualche ordine dalle radici di un polinomio che sai scrivere.

[Anér]

@Anér : grazie mille per la risposta. Anche io faccio casi: 1) $ \alpha +\beta > n $ allora ok, LHS minore di 0 va tutto bene. 2) $ \alpha +\beta = n $ il Lhs si annulla, quindi mi resta da considerare 3) $ \alpha +\beta < n $. Effettivamente quel $ e $ non c'entrava nulla, scusa. Svolgendo i calcoli e semplificando si giunge a

$ \beta(\alpha -2d) +d(n-\alpha) \geq 0 $

ho che $ \alpha + \beta \leq n-1 $ da cui $ \alpha \leq n- \beta-1 $
A questo punto noto che $ \alpha-2d $ non so bene che segno abbia ( se negativo o positivo) , quindi per rendere la disuguaglianza la peggiore possibile allora cerco di farlo rimanere negativo, $ n-\alpha \geq 0 $ in ogni caso. Ora l'idea è di rendere $ n-\alpha $ la più piccola possibile facendo restare $ \alpha + 2d <0 $.
Scelgo $ \alpha=2d -1 $ e minimizzo anche $ n $ ponendo $ n=2d+1 $ ( intanto per rendere $ \alpha-2d $ negativo implica $ \alpha < 2d $) da cui ottengo che $ \beta=1 $ e mi riduco a $ 2d-\beta \geq 0 $ cioè $ 2d \geq 1 $ che è vera.
Più in generale $ \alpha=2d-k $ quindi mantenendo $ n $ minimo a $ 2d+1 $ ottengo $ \beta \leq k $ e per rendere le cose il peggiore possibile pongo $ \beta=k $ e ottengo:

$ -k^2 +d(k+1) \geq 0 $

solo che a questo punto ho a sistema due condizioni: 1) $ k \leq 2d $ e 2) $ k \leq \frac {d+\sqrt {d^2 +4d}}{2} $ che implica $ d^2 +4d \geq 9d^2 $. A questo punto mi blocco perchè non ottengo $ d $ che soddisfano le ipotesi iniziali del problema, cioè $ d \geq 1 $. Sono convinto di sbagliare da qualche parte, ma non riesco a trovare l'errore.

Credo che tu faccia sostituzioni un po' troppo selvagge; scegliere $\alpha$ tra i valori che rendono negativo $\alpha -2d$ non è corretto perché aumentare $\alpha$ rende anche "meno negativo" l'addendo $\beta (\alpha -2d)$. Quando poi vuoi diminuire n con 2d+1, lo fai a tuo rischio e pericolo, nel senso che ciò che stai davvero dicendo è $\beta(\alpha-2d)+d(n-\alpha)\geq \beta(\alpha-2d)+d(2d+1-\alpha)$, ma come vedi questa disuguaglianza non implica affatto $\beta =1$; infatti $\beta$ continua a valere quanto prima, e con questo passaggio stai sperando che la nuova disuguaglianza, più forte, continui a valere.
Prova a fare come dicono nel video, fissa $\alpha, d, n$ e fai variare soltanto $\beta$ tra i valori consentiti, e sfrutta la storia della convessità.

[Astersh]

Alla fine , dato che la dimostrazione in C8 procede per induzione, @Anér , quella delle due condizioni necssarie e sufficienti, e dimostro che man mano mi riduco a insiemi più piccoli, quindi a problemi minori e veri per l'induzione, devo comunque porre un caso base? Se si la faccio fissando $ d $ tipo $ d=1 $ e lasciando $ n $ indeterminato?

[nassus95]

@nassus95: se ti basta un controesempio con 2 incognite, considera il sistema
$(x+y)(x+y-2)=0$
$x^6-2x^3y^3+y^6=0$
Questo è simmetrico in x e y e le soluzioni sono (0,0) e (1,1), almeno se ti limiti alle soluzioni reali, e non si possono ottenere le une dalle altre per permutazioni.
Se hai voglia di fare conti (non meno che nella soluzione ufficiale) senza fare tutti i casi, puoi usare i polinomi simmetrici elementari
S=x+y+z
Q=xy+yz+zx
P=xyz
Le tre equazioni si possono scrivere in funzione di questi (visto che sono simmetriche), in particolare la prima ti dice che S=0, nella seconda puoi isolare un P di primo grado e sostituirlo quindi nella terza che diventa un polinomio non so quanto brutto, ma penso di secondo grado, nella variabile Q (P e S le hai sostituite già). Ora trovi le radici in Q di questo polinomio (e queste possono essere zero, una o due) e a quel punto per ogni scelta di Q hai un polinomio $t^3-St^2+Qt-P$ le cui radici, prese in un qualche ordine, sono una soluzione (x,y,z) del sistema, purché siano tutte reali. Potendo avere più valori di Q puoi avere più soluzioni che non si ottengono le une dalle altre per permutazioni.
In generale se hai un sistema in n equazioni simmetriche in n variabili $x_1,\cdots,x_n$, puoi ridurti a un sistema in cui le variabili sono i polinomi simmetrici elementari; una volta trovate le soluzioni di questo (se ci si riesce), le soluzioni dell'originale sono le n-uple che, soddisfando le uguaglianze dei polinomi simmetrici elementari, sono costituite in qualche ordine dalle radici di un polinomio che sai scrivere.

Ho capito abbastanza bene il tuo discorso ma non posso scrivere tutto quello che mi hai detto. Nella dimostrazione ho scritto:



$
\left\{
\begin{array}{ll}
x^2y+xy^2=-6\\
x^3-7x+x^2y+xy^2=0 \\
\end{array}
\right.
$


$$ \Rightarrow \ x^3-7x-6=0$$

Scomponendo il polinomio $P(x)=x^3-7x-6$ "utilizzando Ruffini" trovo che $P(-1)=0$, allora $P(x)$ $\acute{e}$ divisibile per $(x+1)$, infatti
$$x^3-7x-6=(x+1)(x^2-x-6)=(x+1)(x+2)(x-3)$$
$ \Rightarrow x appartiene a \{-1,-2,3\}$


Ora posso scrivere :

Quindi le soluzioni reali (x,y,z) del sistema sono le permutazioni della terna (-1,-2,3)

->(-1,-2,3);(-1,3,-2);(-2,-1,3);(-2,3,-1);(3,-1,-2);(3,-2,-1); ?????

Serve qualche spiegazione di più? Cosa devo scrivere?