Discrete Wiskunde

Examen 13 juni 2008

1. Zij $V=\{x\in \mathbb{\mathbb{Z}}|1\le x\le 70,x\equiv ̸0mod7,x\equiv ̸6mod7\}$.
   1. Zij W een deelverzameling van V met 37 elementen. Toon aan dat er twee getallen in W zijn die 4 van elkaar verschillen.
   2. Optimaliseer de vorige opgave door 37 te vervangen door een zo klein mogelijk getal.
2. Deze oefening gaat over de kubus. We kleuren enerzijds de zes zijvlakken en anderzijds zes toppen zodat twee overstaande toppen niet gekleurd zijn.
   1. Op hoeveel manieren kan je deze 12 objecten kleuren met de kleuren groen, blauw en rood?
   2. Op hoeveel manieren kan je deze 12 objecten kleuren zodat er 3 groene en 3 blauwe zijvlakken zijn en er 3 blauwe en 3 rode punten zijn?
3. 1. Zij $(V_1,{{ℬ}}_1)$ een 2-$(v_1,3,1)$ design en $(V_2,{{ℬ}}_2)$ een 2-$(v_1,3,1)$ design. Construeer op het Cartesiaans product $V_1\times V_2$ een 2-$(v_1{v}_2,3,1)$ design.
   2. Zij V = {A,B,C,D,E,F,G} en $(V,{ℬ})$ het 2-(7,3,1) design. Construeer op $V\times \{1,2,3\}$ een 2-(21,3,1) design.
4. Voor welke $\lambda \in \mathbb{\mathbb{Z}}\setminus \{0\}$ is de volgende uitdrukking te schrijven als de som van een (vast) aantal hypergeometrische termen in n? Bereken deze som voor de gevonden $\lambda$.
   1. $\sum _{k=0}^{n-1}\frac{(k+1){\lambda }^k}{k!}$
   2. $\sum _{k=0}^{n-1}\frac{{\lambda }^k}{k!}$
5. (Mondeling) Bewijs de Gilbert-Varshamov grens.

Examen 24 juni 2005

1. Bewijs dat in een verzameling met 3n+1 elementen in het vlak waarvan elke 4 elementen er minumum 2 maximum op 1 afstand liggen er minimum n+1 elementen zijn die binnen een gesloten cirkel met straal 1 liggen.
2. Hoeveel verschillende manieren bestaan er bij een vijfvlak (twee driehoeken met drie vlakken tussen) de toppen en de vlakken te kleuren met rood, geel en blauw zo dat:
   • er minimum 5 toppen rood zijn
   • de twee driehoeken in verschillende kleuren zijn
3. Neem een 2-(v,k,lam)-design (V,B). Neem dan (V,B_) waarbij B_ = {b_ = V\b|b el. van B_}. Toon aan dat dit een 2-(v,v-k,lam_) design is en bepaal lam_
4. Toon aan dat f(n) = sum over k=1..n (2^k*lam^k) te schrijven valt als de som van twee hypergeometrische reeksen en voor welke lambda
5. Bewijs dat voor een gegeven controle-veelterm van een (n,k)-cyclische code h=h_0+..+h_kX^k de matrix H zoals in boek pag. 312 welk degelijk de pariteitscontrole matrix is.

Examen 19 juni 2007

Het examen was volledig open boek. Vraag 5 was mondeling te verdedigen bij Veys, de rest was schriftelijk.

1. Toon aan dat er een getal bestaat van de vorm 20062006...2006, dat deelbaar is door 2007.
2. Het kaartspel 'Set!' (Veys had zo'n kaartspel mee om te tonen op het examen) bestaat uit 81 kaarten, waarbij op elke kaart een aantal (1,2 of 3) gekleurde ( rood, groen of paars ) figuren (ruiten, ovalen of krullen) met een bepaalde opvulling ( vol, gearceerd of leeg ) zijn getekend en waarbij elke mogelijke samenstelling van de vier kenmerken voorkomt. We noemen 3 kaarten een 'set' als elk van de vier kenmerken ofwel hetzelfde is ofwel helemaal verschillend ( de 3 mogelijkheden komen voor ) op de drie kaarten. Noteer door V de verzameling kaarten en door B de verzameling 'sets'.
   • Voor welke t is (V,B) een t-(81,3,lambda)-design ? Bepaal de maximale waarde van t en bereken b = |B|.
   • met welk bekend design is dit design isomorf? Geef een isomorfisme. Met welk blok komt de set bestaande uit 2 paarse volle krullen, 3 paarse volle ruiten en 1 paarse volle ovaal overeen ?
3. • Op hoeveel verschillende manieren kan men de hoekpunten en zijvlakken van een octaëder kleuren met rood, geel en zwart, zodat in totaal 2 zijvlakken of hoekpunten rood, 3 geel en 9 zwart zijn ?
   • Op hoeveel manieren kan dit als we bovendien eisen dat 2 overstaande hoekpunten rood moeten zijn ?
4. Voor welke a in de natuurlijke getallen > 0 is $\sum _{k=0}^{n-1}\frac{k(k+1+a)a^k}{(k+1)!(k+a)!}$ te schrijven als een som van hypergeometrische termen in n ? Geef en bewijs voor al deze a deze som.
5. Leg het protocol van Fiat-Shamir uit. Waarom moet de geheime sleutel inverteerbaar zijn ?