Delområder i det flerdimensionale rum

af

H. B. Hansen

 

Opgave

Hvad er det maksimale antal delområder, det d-dimensionale rum kan opdeles i ved hjælp af  (d-1)-dimensionale planer?

Eksempler

En ret linie (det 1-dimensionale rum) kan opdeles i n+1 liniestykker ved hjælp af n punkter (de 0-dimensionale planer), hvis blot punkterne er forskellige.

Går jeg én dimension op, bliver opgaven at finde det maksimale antal områder, som den 2-dimensionale plan kan opdeles i ved hjælp af n rette linier (de 1-dimensionale planer). Lad mig se på nogle simple eksempler. Hvis der er nul rette linier, så er der ét område; hvis der er 1 ret linie, så er der 2 områder; hvis der er 2 rette linier, så deles planen i 4 områder. Den talfølge, der giver antallet af delområder, starter altså således: {1, 2,4, ...}, altså potenser af 2, så nu håber man selvfølgelig, at der bliver 23 = 8 områder med 3 rette linier. Det viser sig imidlertid at være forkert: man kan højst få 7 områder ud af det, se figuren.

3 skærende linier

Katastrofe! Talfølgen af delområder starter altså således: {1, 2, 4, 7, ...} og spørgsmålet er, hvordan den fortsætter. For at besvare dette spørgsmål bemærker jeg, at den n´te linie højst kan skære alle de øvrige n-1 linier i ét punkt hver, dvs. n-1 skæringspunkter, hvilket giver anledning til n nye delområder. Og dette kan kun opnås, hvis den nye linie ikke er parallel med nogle af de øvrige linier, samt ikke skærer to andre linier i deres skæringspunkt. Det forudsætter jeg derfor er tilfældet.

På denne måde kommer jeg frem til følgende rekursion for det maksimale antal delområder an i det todimensionale tilfælde:

a0 = 1

an = an-1 + n

Nu er det let at finde det søgte antal for en hvilken som helst værdi af n, evt. ved hjælp af en computer. Fx finder jeg:

a4 = a3 + 4 = 7 + 4 = 11, a5 = 11 + 5 = 16, a6 = 16 + 6 = 22, osv.

Det kan man selvfølgelig også eftervise, ved at tegne skitser som ovenfor, men denne løsning er jeg imidlertid ikke tilfreds med. Jeg vil finde en formel for an udtrykt ved n, sådan at jeg kan bruge en lommeregner for at finde løsningerne, og sådan at jeg kan vurdere hvordan antallet af områder vokser med voksende n. Ved udfoldelse (såkaldt teleskopering) af rekursionen finder jeg:

an = an-1 + n = an-2 + (n-1) + n = an-3 + (n-2) + (n-1) + n = ... = a0 + 1 + 2 + ... + n

Da a0 = 1 og de øvrige tal danner en differensrække, finder jeg sluttelig:


Som det ses stemmer formlen for de første 4 værdier af n, så den er jeg tilbøjelig til at tro på. For en sikkerheds skyld vil jeg dog lige ved hjælp af induktion teste løsningen i den oprindelige rekursion:

Det viser sig altså, at antallet stiger med anden potens af n.

Men nu til den svære del af opgaven. Hvordan ser det ud for højere dimensioner end 2, fx i det 3-dimensionale rum, hvor det er 2-dimensionale planer der inddeler rummet?

Jeg indfører nu en ny notation, idet an(d) skal betegne den størrelse, jeg indtil nu har kaldt an, blot for dimensionen d.  Jeg har hidtil fundet an(1) = 1 + n og an(2) = 1 + n(n+1)/2. For at gå helt til grænsen vil jeg endvidere definere det 0-dimensionale rum som et punkt, der ikke kan deles af "planer" med mindre dimension; jeg har derfor an(0) = 1.

Fordelen ved denne notation er, at den sætter mig i stand til at nedskrive en betingelse, som an(d) skal opfylde. Det d-dimensionale rum skæres af (d-1)-dimensionale planer. Sporene bliver (d-2)-dimensionale "kurver". Lad os sige, at der indtil nu er sket n-1 skæringer, og at der derfor eksisterer an-1(d) delrum, defineret ved n-1 (d-1)-dimensionale planer. Nu kommer den n´te plan. Min hypotese er, at denne plan højst kan skære de øvrige planer med ét spor for hver plan. Det er rigtigt for d lig med 2 og 3; om det gælder for højere dimensioner skal jeg ikke kunne sige med sikkerhed, men det er i hvert fald min hypotese (som jeg i parentes bemærket ikke har kunnet bevise endnu). Under denne hypotese må det derfor gælde at:


Lad mig se, om denne sammenhæng stemmer for de små dimensioner, jeg hidtil har behandlet. For d = 1, det lineære rum, fås:

eller:


hvilket stemmer. For d = 2, den todimensionale plan, fås:


hvilket netop er den rekursion, jeg løste ovenfor.  Opgaven består derfor nu i at finde løsningen til rekursionen (1).

Det første jeg bemærker er, at denne rekursion er den samme, som man kender fra binomialkoefficienterne:


og som jo er grundlaget for Pascals trekant. Er løsningen til (1) simpelthen binomialkoefficienterne? Desværre nej, for startværdierne er anderledes. Hos Pascal er der kun ét 1-tal i øverste række, men her er der uendeligt mange, svarende til at der findes præcist 1 tomt d-dimensionalt rum for alle værdier af d. Men tallene an(d) kan tænkes ordnet i et todimensionalt skema med uendelig mange rækker og søjler. Det øverste venstre hjørne af dette skema ser således ud (brug formel (1)):


n d®

¯

0

1

2

3

4

5

6

0

1

1

1

1

1

1

1

1

1

2

2

2

2

2

2

2

1

3

4

4

4

4

4

3

1

4

7

8

8

8

8

4

1

5

11

15

16

16

16

5

1

6

16

26

31

32

32


Som det ses, stemmer tallene i søjle 1 og 2 med de formler, jeg har udledt tidligere. Det betyder, at jeg i princippet kan beregne an(d) for en hvilken som helst værdi af n og d ved hjælp af et simpelt computerprogram. Men igen: jeg ønsker at finde en sluttet formel for tallene.

En nærmere granskning af tabellen afslører, at tallene i og over diagonalen er potenser af 2. Man kunne i princippet undvære hele tabellen over diagonalen. Endvidere ser jeg, at tallene lige under diagonalen er disse potenser minus 1. Nu ved jeg, at summen af binomialkoefficienterne for et givet n er 2n. Det følger af, at


Da yderligere  og tallene under diagonalen som sagt er 1 mindre end topotenserne, får jeg mistanke om, at tabellen simpelthen indeholder summer af binomialkoefficienter. Stikprøver bestyrker min mistanke; fx er , hvilket stemmer med a(5,3) i tabellen.  Men kan jeg bevise denne mistanke? Det første, jeg kan gøre, er at undersøge om de løsninger for d = 1 og 2, jeg allerede har fundet, kan skrives som en sum af binomialkoefficienter. For d = 1 finder jeg , og for d = 2 fås

         .

Det ser jo godt ud, men det er stadig ikke noget bevis.

Men heldigvis kan mistanken bevises ved induktion. Jeg antager derfor nu, at løsningen til (1) er en sum af binomialkoefficienter, nærmere betegnet at:

       

samt at denne antagelse er bevist for alle delrum og dimensioner op til og med n-1 og d-1.  Nu medfører (1) at

        

Ved at bruge (2) på de to summer, idet leddene tages parvis, fås:       

       

Da mistanken er påvist at være sand for d = 0, 1 og 2, må den altså også være opfyldt for d = 3, osv. Min mistanke er blevet til vished!

Jeg har hermed bevist følgende sætning:

Det d-dimensionale rum kan højst opdeles i  delrum af n (d-1)-dimensionale underrum.