Pizza al taglio

[axpgn]

- Tagliamo una pizza circolare con $n$ tagli rettilinei; in ogni punto di intersezione concorrono solo due tagli e nessuna intersezione si trova sul bordo della pizza.
Dimostrare che il massimo numero di pezzi in cui è possibile dividere la pizza con $n$ tagli è $P(n)=((n),(0))+((n),(1))+((n),(2))$

- Supponiamo che con $n$ tagli si formino il numero massimo di pezzi.
Mostrare che il numero di pezzi che non toccano il bordo sono $((n),(0))-((n),(1))+((n),(2))$

- Se con $n$ tagli, dividiamo una pizza nel numero massimo di pezzi possibili, allora almeno un pezzo è più grande di $n/8$ volte il pezzo di pizza medio.
Dimostrazione?


Cordialmente, Alex

[Quinzio]

Dimostrare che il massimo numero di pezzi in cui è possibile dividere la pizza con $ n $ tagli è $ P(n)=((n),(0))+((n),(1))+((n),(2)) $

Intanto bisogna capire cosa c'e' dietro a questa espressione

$ P(n)=((n),(0))+((n),(1))+((n),(2)) $

che e' bella da vedere ma un po' oscura.

Intanto $((n),(k)) = (n!)/(k!(n-k)!)$ quindi

$ P(n)=1+n+ (n(n-1))/2 $

$ P(n)=1+(n(n-1)+2n)/2 $

$ P(n)=1+(n(n+1))/2 $

$ P(n)=1+\sum_{k=1}^n k $

e la mettiamo da parte un attimo.

Ora prendiamo un piano e una retta, che divide il piano in due parti, poi una seconda retta che non e' parallela alla prima.
Il piano e' diviso in 4 parti.
Poi una terza retta che non e' parallela alle altre 2 e non passa per una intersezione gia' presente.
Poi si prosegue aggiungendo rette che non sono parallele alle altre e che non passano per nessuna intersezione.
Tracciare rette non parallele non e' difficile da fare, mentre invece per fare in modo che non passino per nessuna intersezione si puo' prendere un cerchio che contenga tutte le intersezioni e far passare la retta esternamente al cerchio.
Ogni nuova retta viene divisa dalle altre $n-1$ rette in $n-2$ segmenti e le $2$ semirette esterne.
Ogni segmento e le $2$ semirette dividono l'area che le contiene in $2$ parti.
Quindi la $n$esima retta crea $n$ nuove aree.

Allora la formula $P(n)$ e' dimostrata per induzione. $P(1) = 2$ e $P(n) - P(n-1) = n$.
Se poi si traccia un cerchio che contiene tutte le intersezioni abbiamo la nostra pizza divisa in $P(n)$ pezzi.

Mostrare che il numero di pezzi che non toccano il bordo sono $ ((n),(0))-((n),(1))+((n),(2)) $

Allora il numero di pezzi che tocca il bordo e'

$P(n) - [((n),(0))-((n),(1))+((n),(2))] = 2n$

Infatti il numero di intersezioni sulla circonferenza e' $2n$, il doppio del numero di rette.
E la circonferenza e' divisa in $2n$ archi.
Ogni arco delimita un pezzo di pizza che tocca il bordo.

[axpgn]

Ho qualche perplessità ...

Una è questa $(n(n+1))/2=sum_(k=1)^n k!=sum_(k=1)^(n+1) k$

L'altra è che, secondo me, hai dimostrato come calcolare il numero di pezzi tramite ricorrenza ma non con una formula chiusa, non quella formula chiusa, non vedo un legame chiaro e preciso tra le due.
Prima espliciti la formula proposta con un'altra; corretto ma non è una formula di ricorrenza.
Poi trovi una formula di ricorrenza; corretta ma dov'è il legame con l'altra?
Io non lo vedo ...

Il secondo punto è ok.

Cordialmente, Alex

[Quinzio]

Alex, l'idea era questa: nella prima parte ho cercato di dimostrare che l'$n$esima retta crea $n$ nuove aree.
A questo punto ho verificato che $P(n) - P(n-1)$ dia come risultato proprio $n$.
Ed infatti
$P(n) - P(n-1) = 1+\sum_{k=1}^n k - (1+\sum_{k=1}^{n-1} k) = n$
E siccome $P(0) = 1$, $P(1) = 2$, $P(2) = 4$ sono verificabili direttamente per ispezione, allora la validita' di $P(n)$ e' stata dimostrata.
L'obbiettivo non era quello di di fornire una formula chiusa, che e' quella che hai gia' scritto tu ($P(n)$), ma quanto quello di dimostrarla.
Mi parli di ricorrenza, ma questo e' il modo standard che ho sempre visto di usare l'induzione per dimostrare un asserto.

PS. Ho corretto l'errore.
PPS. Manca poi l'ultima domanda

[axpgn]

Hai dimostrato che la formula del post iniziale è equivalente all'altra, la quale conta correttamente i pezzi di pizza generati da $n$ tagli.
Giustissimo.
Quello che intendevo chiedere è: perché è possibile rappresentare il numero di pezzi risultanti dai tagli proprio in quel modo (coefficienti binomiali)? Che algebricamente siano equivalenti è chiaro ma hanno anche un senso "fisico/geometrico"?

[dan952]

1)

Procediamo per induzione:

1) i casi $n=1$ e $n=2$ sono verificati.

2) supponiamo valga per i primi $n$ tagli e verifichiamo che vale anche per $n+1$ tagli. Per massimizzare il numero di pezzi in cui viene tagliata la pizza l' n+1-esimo taglio deve intersecare gli $n$ tagli precedenti così facendo egli viene diviso in $n+1$ parti ognuna delle quali crea un nuovo pezzo. Quindi vengono aggiunti $n+1$ pezzi.

$P(n+1)=P(n)+2n+2=1+n+\frac{n(n-1)}{2}+n+1=1+(n+1)+\frac{(n+1)n}{2}$

[axpgn]

Ok, bene ma ...

Questo dubbio rimane ...

"axpgn":Quello che intendevo chiedere è: perché è possibile rappresentare il numero di pezzi risultanti dai tagli proprio in quel modo (coefficienti binomiali)? Che algebricamente siano equivalenti è chiaro ma hanno anche un senso "fisico/geometrico"?

... oltre al terzo punto

È carino poi il fatto che nessuno ha scritto la formula chiusa più "banale"

$P(n)=(n^2+n+2)/2$

Cordialmente, Alex

[dan952]

Il terzo punto intendi che esiste P tale che

$P/M=n/8$

oppure

$P \geq \frac{n}{8} M$
?

Dove P è la misura di un pezzo e M è la misura media del pezzo di pizza


Comunque

Il problema è strettamente legato alla successione dei numeri triangolari, infatti se disponiamo dei punti in modo da formare un triangolo isoscele e li separiamo otteniamo la divisione in $P(n)-1$ parti .

[axpgn]

La seconda che hai detto

[dan952]

Qualche idea sul terzo punto:

L' idea è quella di procedere per induzione osservando che se il pezzo con $n$ tagli (massimizzati) $P_n$ è tale che $P_n \geq \frac{n}{8}M_n$, dove $M_n$ è la misura media con $n$ tagli (massimizzati), allora un altro taglio può o lasciarlo inalterato o dividerlo in due parti che possono essere diverse, una delle quali necessariemente maggiore di $P_n/2$, oppure uguali di misura $P_n/2$, quindi partendo da $P_n \geq \frac{n}{8}M_n$
potremmo dimostrare che
$P_n/2 \geq \frac{n+1}{8}M_{n+1}$

[axpgn]

... mmm ... la vedo difficile ...

Tanto per comicniare, il passo base quale sarebbe?

L'area del pezzo medio (supposto che $n$ tagli massimizzino il numero di pezzi) è $M_n=(piR^2)/((n^2+n+2)/2)$ dove si può supporre che sia $R=1$ e quindi $M_n=(2pi)/(n^2+n+2)$

Cordialmente, Alex

[dan952]

Sia $A$ l'area della pizza allora il caso base $n=1$ si verifica osservando che $M_1=A/2$ quindi o il taglio divide a metà la pizza quindi $P_1=M_1$ o in due pezzi di misura diversa una delle quali necessariemente più grande della metà $P_1 \geq M_1>\frac{1}{8}M_1$.

Osserviamo che $P(n)M_n=P(n+1)M_{n+1}=A$ quindi $M_{n+1}=\frac{P(n)}{P(n+1)}M_{n}$, dunque se aggiungiamo un taglio e il pezzo $P_n$ rimane inalterato allora si conserva la disuguaglianza, infatti poiché

$\frac{n+1}{8}\frac{P(n)}{P(n+1)} \frac{8}{n} <1$

segue

$\frac{n+1}{8}M_{n+1}=\frac{n+1}{8}\frac{P(n)}{P(n+1)}M_n \leq =\frac{n+1}{8}\frac{P(n)}{P(n+1)} \frac{8}{n} P_n
Il problema rimane quando $P_n$ viene tagliato...

Comunque la strada mi pare di aver capito non è quella più immediata o giusta... Allora necessito di un hint (sono passati i bei tempi in cui non avevo bisogno...)

[axpgn]

In effetti, mentre i primi due punti erano appropriati per la sezione, il terzo è un "bonus" che va oltre

Per risolverlo "facilmente", l'autore usa un teorema poco noto, il "Teorema di Ismailescu".

Ecco, adesso ti ho detto tutto



Cordialmente, Alex

[dan952]

Non trovo nulla riguardo a questo teorema...

[axpgn]

Beh, è poco noto


Dice ...

Ismailescu's Theorem

If $n$ cuts ($n>=1$) of a unit circular pizza form $(n^2+n+2)/2$ pieces, then the area of the biggest piece is greater than $pi/(4n)$.

Cordialmente, Alex

[Mathita]

[ot]Ho tentato diversi approcci per attaccare il 3° punto del problema, ma nessuno di questi ha prodotto il risultato sperato. Il teorema che hai suggerito è abbastanza potente da "banalizzare" il quesito (una maggiorazione ad hoc e via) ... Ora però sarei curioso di leggere una dimostrazione di questo teorema. Siccome non ho trovato nulla in giro, non è che per caso hai un riferimento da proporre? Grazie.

Ps: lascio il tempo a Dan95 e a Quinzio di leggere il suggerimento e di formulare una loro soluzione.[/ot]

[axpgn]

@Mathita

[ot]Sì, è un teorema "potente" e la dimostrazione tutt'altro che banale (non alla mia portata ).

Ho fatto fatica a trovarlo e non saprei come mandartelo ma il riferimento è questo:

Ismailescu, D., Slicing the pie, Discrete and Computational Geometry 30 (2003), 263-276.

Ah, la D. sta per DAN [/ot]


Cordialmente, Alex

[Mathita]

Trovato! Grazie mille, axpgn!

[axpgn]

Di nulla.

Però adesso ci dici cosa ne pensi, facci una recensione

[Mathita]

@axpgn

[ot]Ho letto l'articolo ed è interessante! Purtroppo non sono entrato in dettaglio perché il relatore si avvale di teoremi pregressi che non conosco. Sembra usare il concetto di indice di avvolgimento (che ho incontrato in analisi complessa, una volta sola, secoli fa) e lo sfrutta per esprimere una generalizzazione della formula di Gauss per il calcolo delle aree di poligoni a partire dalle coordinate dei loro vertici (andando a memoria è legato all'interpretazione geometrica di prodotto vettoriale). L'approccio di Ismailescu è davvero bello, anche se un po' calcolotico: ci sono punti in cui mi perdo, perché dovrei analizzarli con più attenzione ... e perché sono ignorante come una capra. [/ot]

[axpgn]

@Mathita
[ot]

"Mathita": Sembra usare il concetto di indice di avvolgimento

Sarebbe il "winding number"?

"Mathita":... anche se un po' calcolotico:

La parte trigonometrica è infinita, è impossibile non perdercisi

Bella recensione!

Thanks[/ot]

Cordialmente, Alex