Is een kruiswoordraadsel wiskunde? (opnieuw simpele JWO)
Opgave - JWO 2006 dag 1 vraag 4
Een kruiswoordraadsel van vijf bij vijf kan volledig worden ingevuld met woorden van niet meer dan drie letters. Vanuit elk wit vlak moet elk ander wit vakje bereikbaar zijn door alleen maar horizontaal of vertikale stappen te zetten zonder over zwarte vakjes te passeren.
Wat is het minimaal aantal zwarte vakjes waarvoor dit mogelijk is?
Oplossing
Er moet tenminste 1 zwart vakje per rij en kolom zijn, want ander zouden er 5 witte vakjes op een rij of kolom zijn en dat mag niet.
1, 2, 3, en 4 kan dus niet.
5 kan ook niet omdat als je eentje per kolom en rij doet zal elk vakje op een verschillende kolom en rij liggen. Het vakje op de 1ste rij is de eerste op zijn kolom, en daardoor zijn er 4 witte vakjes onder elkaar in deze kolom, wat niet mag.
6 kan, en er is daar een voorbeeld van:
http://www1.picturepush.com/photo/a/5509364/img/Anonymous/bewijs-kruiswo...
In iedere rij en kolom moet een zwart hokje staan om te vermijden dat een hele rij wit is. Er zijn dus al zoiezo minstens $5$ zwarte hokjes nodig.
Om dit minimum te bereiken, mag er ook niet meer dan $1$ hokje zwart zijn per kolom en rij.
Als we met $1$ vakje zwart per kolom kijken, merken we dat we, wanneer we voor de horizontale woorden kijken, nooit een zwart vakje mogen hebben volledig links of rechts. Wanneer we onze vakjes zo zouden opstellen, zouden we dus $2$ open kolommen krijgen, wat $5$ dus ook volledig uitsluit als mogelijkheid.
Bij 6 kan je gebruikmaken van $1$ extra zwart blokje om je kruiswoordraadsel op te vullen. Dit biedt het voordeel dat je $1$ rij en $1$ extra kan 'indekken' om geen woorden langer dan $3$ letters te hebben en dus kan je hier wel 2 vakjes op uiterste kolommen plaatsen (bv. $1$ van de huidige links en het nieuwe rechts op dezelfde rij), wat $6$ (in theorie) mogelijk maakt.
De redenering wordt na even zoekwerk ook bewezen met deze opstelling (A=wit, X=zwart)
AXAAA
AAXAA
XAAAX
AAAXA
AXAAA