matematikk.net

Gitt et brett på 6 ganger 6 ruter og 18 dominobrikker (som hver dekker 2 ruter), kan man fylle brettet med brikkene på en måte så det ikke er mulig å trekke noen linje gjennom brettet som ikke skjærer noen brikker?

EDIT: Bare glem dette - misforsto spørsmålet.

Den skjønte jeg ikke. 6x6 ruter = 36 ruter, og 18 brikker*2ruter = 36 ruter. Hele brettet vil altså dekkes og det er vanskelig å trekke noe linje uten å skjære noen brikker da. Gidder du å utdype for oss trege?

Det er korrekt at hele brettet skal dekkes. Hvis man for eksempel lar alle brikkene være liggende, vil man kunne trekke 5 horisontale og 2 vertikale linjer gjennom brettet som ikke skjærer noen brikker.

Linjene det er spørsmål om er de som går langs skillelinjene mellom rutene, sant?

Karl_Erik skrev:Linjene det er spørsmål om er de som går langs skillelinjene mellom rutene, sant?

Det kan vi godt si, linjer av en annen type gjennom brettet skjærer jo nødvendigvis noen brikker.

Jeg tror ikke at det går ann. Ville det være et godt nok bevis hvis et dataprogram gikk igjennom alle mulige kombinasjoner og fant ut at det ikke gikk, eller må det bevises matematisk?

Klarer ikke formulere dette matematisk, men har en teori på at det ikke går, og hvorfor! : )

Uansett hvor du legger en brikke vil den krysse enten en vertikal eller en horisontal strek.

Streken deles opp i henholdsvis enten et oddetall resterende "overganger" (om du legger en brikke helt i kanten av rutenettet), eller i partall + oddetall.

Hvis du skal legge en overgang over alle de vertikale strekene vil det resultere i en slags overlapping, noe som fører til et partall resterende potensielle overganger sett fra oven, untatt i en eneste rad!

Det fører til at neste rad må spoleres for å få oddetallsraden til å gå opp!

La et felt i matrisa ha betegnelsen "S" dersom den er dekket av en stående brikke.

Anta at det er mulig. Da må vi ha fem stående brikker slik at alle horisontale linjer er blokkert. Da vil fordelingen av antall "S"-felt initielt være:

1
2
2
2
2
1

Må i tillegg ha like antall "S"-felt i hver rad. Derfor må det legges til et odde antall i første rad. Men da blir antall "S"-felt i andre rad odde. Fortsetter vi å legge til stående brikker på denne måten slik at alle rader til slutt får et like antall "S"-felt, må vi minst bruke 10 stående brikker.

P.g.a. symmetri mellom stående/liggende brikker må vi i tillegg bruke minst 10 liggende brikker. Totalt må vi bruke minst 20 brikker. Siden vi kun har 18 tilgjengelig har vi et paradoks. Konklusjonen er derfor at det ikke er mulig.

Jeg tror min løsning tilsvarer plutarco sin.

Anta at det går an. For hver horisontal og vertikal strek trenger vi minst én dominobrikke som må stå i veien. De røde brikkene på toppen bildet må altså tres vertikalt ned på rutenettet, og de røde til venstre må tres horisontalt inn på figuren.

Etter vi har tredd dem på, har vi i midlertidig et odde antall tomme ruter i den øverste rekken. Det betyr at vi trenger minst én til vertikal brikke i den øverste rekken. Den er farget blå. Tilsvarende trenger vi en blå på den nederste rekken, og de to ytterst til både venstre og høyre.

Nå har vi et odde antall tomme ruter i den nest øverste rekken. Denne må fylles inn med en ytterligere vertikal brikke. Dette kan enten gjøres ved å tre inn en brikke på samme sted som den blå, eller der brikken er tegnet grønn. Tilsvarende må gjøres på den nest nederste rekken, og de to nest ytterste vertikale rekkene.

Nå har vi brukt 18 brikker. Men hvis vi ser på de øverste horiontale rekkene så har én av dem et odde antall fylte ruter avhengig av hvordan vi plasserer de siste brikkene (på den grønne eller ved siden av den blå). Dette er en motsigelse ettersom det må være et partall antall fylte ruter hvis rutenettet skal være fylt.