Fasit til "Ukens nøtt 5"

Nøtten (til uken 27/9-1/10)

Et kvadratisk brett er delt inn i 36 like store, kvadratiske ruter. Du har 18 dominobrikker som hver dekker to ruter på brettet. Er det mulig å dekke hele brettet med dominobrikker slik at det ikke oppstår vertikale eller horisontale sprekker? En vertikal sprekk er en vertikal linje gjennom brettet som ikke skjærer noen av dominobrikkene, og en horisontal sprekk er definert tilsvarende.

Løsning

Dominobrikkene kan plasseres på to måter - liggende og stående. La oss først se hvor mange stående brikker det må være for at vi skal unngå horisontale sprekker. Vi tenker oss at vi fyller opp med stående brikker nedenfra. Hvor mange stående brikker kan det være som hviler på den nederste kanten av brettet? Det må være et like antall (ellers får vi ikke fylt opp hele brettet), og skal vi unngå horisontale sprekker, kan det ikke være 0 eller 6. Følgelig er det 2 eller 4. Vi går nå til neste horisontale linje på brettet. Hvor mange stående brikker kan det være som hviler på denne linjen? Det må igjen være et like antall, og siden 0 fører til en horisontal sprekk, må det igjen være 2 eller 4 (6 er det ikke plass til). Slik kan vi fortsette oppover, og vi ser at det på hver av de fem nederste linjene på brettet må hvile 2 eller 4 stående brikker om vi skal unngå horisontale sprekker. Ialt er det derfor minst 2 ganger 5 = 10 stående brikker. Gjør vi et tilsvarende argument med liggende brikker, ser vi at vi trenger minst 10 av dem for å unngå vertikale sprekker. Ialt trenger vi derfor 20 dominobrikker, og det er umulig siden det bare finnes 18.

Oppdatert 27/9-99 av Tom Lindstrøm