Bräde
[kkratings]
Ett bräde är indelad i 4×4 rutor. Du får såga längs med de små rutdiagonalerna (det går bra att såga i båda diagonalerna på en vissa ruta). Hur många små diagonaler kan du som mest såga utan att brädet faller isär i bitar?
Nio stycken, till exempel så här:
Bevis och generalisering (inskickat av Skägget):
Vi betraktar brädan som några noder i ett 5×5 rutnät, där noderna är punkten vi kan såga till/från, och där alla de yttersta noderna är anslutna. Brädan faller isär om några sågningar bildar en cykel i grafen (ett tillräckligt men inte nödvändigt vilkor).
Vi betraktar nu enbart de innersta noderna, minus mittpunkten som vi tills vidare tänker bortse ifrån. Om
någon av dessa noder är anslutna till någon av kantnoderna på mer än ett sätt så faller brädan sönder, men vi kan såga på ett sätt så att de alla är anslutna till kanten och inte till varandra (se bild).
Vi konstaterar nu att varje ny sågning (från ett tillstånd där brädan sitter ihop) innebär att två icke-anslutna noder
ansluts, vilket innebär att bara en av dem får anslutas till kanten, ty annars får vi en cykel. Med andra ord innebär varje ny sågning att en potentiell anslutning till kanten går förlorad.
Men hur var det med mittpunkten? Den kan vi också såga till/från, men efter att vi sågat en gång, gäller samma princip
som ovan, att varje ny sågning ansluter två noder och därför eliminerar en potentiell sågning mot kanten.
Alltså, vi har 8 potentiella sågningar, och varje ny sågning (bortsett från en i mitten) innebär att en sådan potentiell sågning elimineras, så det maximala antalet gånger vi kan såga är 9, och ett exempel är som i bilden, fast med en extra sågning i mitten.
Denna lösning kan enkelt utvidgas till det generella fallet med brädor av godtycklig storlek. Varje nod utom de på utkanten har alltid en potentiell sågning utåt i brädan, och varje annat sågtag eliminerar en sådan potentiell sågning. Så alla noder utom de på kanten bidrar med en möjlig sågning, och därmed gäller att vi kan göra (n-2) x (m-2) sågningar i en n x m-bräda (där n och m alltså är antalet noder i grafen, inte rutor i brädet).