WisFaq!

Binairo

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
9-12-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·F₁₂ = 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.

Er komt 208 uit.

hr
30-12-2010