Kombinatorikk på sjakkbrett

[Karl_Erik]

Du har et 4x4-sjakkbrett, og 6 identiske marihøner. Du ønsker å plassere marihønene på en slik måte at enhver rad inneholder et partallig antall marihøner, og enhver kolonne inneholder et partallig antall marihøner. Hvor mange måter kan dette gjøres på?

For å oppklare:

OMMO
MMOO
MOMO
OOOO

der M indikerer en marihøne og O en tom rute en gyldig måte å gjøre dette på, mens

MMMM
OMMO
OOOO
OOOO

ikke er det, da kolonnene på siden inneholder én marihøne hver.

[Vektormannen]

96?

[Karl_Erik]

Det er riktig, ja. Har du et bevis også?

[Vektormannen]

Nei Jeg er ganske dårlig på å formulere formelle bevis. Men tankegangen var slik:

Vi avgrenser oss først til et 3x3-brett. Da må marihønene plasseres slik at det i hver rad og hver kolonne er én rute der det ikke er en marihøne. Dette kan gjøres på 3! måter. På et 4x4-brett vil marihønene alltid måtte plasseres slik at det blir én rad uten marihøner, og én kolonne uten marihøner. Disse radene og kolonnene kan befinne seg i 4*4 = 16 forskjellige kombinasjoner på brettet. På de gjenværende rutene må marihønene plasseres i én av de 3! konfigurasjonene som er på et 3x3-brett. Det gir totalt 3! * 4 * 4 = 96 måter å plassere dem på.

[Karl_Erik]

Men dette er da et finfint bevis det. Veldig bra.