matematikk.net

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.

96?

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

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å.

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