Usuari:Enricbraso/Seqüència del tallador mandrós

Pastís tallat en set trossos amb tres talls rectes.

La seqüència del tallador mandrós, (de l'anglès lazy caterer's sequence) descriu el nombre màxim de trossos que es poden obtenir d'un pastís rodó amb talls verticals rectes. Per exemple, amb dos talls podem obtenir 4 trossos si vigilem que els dos talls es creuin.

Formalment és el nombre màxim de regions en que es pot dividir un cercle amb línies rectes. També és el nombre màxim de regions en que es pot dividir el pla amb línies rectes.

L'equivalent amb tres dimensions considerant un pastís cilíndric i els talls realitzats en qualsevol direcció s'anomenen números pastís.


Talls	Nombre màxim de trossos
0	1
1	2
2	4
3	7
4	11
5	16
6	22

Fórmula i seqüència

El nombre màxim p de peces que es poden crear amb un nombre determinat de talls $n$ (on $n \geq 0$ ) ve donat per la fórmula

p={\frac {n^{2}+n+2}{2}}.

Aquesta és la seqüència A000124 de l'OEIS, començant per $n = 0$ , és:

1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79 , 92, 106, 121, 137, 154, 172

Prova

Anomenem p = f(n) el nombre màxim de trossos que es poden obtenir d'un cercle amb n talls. Considerem el nombre de trossos afegits per l'últim tall. Aquesta línia, per obtenir el màxim de trossos, ha de travessar les n-1 línies anteriors.

La nova línia només pot creuar cada línia anterior una vegada. Una línia de tall sempre pot travessar totes les línies de tall anteriors, evitant els punts d'intersecció dels talls anteriors.

Al tallar n-1 línies es passa per n regions que d'aquesta manera es divideixen en dos afegint exactament $n$ al nombre de peces.

Així, el nombre total de peces després $n$ talls és

$f(n)=n+f(n-1).$

Aquesta relació de recurrència permet continuar, aplicat-la a $f (n - 1)$ s'obté

$f(n)=n+(n-1)+f(n-2).$

I seguint fins l'últim terme s'obté

$f(n)=n+(n-1)+(n-2)+\cdots +1+f(0).$

Com que $f(0)=1$ , perquè sense fer cap tall el disc és d'una peça, es pot reescriure com

$f(n)=1+(1+2+3+\cdots +n).$

El contingut del parèntesi és un progressió aritmètica, així que:

$f(n)=1+{\frac {n(n+1)}{2}}={\frac {n^{2}+n+2}{2}}.$

Referències

Moore, T. L. (1991), "Using Euler's formula to solve plane separation problems", The College Mathematics Journal (Mathematical Association of America) 22 (2): 125–130, DOI 10.2307/2686448.

Wetzel, J. E. (1978), "On the division of the plane by lines", American Mathematical Monthly (Mathematical Association of America) 85 (8): 647–656, doi:10.2307/2320333, <http://webcourse.cs.technion.ac.il/236603/Spring2008/ho/WCFiles/Wetzel.pdf>. Consulta: 15 desembre 2008.

Enllaços externs

Weisstein, Eric W. "Circle Division by Lines". MathWorld.^[1]

[[Categoria:Seqüències d'enters]] [[Categoria:Optimització]]

↑ Weisstein, Eric W. «Circle Division by Lines» (en anglès). [Consulta: 7 octubre 2024].

[1] Weisstein, Eric W. «Circle Division by Lines» (en anglès). [Consulta: 7 octubre 2024].

[1]