Skriftlig Eksamen DM11

Institut for Matematik og Datalogi Odense Universitet

Onsdag den 12. juni 1996, kl. 9–13

Alle sædvanlige hjælpemidler (lærebøger, notater, etc.) samt brug af lommeregner er tilladt.

Eksamenssættet består af 5 opgaver på 6 nummererede sider (1–6). Fuld besvarelse er besvarelse af alle 5 opgaver. Der er ialt 15 spørgsmål, som tillægges samme vægt ved bedømmelsen.

Der må gerne refereres til algoritmer og resultater fra lærebogen inklusive øvelsesopgaverne. Specielt må man gerne begrunde en påstand med at henvise til, at det umiddelbart følger fra et resultat i lærebogen (hvis dette altså er sandt!). Henvisninger til andre bøger (udover lærebogen) accepteres ikke som besvarelse af et spørgsmål.

Bemærk, at hvis der er et spørgsmål i en opgave, man ikke kan besvare, kan man godt besvare de efterfølgende spørgsmål og blot antage, at man har en løsning til de foregående spørgsmål.

Opgave 1

Denne opgave handler om rekursive definitioner, differensligninger og induktion.

Definer mængden L af strenge over alfabetet {a, b} som følger:

• λ ∈ L (Den tomme streng ligger i L.)

• Hvis x ∈ L, så ligger xaa og xbb også i L. (Man kan enten konkatenere symbolet a på højresiden to gange eller konkatenere symbolet b på højresiden to gange.)

Der er ikke andre strenge i L.

spørgsmål a

Bevis formelt at for alle strenge y ∈ L gælder der, at y har et lige antal a’er og et lige antal b’er.

spørgsmål b

Angiv en rekursionsligning (recurrence relation) der udtrykker hvor mange strenge af længde n, der er i L. Hvad er begyndelsesbetingelserne (the initial conditions)?

spørgsmål c

Løs relationen fra spørgsmål (b). Brug en karakteristisk ligning (characteristic equation) og angiv et svar, der gælder for alle n > 0. (Dvs. ikke en separat funktion for lige og ulige n.)

Opgave 2

Denne opgave handler om binomialsætningen (sætning 6 i afsnit 4.3).

spørgsmål a

Udtryk ∑_{j=0}^{n} ( \begin{matrix}n \\ j \end{matrix} ) 2^{j}3^{n−j} på lukket form (brug hverken ∑ eller ...).

spørgsmål b

Lad n ∈ ZZ, n > 1. Bevis at

∑_{k=1}^{n}(−1)^{k−1}k ( \begin{matrix}n \\ k \end{matrix} ) = 0.

Hjælp: bevis først at ( \begin{matrix}n \\ k \end{matrix} ) = \frac{n}{k} ( \begin{matrix}n − 1 \\ k − 1 \end{matrix} ), hvis n ≥ k ≥ 1, n > 1.

Denne opgave handler om tælleargumenter og sandsynlighedsregning.

Lad n ∈ ZZ, n ≥ 5. Lad en (5, n)-sekvens være en strengt aftagende sekvens af 5 positive heltal, der alle er mindre end eller lig med n. Dvs. et 5-tupel (a_{1}, a_{2}, a_{3}, a_{4}, a_{5}), hvor n ≥ a_{1} > a_{2} > a_{3} > a_{4} > a_{5} ≥ 1. Lad et eksperiment A bestå i at vælge 5 heltal tilfældigt og uafhængigt fra en uniform fordeling (valgt med lige sansynlighed) over S, hvor S = {1, 2, ..., n}.

spørgsmål a

Lad K_{n} betegne antallet af forskellige (5, n)-sekvenser. Find K_{n}.

spørgsmål b

Hvad er sandsynligheden p_{n} for at udfaldet af eksperimentet A bliver en (5, n)-sekvens?

spørgsmål c

Antag at man gentager eksperimentet A indtil man får en (5, n)-sekvens. Hvad er det forventede antal eksperimenter?

spørgsmål d

Hvor mange (5, n)-sekvenser findes der, som opfylder a_{i−1} − a_{i} > 1 for i ∈ {2, 3, 4, 5}?

Opgave 4

Denne opgave handler om en relation over A = {(a, b, c) | a, b, c ∈ ZZ}. Definer relationen R sådan:

((a, b, c), (x, y, z)) ∈ R hvis 5 | (a + b + c − (x + y + z)).

Notationen “5 | k” betyder, at “5 går op i k”.

spørgsmål a

Bevis at R er en ækvivalensrelation.

spørgsmål b

Hvor mange ækvivalensklasser er der? Beskriv dem.

Denne opgave handler om gruppeteori.

Lad G være en abelsk gruppe (abelian group) af orden n. Definer en kubikrod af et element x ∈ G til at være et y ∈ G, sådan at y ⊙ y ⊙ y = x. Hvis x har mindst én kubikrod, så kaldes det et kubik-element.

spørgsmål a

Bevis at {x | x er et kubik-element} er en undergruppe af G.

Antag nu, at G er cyklisk, og at 3|n. Lad g være en frembringer (generator) for G, og lad e være det neutrale element (identity) i G.

spørgsmål b

Bevis at {g^{n/3}, g^{2n/3}, e} er kubikrødder af e.

spørgsmål c

Bevis at e ikke har andre kubikrødder end de i spørgsmål (b) angivne.

spørgsmål d

Bevis at enhvert kubik-element i G har præcis 3 kubikrødder.