Annons

Maxade diagonaler

Författare: 

I ett 8 x 8-rutnät dras diagonalerna i några av rutorna på att sådant sätt att två diagonaler aldrig har en gemensam punkt. Vilket är det största antal diagonaler som kan dras? Notera att det inte räcker med att konstruera en lämplig konfiguration av diagonaler, man ska också visa att det inte finns någon med större antal diagonaler.

Facit

Det är enkelt att konstruera ett exempel med 36 diagonaler. Vi ska visa att det inte är möjligt att ha fler än 36 diagonaler. Tänk att man placerar rutnätet i koordinatsystem så att nedre vänstra hörnet hamnar i punkten (0,0) och övre högra hörnet i punkten (8,8).

Färglägg alla 81 skärningspunkter i två färger: punkten (a,b) målas blå om a är jämnt, men gul om a är udda. Då får vi 45 blå punkter och 36 gula. Eftersom varje diagonal förbinder en blå punkt med en gul så kan det totala antalet diagonaler som uppfyller uppgiftens villkor inte vara större än 36.