Parenteser

[daofeishi]

Vår venn Brynjar, advokaten, sitter og arbeider med et viktig rettslig dokument. Det begynner å bygge seg på med klausuler og tilleggsklausuler, som alle fordrer avklaringer, ordforklaringer og referanser til lovtekstene. Ved nærmere gjennomlesing ser han at parantesene i første linje i dokumentet fordeler seg slik, dersom du utelater ordene:

( ()((()(())))( ()() )() )

Han begynner så å tenke...
..."hvordan vet jeg at det ikke er kluss med parentesene her... Det må helt klart være like mange venstreparenteser som høyreparenteser. Det kan heller ikke, dersom jeg starter å telle fra venstre, på noe punkt i rekken være flere høyreparenteser enn venstreparenteser..." Denne tankerekken avbrytes imidlertid av et nytt spørsmål:

"Gitt at vi har n parenteser - hvor mange 'lovlige' måter finnes det å plassere dem sammen? For eksempel, gitt 3 parenteser, finnes det fem muligheter:
((())); (()()); (())(); ()()(); ()(())"

Kan du hjelpe Brynjar?

[Knuta]

Om jeg kan hjelpe Brynjar? Tja eg veit ikke, men jeg kan jo prøve å telle.
Jepp det var det jeg gjorde. først 1. Så 2. og så var det på tide å sette opp noe.

Og dette kom jeg fram til:
[tex]P_n=\frac{(2n!)}{(n!)^2 (n+1)}[/tex]

hvilket gir [tex]P_{11}= 58786[/tex]

[daofeishi]

Stemmer det, Knuta. Har du et annet bevis for det? (Telling i seg selv er jo ikke et gyldig bevis )

[Knuta]

Øhhh. Det var det værre med. i tallteori er jeg som alt annet med veldig dårlig i. Jeg finner bare et mønster og vips så ligger resultatet der. Vanskelig å forklare.

[daofeishi]

Hvor mange ledd i følgen regnet du ut før du fant uttrykket? Dersom du regnet ut f.eks. til 6. ledd, (43), finnes det likevel mange ulike følger som tilsynelatende tilfredsstiller tallene.

De 6 første er 1, 1, 2, 5, 14, 42, 132

Hvordan vet du at følgen er
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900...
og ikke
1, 1, 2, 5, 14, 42, 132, 428, 1416, 4744, 16016, 54320, 184736, 629280...
eller
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4861, 16778, 58598, 206516, 732825...
eller
1, 1, 2, 5, 14, 42, 132, 429, 1429, 4846, 16645, 57686, 201158, 704420...
eller
1, 1, 2, 5, 14, 42, 132, 429, 1429, 4852, 16730, 58422, 206192, 734332...
eller
1, 1, 2, 5, 14, 42, 132, 428, 1417, 4757, 16119, 54963, 188219, 646460...
osv, osv...

Som alle er matemematiske følger av en viss betydning. (Sjekk Sloane's)

[Knuta]

Jeg skal innrømme en ting. Det tok meg fem minutter å finne svaret. Det ble tellet. Jeg hadde svaret før jeg rakk å blunke.

Det jeg gjorde var å bytte ut "(" med "+1" og ")" med "-1" så kombinasjonen ()() er +1-1+1-1. Legger man sammen dette får man 1010. Tilsvarende 1210 som er (()). Måtte bare sjekke at svaret ikke under noen omstendighet hadde gått under null. Veldig lett oppgave i sammenlignet med ProjectEuler. Jeg hadde svaret, slo opp i sloane og der lå formelen. Men svaret hadde jeg ved brute force, så det vet jeg at er riktig.

I ProjektEuler finnes det for det meste oppgaver det ikke går ann å slå opp. De spør som regel etter P_100 og gir to, tre eksmpler. Ok, så teller man opp fem, seks stykker og leter etter mønster. Da må man virkelig sette barken i sving, for brute force metoden tar alt for lang tid.