Göm meny

Septemberproblemen 2004

1. För att numrera sidorna i en 11-sidig bok från 1 till 11 går det åt 13 siffror. Finns det någon bok för vilken det går åt 2004 siffror till numreringen?

2. På ett schackbräde (8x8 rutor) sprids en "infektion". En ruta blir infekterad om den har minst två infekterade angränsande rutor (med angränsande menas här att rutorna ska ha en gemensam sida, inte bara ett gemensamt hörn). En infekterad ruta förblir alltid infekterad. Hur många rutor måste minst vara infekterade från början, om till slut alla rutor blir infekterade?

Lösningar

1. För att numrera en 99-sidig bok går det åt 9+2*90 = 189 siffror. (9 ensiffriga sidor och 90 tvåsiffriga.) Numreringen av en (99+k)-sidig bok kräver alltså 189+3k siffror, så länge den har mindre än tusen sidor. Ekvationen 189+3k = 2004 har en lösning, k = 605. Det går alltså åt exakt 2004 siffror för att numrera en bok med 99+605 = 704 sidor. Det finns säkert många böcker med 704 sidor; en sådan är den ryska översättningen av Donald E. Knuths bok Concrete Mathematics.

/Pontus

2. Om de 8 rutorna längs en diagonal är infekterade från början, kommer alla rutor så småningom att bli infekterade. Vi ska bevisa att minst 8 rutor måste vara infekterade från början för att alla rutor ska bli infekterade. Vi observerar att omkretsen av de infekterade rutorna aldrig kan öka när en ny ruta blir infekterad. Med omkretsen menar vi antalet linjesegment som antingen bildar gräns mellan en infekterad och en oinfekterad ruta, eller som ligger längs kanten av brädet och begränsar en infekterad ruta. När en ny ruta infekteras kommer minst två linjesegment som tidigare hörde till omkretsen att hamna i det inre av det infekterade området, och högst två nya linjesegment kommer att hamna längs omkretsen. Om alla rutor till slut ska bli infekterade, måste därför de infekterade rutorna redan från början ha en omkrets på minst 32. Eftersom varje ruta bara har fyra sidor, måste minst 8 rutor vara infekterade från början.

/Johan


Sidansvarig: jana.bjorn@liu.se
Senast uppdaterad: 2019-12-03