We kregen de vraag over het spelletje Binairo, dat is een soort soduku met deze regels:
1) Je mag enkel nullen en eentjes gebruiken 2) Niet meer dan 2 nullen of 2 éénen naast elkaar 3) Er moeten 6 enen en 6 nullen in één rij staan 4) Er is slechts 1 oplossing
En de vraag was, op hoeveel manieren kan je 1 rij invullen... Dank u
Joey
3de graad ASO - donderdag 9 december 2010
Antwoord
Hallo, Joey.
Je vraagt op hoeveel manieren je een rij van lengte twaalf kunt maken met zes nullen en zes enen, waarbij niet meer dan twee nullen of enen naast elkaar staan?
Als je een boom maakt met aan de wortel een 1, en dan een niveau hoger een 1 of een 0, en dan een niveau hoger boven de 1 een 0 en boven de 0 een 1 of een 0, etcetera, dan merk je dat op niveau k het aantal voortzettingen gelijk is aan het k-de Fibonaccigetal in de reeks 1,2,3,5,8, ...
Je kunt natuurlijk ook met een 0 aan de wortel beginnen.
Dus er zijn 2·F12 = 466 rijen van lengte twaalf waarbij niet meer dan twee nullen of enen naast elkaar staan. Nu moet je nog tellen hoeveel daarvan evenveel nullen en enen hebben.
Je kunt het doen met dit pascalprogramma:
program rijtjes; var a:integer; k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12:0..1; begin a:=0; for k1:=0 to 1 do for k2:=0 to 1 do for k3:=0 to 1 do for k4:=0 to 1 do for k5:=0 to 1 do for k6:=0 to 1 do for k7:=0 to 1 do for k8:=0 to 1 do for k9:=0 to 1 do for k10:=0 to 1 do for k11:=0 to 1 do for k12:=0 to 1 do if k1+k2+k3+k4+k5+k6+k7+k8+k9+k10+k11+k12=6 then if k1+k2+k3<3 then if k2+k3+k4<3 then if k3+k4+k5<3 then if k4+k5+k6<3 then if k5+k6+k7<3 then if k6+k7+k8<3 then if k7+k8+k9<3 then if k8+k9+k10<3 then if k9+k10+k11<3 then if k10+k11+k12<3 then if not k1+k2+k3=0 then if not k2+k3+k4=0 then if not k3+k4+k5=0 then if not k4+k5+k6=0 then if not k5+k6+k7=0 then if not k6+k7+k8=0 then if not k7+k8+k9=0 then if not k8+k9+k10=0 then if not k9+k10+k11=0 then if not k10+k11+k12=0 then a:=a+1; writeln(a:5); readln end.
