Tag Archives: combinaties

het dubbele achternaam ‘probleem’

Een hot-topic op dit moment is het wetsvoorstel betreffende de dubbele achternaam die we voor onze kinderen kunnen kiezen (de mogelijkheden zijn de naam van de moeder, de vader, moeder-vader of vader-moeder). Vooral het woordje “kiezen” hierin is belangrijk want velen hebben het foute idee dat dit een verplichting wordt. Nochtans kan je evengoed voor het traditionele gaan en de achternaam van de vader laten doorlopen in de volgende generatie.
Een argument dat sommigen naar voor schuiven tegen het wetsvoorstel, is dat het aantal combinaties van mogelijke namen snel zal stijgen voor komende generaties. Volgens hen zal dit de keuze van de door te geven naam bemoeilijken met discussies en familievetes als gevolg.

Maar hoeveel van deze combinaties zijn er eigenlijk? Kunnen we hier een wiskundige formule voor ontwerpen?
Wel eigenlijk is dit niet zo moeilijk. Laten we eerst even 1 generatie bekijken, of met andere woorden, welke achternamen zouden onze kinderen kunnen krijgen?
!!! We beginnen dus bij het standpunt dat vandaag iedereen nog een enkele achternaam heeft !!!
Laat ons die voor de makkelijkheid even gewoon A, B, C, … noemen. Een kleine stamboom ziet er dan als volgt uit.
1

Je kan zien dat mijn zoon of dochter dus 4 mogelijke achternamen zal kunnen krijgen. Hoe zit het als we een generatie verder kijken?
2
De keuze word al meteen verviervoudigd tot 16 mogelijkheden! Als we weer een generatie opschuiven en naar mijn achterkleinkinderen gaan kijken zullen ze al een keuze hebben tussen 64 namen, weer een viervoud groter dus.
Je hebt allicht door dat dit patroon zich verder zal blijven zetten en de keuze in namen dus steeds een macht van vier zal zijn.

MAAR dan houd je geen rekening met het feit dat enkele van je voorouders een achternaam gemeen zouden kunnen hebben… Neem nu de familienaam Peeters, wat de meest voorkomende achternaam in België is. Maar liefst 33.000 landgenoten dragen deze achternaam. Het is dus mogelijk dat zowel je oma aan vaders kant én je oma aan moeders kant beide mevrouw Peeters zullen heten. Dit heeft echter wel een invloed op de telling want in dit geval ziet je stamboom en de keuze van namen er als volgt uit:
1-2

In dit geval heeft het kind ‘slechts’ keuze tussen 9 familienamen… niet 16 zoals in het vorige geval, en het is al zeker geen macht van 4.
De algemene formule vinden ligt dus ietsje moelijker. Laten we een tweede poging ondernemen.

Eerst merk je op dat je elke naam van je voorouder kan krijgen als je ouders en voorouders kiezen om slechts een enkele naam door te geven en het nieuwe systeem dus links te laten liggen. In stamboom 2 waren er 4 voorouders: A, B, C en D en je ziet dat het kind deze 4 namen kan doorkrijgen. In stamboom 3 zaten er slechts 3 namen (A, B en C) in de mix en het kind kan dus A, B of C heten met zijn achternaam, 3 mogelijkheden dus.
Het aantal ENKELE namen dat je kan krijgen = het aantal namen dat in de ‘begingeneratie’ zit.

Wat is nu het aantal mogelijkheden als je voorouders wel kiezen om dubbele achternamen te beginnen gebruiken?
Hiervoor moet je gaan kijken welke onderlinge combinaties er mogelijk zijn. Voor de makkelijkheid veronderstellen we even dat A-B gelijk is aan de naam B-A zodat we even enkel naar de ‘koppels’ kijken en de volgorde van de namen negeren. In onderstaande tabel zie je hoe het aantal koppels evolueert:

koppels
Als je goed kijkt kan je opmerken met hoeveel het aantal koppels stijgt telkens er een persoon bij komt. Inderdaad, het aantal stijgt met respectievelijk +1, +2, +3, +4, … koppels.
0
0 + 1 = 1
1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
10 + 5 = 15

Deze reeks 1,3,6,10,15,… noemen we de driehoeksgetallen. Deze naam word duidelijk als je de getallen op de volgende manier grafisch voorstelt:
drieh

We kunnen dus zeggen dat het aantal koppels te maken met N personen gelijk is aan Δ(N-1) . Hierij bedoelen we het (N-1)de driehoeksgetal. LET OP, we moeten dit aantal nog wel verdubbelen als we onderscheid maken tussen het koppel A-B en B-A, of met andere woorden als de volgorde wel van belang is (en bij ons namen-probleem speelt die volgorde dus wel degelijk een rol).
Het aantal DUBBELE namen dat je kan krijgen = Δ(N-1) x 2 met N het aantal namen dat in de ‘begingeneratie’ zit.

Als laatste moeten we nog opmerken dat we bij het tellen van de verschillende koppels enkel diegene telde van de vorm A-B waarbij A ≠ B. Maar zoals aangehaald bij stamboom 3 kan het ook zijn dat er namen gedeeld worden waar door je zoals in de figuur kan zien ook achternaam B-B kan erven. We moeten met andere woorden nog een laatste term bijvoegen bij onze formule, namelijk term D. Hierbij zeggen we dat D het aantal namen is dat dubbel voorkomt bij de ‘begingeneratie’.

Zo, nu hoeven we enkel het aantal keuzes van ENKELE namen op te tellen met het aantal mogelijkheden om een DUBBELE naam te kiezen. Het totale aanbod zal dus N + [Δ(N-1) x 2] + D  zijn waarbij N het aantal namen is dat in de begingeneratie zit, en D het aantal namen dat in deze beginsituatie dubbel voorkomt.

DAAROM WISKUNDE

Giedts Tom

Advertisements

Leave a comment

Filed under andere

ACCES DENIED: je smartphone beveiligen

Een gewone gsm is al langer niet meer uit het straatbeeld te denken maar de moderne smartphones beginnen nu ook steeds meer de standaard te worden. Sinds de Blackberry’s op de markt kwamen proberen technologiegiganten steeds meer gadgets of apps in hun mobiele telefoons te proppen. Ofwel heb je er zelf eentje, ofwel ken je ongetwijfeld wel iemand anders die met een Iphone, Samsung Galaxy of Nokia Lumia telefoneert.

Natuurlijk willen we, nu er steeds meer van onze persoonlijke gegevens in onze smartphones verdwijnen, onze telefoons goed beveiligen. Bij het opzetten van je telefoon moet je natuurlijk allereerst je pin-code ingeven. Maar eens je telefoon aanstaat hebben we nu ook de mogelijkheid om een extra schermbeveiliging in te stellen. Hiervoor geven de producenten ons zelfs enkele mogelijkheden. 

Afbeelding

3 van dit soort mogelijkheden die ik heb op de Samsung Galxy 4S, die ik onlangs kocht, zijn pincode (een tweede pincode naast de originele om de sim-kaart te ontgrendelen), een wachtwoord of een patroon. Er zijn nog enkele andere keuzes zoals gezicht en stem herkenning. Maar aangezien deze technologie nog niet op punt staat geeft ook Samsung aan dat deze slechts een lage beveiliging kunnen garanderen. De 3 keuzes die ik boven noemde zijn volgens de smartphone het veiligste. De volgorde waarin ik ze gaf is volgens Samsung trouwens de volgorde van minst veilig tot meest beveiligend voor mijn gegevens te coderen.
Maar is dat wel zo? Met andere woorden, laten we de drie methodes eens naast elkaar leggen en kijken welke de moeilijkste is om te kraken.

1. PATROON (Volgens Samsung “normale beveiliging”)

Er zijn 9 stippen waarop je een zelfgekozen patroon moet tekenen. Hiermee bedoel ik dat je in een gekozen volgorde de stippen moet doorlopen. Bijvoorbeeld in volgorde 1-5-9-8-6. Dus je begint bij stip 1, je veegt naar stip 5, dan naar stip 9, dan naar stip 8 en dan naar stip 6. Allemaal in 1 beweging zonder je scherm te lossen. In de afbeelding hieronder is de gekozen volgorde dus 7-4-1-6-8-5-2-3-9.AfbeeldingLet wel op, er bestaan enkele voorwaarde voor je patroon. Zo kan je elk getal slechts 1 keer bezoeken. Het patroon 1-5-1-2-3 is dus niet mogelijk want hier bezoek je stip 1 tweemaal. Een andere restrictie is dat de telefoon geen verschil zit tussen de volgorde 7-1 of 7-4-1. Met andere woorden als je van 7 naar 1 schuift ‘denkt’ de smartphone dat je ook stip 4 bezocht hebt omdat deze stip op de verbindingslijn tussen 1 en 7 ligt. Hetzelfde geldt bijvoorbeeld als je van vakje 1 naar vakje 9 beweegt. Dan zal mijn Galaxy ‘denken’ dat ik ook vakje 5 gepasseerd bent. Het patroon van op de foto kan dus even goed 7-1-6-8-2-3-9 zijn. 
De 3de en laatste voorwaarde is dat je in je patroon minstens 4 vakjes moet bezoeken (en maximum 9 maar dit volgt al uit voorwaarde 1).

Stel dat we enkel de voorwaarde hebben dat je combinatie uit minstens 4 en maximum 9 cijfers kan bestaan, hoeveel mogelijkheden hebben we dan? Van een combinatie van lengte 4 zijn er 9*9*9*9 = 9^4 mogelijkheden, van lengte 9^5 mogelijkheden… van cijfercombinaties van lengte 9 zijn er 9^9 mogelijkheden. in totaal hebben we dus 9^4 + 9^5 + … + 9^9 = 435.847.230 mogelijkheden wat best veel is. Maar door de eerste voorwaarde (dat geen enkel cijfer 2 maal mag voorkomen) verkleint dit aantal drastisch.

Als 1ste vakje kunnen we kiezen uit alle 9, Voor het 2de vakje kunnen we nog maar kiezen tussen de 8 overgebleven stippen. Voor het derde cijfer zijn er nog maar slechts 7 mogelijkheden, voor het 4de nog maar 6….
Om een cijfercombinatie van 4 cijfers te kiezen hebben we dus keuze tussen 9*8*7*6 mogelijkheden= 9!/5! = 3.024
Voor een lengte van 5 hebben we de keuze tussen 9*8*7*6*5 = 9!/4! = 15.120.

Voor een lengte van 9 cijfers hebben we de keuze tussen 9*8*7*6*5*4*3*2*1 combinaties = 9!/0! = 362.880
Als we de mogelijkheden van al de lengtes optellen bekomen we een totaal van 985.824. We hebben dus duidelijk een pak minder mogelijkheden nu deze voorwaarde er is.

Als we dan nog eens rekening houden met de restrictie dat de telefoon het verschil niet ziet tussen bijvoorbeeld 1-2-3 of 1-3 zijn er nog eens minder mogelijkheden. Het uiteindelijke aantel slinkt zo tot slechts 389.112 combinaties om je GSM op slot te zetten via het patroon -systeem.
Afbeelding
2. PIN-CODE (Volgens Samsung “normale tot hoge beveiliging”)

Hier hebben we een klassiek voorbeeld van beveiliging. Je moet een cijfercombinatie maken met de cijfers 0-9 (bij de beveiliging met behulp van het patroon kon je 0 niet kiezen). Je moet wel minstens 4 cijfers gebruiken en maximum 16. Merk op dat deze minimum en maximumlengtes de enige restricties zijn. Je mag dus getallen meermaals gebruiken. Er zijn dus 10^4 mogelijke PIN-codes van lengte 4. 10^5 mogelijke codes van lengte 5. … En 10^16 mogelijke codes van lengte 16. In totaal dus 1.111.111.111.111.000 mogelijkheden.
Afbeelding

3. WACHTWOORD (Volgens Samsung “hoge beveiliging”)

Anders dan bij de PIN-code kan je hier buiten cijfers, ook letters (én hoofdletters) en leestekens kiezen. De lengte moet wederom tussen 4 en 16 liggen. Een bijkomende voorwaarde hier is dat er minstens 1 letter in je wachtwoord voorkomt. Hoeveel combinaties zijn er nu? Wel we kunnen telkens kiezen tussen 10 cijfers + 26 letters + 26 hoofdletters + 31 tekens = 93 mogelijke input.
Van lengte 4 zijn er dus 52 * 93^3 mogelijkheden. het zou 93^4 geweest zijn moest de voorwaarde van minstens 1 letter er niet geweest zijn. Deze is er nu wel en dus voor 1 teken kunnen we ‘slechts’ kiezen tussen 52 letters (26 gewone en 26 hoofdletters). voor lengte 5 zijn er 52 * 93^4 mogelijkheden… Voor lengte 16 zijn er 52 * 93^15 mogelijkheden.

Als we al de mogelijkheden van lengte 4, lengte 5, … lengte 16 optellen komen we op een totaal van 17.698.754.009.582.674.592.842.094.110.164 mogelijkheden!!!
Als elke (van de 7 miljard) mens op aarde per seconde 1 miljard combinaties zou kunnen uittesten, zou het de mensheid nog meer dan 80.000 jaar vragen om alle combinaties uit te proberen.
Afbeelding

BESLUIT:
De volgorde die Samsung ons aangeeft van minst naar meest beveiligende code is de correcte.
1. PATROON (normale beveiliging) 389.112 combinaties
2. PIN-CODE (normale tot hoge) 1.111.111.111.111.000 combinaties
3. WACHTWOORD (hoge) 17.698.754.009.582.674.592.842.094.110.164 combinaties

DAAROM WISKUNDE

Giedts Tom

Leave a comment

Filed under andere