Sia [tex]S[/tex] un insieme di punti nel piano, a [tex]3[/tex] a [tex]3[/tex] non allineati. Dato un poligono convesso [tex]P[/tex] i cui vertici sono in [tex]S,[/tex] sia [tex]a(P)[/tex] il numero di vertici di [tex]P[/tex] e [tex]b(P)[/tex] il numero di punti di [tex]S[/tex] all'esterno di [tex]P.[/tex] Dimostrare che per ogni [tex]x \in R[/tex] vale [tex]\sum_{P} x^{a(P)}(1 - x)^{b(p)} = 1[/tex] dove la somma è operata su tutti i poligoni convessi con i vertici in [tex]S[/tex] (l'insieme vuoto, un punto e un segmento sono considerati poligoni convessi di rispettivamente [tex]0, 1, 2[/tex] vertici).
Ma se $|S|=3, a(P)=3, b(P)=0, x=1$ come lo definisci $0^0$?
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Definiamo $f\left(P\right)=x^{a\left(P\right)}\left(x-1\right)^{b\left(P\right)}$.
Consideriamo una generica configurazione con $n$ punti a tre a tre non allineati. sia $G\subseteq S$ tale che gli elementi di $G$ siano vertici di un poligono convesso $\mathfrak{P}$ tale che $S\subset\mathfrak{P}$ (chiameremo i vertici di $\mathfrak{P}$ $A_1,A_2,...,A_k$ in senso orario a partire da un vertice a scelta). Se vogliamo proprio essere precisi ecco un modo per trovare $G$ con queste proprietà (l'unicità non la dimostro perché è ovvia e non è nemmeno utile agli scopi della dimostrazione). Prendiamo cerchio $\alpha$ con relativa circonferenza $\Omega$ tale che $S\subset\alpha$ e $S\cap\Omega\ne\emptyset$. Sia quindi $A_1$ un punto in $S\cap\Omega$, e $r$ la retta per $P$ tangente a $\Omega$. Cominciamo ora a ruotare in senso orario con fulcro $A_1$ la retta $r$. Il primo punto in $S$ che incontra lo chiameremo $A_2$. In generale il punto $A_{t+1}$ sarà il primo punto in $S$ che la retta $A_{t-1}A_{t}$ incontra ruotando in senso orario con centro $A_t$. Darei per scontato che a un certo punto incontreremo nuovamente il punto $A_1$, quindi il nostro poligono $\mathfrak{P}$ sarà definito (eventualmente se $n=2$ il nostro poligono sarà un segmento, ma vabbe'). Chiaramente $f\left(\mathfrak{P}\right)=x^k$
Adesso per ogni $0\le i\le k$ definiamo $P_i=\left\{\mathfrak{A},\ A_j\in\mathfrak{A} \ \forall\ 1\le j\le i\right\}$. Chiaramente $P_0\equiv S$.
Dimostriamo ora per induzione su $n-m$ che per ogni $0\le m\le k$ vale che$$\sum_{\mathfrak{A}\in P_m}f\left(\mathfrak{A}\right)=x^m$$Fatto questo avremmo la tesi.
Passo base ok. Ora, supponiamo quello che vogliamo dimostrare vero per $n-1$ punti e dimostriamolo per $n$ punti.
Dato un generico $0\le m\le k$ dimostriamo che $\sum_{\mathfrak{A}\in P_m}f\left(\mathfrak{A}\right)=x^m$ per induzione con $m$ decrescente. Il passo base $m=k$ è vero. Supponiamo adesso quello che vogliamo dimostrare vero per $m+1$ e dimostriamolo per $m$.
Abbiamo che $$\sum_{\mathfrak{A}\in P_m}f\left(\mathfrak{A}\right)=\sum_{\mathfrak{A}\in P_m\setminus P_{m+1}}f\left(\mathfrak{A}\right)+\sum_{\mathfrak{A}\in P_{m+1}}f\left(\mathfrak{A}\right)\stackrel{hp. ind. 2)}{=}\sum_{\mathfrak{A}\in P_m\setminus P_{m+1}}f\left(\mathfrak{A}\right)+x^{m+1}$$Quindi dobbiamo far vedere che $$\sum_{\mathfrak{A}\in P_m\setminus P_{m+1}}f\left(\mathfrak{A}\right)=x^{m}-x^{m+1}$$ Ora si ha che se eliminassimo il punto $A_{m+1}$ e definissimo i primi $m$ vertici del nuovo poligono $\overline{\mathfrak{P}}$ (l'overline indica che è quello nuovo) coincidenti con $A_1,...,A_m$ allora l'insieme $\overline{P_m}$ coinciderebbe con $P_m\setminus P_{m+1}$. Adesso sappiamo per l'ipotesi induttiva $1)$ che in $\overline{S}$ si ha che $$\sum_{\mathfrak{A}\in \overline{P_m}}f\left(\mathfrak{A}\right)=x^m$$ Quindi poiché il vecchio $A_{m+1}$ è esterno a tutti i poligoni in $\overline{P_m}$ si ha che $$\sum_{\mathfrak{A}\in P_m\setminus P_{m+1}}f\left(\mathfrak{A}\right)=\left(1-x\right)\sum_{\mathfrak{A}\in \overline{P_m}}f\left(\mathfrak{A}\right)=\left(1-x\right)x^m=x^{m}-x^{m+1}$$ che è quello che volevamo.
Comunque bel problema, la fonte?
mentre il mondo persiste nei suoi sanguinosi conflitti, la vera guerra è combattuta dai matematici
Definiamo $f\left(P\right)=x^{a\left(P\right)}\left(x-1\right)^{b\left(P\right)}$.
Consideriamo una generica configurazione con $n$ punti a tre a tre non allineati. sia $G\subseteq S$ tale che gli elementi di $G$ siano vertici di un poligono convesso $\mathfrak{P}$ tale che $G\subset\mathfrak{P}$ (chiameremo i vertici di $\mathfrak{P}$ $A_1,A_2,...,A_k$ in senso orario a partire da un vertice a scelta). Se vogliamo proprio essere precisi ecco un modo per trovare $G$ con queste proprietà (l'unicità non la dimostro perché è ovvia e non è nemmeno utile agli scopi della dimostrazione). Prendiamo cerchio $\alpha$ con relativa circonferenza $\Omega$ tale che $S\subset\alpha$ e $S\cap\Omega\ne\emptyset$. Sia quindi $A_1$ un punto in $S\cap\Omega$, e $r$ la retta per $P$ tangente a $\Omega$. Cominciamo ora a ruotare in senso orario con fulcro $A_1$ la retta $r$. Il primo punto in $S$ che incontra lo chiameremo $A_2$. In generale il punto $A_{t+1}$ sarà il primo punto in $S$ che la retta $A_{t-1}A_{t}$ incontra ruotando in senso orario. Darei per scontato che a un certo punto incontreremo nuovamente il punto $A_1$, quindi il nostro poligono $\mathfrak{P}$ sarà definito (eventualmente se $n=2$ il nostro poligono sarà un segmento, ma vabbe'). Chiaramente $f\left(\mathfrak{P}\right)=x^k$
Adesso per ogni $0\le i\le k$ definiamo $P_i=\left\{\mathfrak{A},\ A_j\in\mathfrak{A} \ \forall\ 1\le j\le i\right\}$. Chiaramente $P_0\equiv S$.
Dimostriamo ora per induzione su $n-m$ che per ogni $0\le m\le k$ vale che$$\sum{\mathfrak{A}\in P_m}f\left(\mathfrak{A}\right)=x^m$$Fatto questo avremmo la tesi.
Passo base ok. Ora, supponiamo quello che vogliamo dimostrare vero per $n-1$ punti e dimostriamolo per $n$ punti.
Dato un generico $0\le m\le k$ dimostriamo che $\sum_{\mathfrak{A}\in P_m}f\left(\mathfrak{A}\right)=x^m$ per induzione con $m$ decrescente. Il passo base $m=k$ è vero. Supponiamo adesso quello che vogliamo dimostrare vero per $m+1$ e dimostriamolo per $m$.
Abbiamo che $$\sum_{\mathfrak{A}\in P_m}f\left(\mathfrak{A}\right)=\sum_{\mathfrak{A}\in P_m\setminus P_{m+1}}f\left(\mathfrak{A}\right)+\sum_{\mathfrak{A}\in P_{m+1}}f\left(\mathfrak{A}\right)\stackrel{hp. ind. 2)}{=}\sum_{\mathfrak{A}\in P_m\setminus P_{m+1}}f\left(\mathfrak{A}\right)+x^{m+1}$$Quindi dobbiamo far vedere che $$\sum_{\mathfrak{A}\in P_m\setminus P_{m+1}}f\left(\mathfrak{A}\right)=x^{m}-x^{m+1}$$ Ora si ha che se eliminassimo il punto $A_{m+1}$ e definissimo i primi $m$ vertici del nuovo poligono $\overline{\mathfrak{P}}$ (l'overline indica che è quello nuovo) coincidenti con $A_1,...,A_m$ allora l'insieme $\overline{P_m}$ coinciderebbe con $P_m\setminus P_{m+1}$. Adesso sappiamo per l'ipotesi induttiva $1)$ che in $\overline{S}$ si ha che $$\sum_{\mathfrak{A}\in \overline{P_m}}f\left(\mathfrak{A}\right)=x^m$$ Quindi poiché il vecchio $A_{m+1}$ è esterno a tutti i poligoni in $\overline{P_m}$ si ha che $$\sum_{\mathfrak{A}\in P_m\setminus P_{m+1}}f\left(\mathfrak{A}\right)=\left(1-x\right)\sum_{\mathfrak{A}\in \overline{P_m}}f\left(\mathfrak{A}\right)=\left(1-x\right)x^m=x^{m}-x^{m+1}$$ che è quello che volevamo.
Comunque bel problema, la fonte?
Testo nascosto:
Ok, se ho capito bene leggendo in velocità è come la mia, ovvero consideri la convex hull di un insieme di punti e mostri che la somma delle [tex]f(P)[/tex] sui poligoni con esattamente [tex]m[/tex] vertici sulla hull è [tex]x^m[/tex] (tutto ciò dovrebbe essere la tua [tex]\sum{\mathfrak{A}\in P_m}f\left(\mathfrak{A}\right)=x^m[/tex]), e poi vabbè la tesi segue facile, giusto?
Probabilmente viene anche così come dici tu, ma io ho definito $P_m$ come l'insieme di tutti poligoni che hanno come vertici i primi $m$ vertici del poligono $\mathfrak{P}$ (ma magari contengono anche altri vertici di $\mathfrak{P}$, quindi i $P_i$ non sono disgiunti come avevi capito tu)
Comunque scusami per i tantissimi typo che piano piano stavo cercando di levare... XD
mentre il mondo persiste nei suoi sanguinosi conflitti, la vera guerra è combattuta dai matematici
Ok ora ho letto per bene, funziona perfettamente anche così
Testo nascosto:
alla fine l'idea è la stessa per la cosa che hai fatto tu e quella che dicevo, cioè per l'induzone ti serve che una cosa sia [tex]x^m - x^{m+1}[/tex] e questo segue sempre per l'induzione dal togliere un punto che stando sulla hull ti dà quel fattore $(1 - x)$ che moltiplica
Veritasium ha scritto:la somma delle [tex]f(P)[/tex] sui poligoni con esattamente [tex]m[/tex] vertici sulla hull è [tex]x^m[/tex]
Ma sei sicuro che questa cosa sia giusta? Ad esempio se $S$ ha tre punti e poni $m=1$ dovresti avere che $3x\left(1-x\right)^2\ne x$
No (intendevo con i vertici fissati, cioé non la somma delle somme, ma sarebbe lo stesso sbagliata) infatti ricontrollando quanto ho scritto è
Testo nascosto:
Siano [tex]Q_1, ... Q_k[/tex] punti sulla hull di [tex]S,[/tex] allora [tex]\sum_{P:Q_1, ..., Q_k \in P} x^{a(P)}(1 - x)^{b(P)} = x^k[/tex]
che dovrebbe essere come la tua. Per qualche motivo a un giorno di distanza c'ho mentalmente aggiunto che quelli fossero gli unici punti della hull, boh
, e sì, è praticamente uguale alla mia!