Obligatorisk oppgavesett nr. 2, MAT1030, våren 2005

Besvarelsene, tydelig merket med “Oblig 2, MAT1030, våren 2005” og ditt fullstendige navn, må leveres innen fredag 29. april 2005 klokken 14.30 i ekspedisjonen for Matematisk institutt, i 7. etasje i N. H. Abels hus.

Det er tillatt å bruke alle hjelpemidler. Det er lov å samarbeide, men studenten skal selv ha skrevet den besvarelsen som leveres inn, og den skal gjenspeile studentens forståelse av stoffet. Studenten kan bli bedt om å redegjøre muntlig for innholdet i den obligatoriske oppgaven.

Oppgave 1

Krypteringsmaskinen “Enigma” benyttet fem kodehjul, nummerert 1, 2, 3, 4 og 5, som hver for seg kunne dreies til en av tjueseks innstillinger, merket a, b, ..., z. Før bruk ble tre forskjellige kodehjul valgt ut og plassert etter hverandre i tre spor i maskinen, nummerert I, II og III. Deretter ble hver av disse tre kodehjulene dreid til en av de tjueseks innstillingene, uavhengig av de andre kodehjulene.

F. eks. kunne hjul 3, 1 og 4 brukes i spor I, II og III, dreid til innstillingene f, o og o.

a) Hvor mange forskjellige utvalg og plasseringer av tre kodehjul var mulige?

b) Hvor mange forskjellige innstillinger kunne oppnås ved å dreie på de tre kodehjulene? (Når et utvalg og en plassering er fastlagt, som i a).)

Maskinens tastatur hadde tjueseks tegn (A, B, ..., Z), og en koblingsboks der ti par av forskjellige tegn ble ombyttet, parvis, mens de resterende seks tegnene forble uendret.

F. eks. kunne A byttes med B, C med D, E med F, G med H, I med J, K med L, M med N, O med P, Q med R og S med T, mens U, V, W, X, Y og Z var uendret. Eller A kunne byttes med Z, B med Y, C med X, D med W, E med V, F med U, G med T, H med S, I med R og J med Q, mens K, L, M, N, O og P var uendret.

c) Hvor mange forskjellige ombyttinger av tegn var mulige?

Oppgave 2

En simpel graf G kalles homogen dersom det for hvert par av hjørner x og y i G finnes en isomorfi f fra G til seg selv som tar x til y, dvs. med f(x) = y. Dette betyr at G “ser likedan ut fra hvert hjørne”, opp til isomorfi.

La G være en simpel homogen graf med n hjørner og m kanter.

a) Forklar hvorfor alle hjørnene i G har samme grad.

b) Hvis n er et oddetall, så må alle hjørnene i G ha jevn grad. Forklar hvorfor.

c) Tegn alle de simple homogene grafene med n=5 hjørner, opp til isomorfi. Mer presist, tegn en og bare en representant fra hver isomorfiklasse av slike grafer. Hint: Bruk resultatene i a) og b).

Oppgave 3

En ball B er dekket med fem- og sekskantede lærlapper, som er sydd sammen langs kantene slik at to lapper møtes langs hver kant og tre kanter møtes i hvert hjørne. De sammensydde kantene og hjørnene danner da en graf G på ballen B.

La P (for pentagon) være antallet femkantede lapper, H (for heksagon) være antallet sekskantede lapper, la F = P + H (for “faces”) være det totale antallet lapper, la E (for “edges”) være antallet kanter i G, og la V (for “vertices”) være antallet hjørner i G.

Euler vis(s)te at antallet hjørner, kanter og sideflater alltid oppfyller likningen

V – E + F = 2 .

Du skal ikke bevise dette.

a) Forklar hvorfor E = (5P + 6H)/2 .

b) Forklar hvorfor V = 2E/3 .

c) Bruk likningene ovenfor til å vise at antallet femkantede lapper, P, alltid er det samme, og til å finne dette antallet.

John Rognes, 11. april 2005

2005-01-25T10:37:59