Göm meny

November 2011

Enligt legenden fick schackets uppfinnare välja ett pris. Han valde att få ett risgryn på första schackrutan, två på andra, fyra på tredje, åtta på fjärde, osv. 2n-1 gryn på n-te rutan. Hur många rutor behövs för att få åtminstone 1000 gryn? Vilka rutor skall man välja för att få exakt 1000 gryn?
Om man istället lägger 1, 3, 9, 27, ..., 3n-1, ... gryn på varje ruta, kan summan på några rutor bli exakt 1000 gryn? Kan den bli exakt 2011 gryn?
För vilka heltal k > 1 kan man lägga kn-1 gryn på n-te rutan, n = 1, 2, ..., 64, och summan på några rutor blir exakt 2011?


Lösning

Antalet gryn på de första n rutorna är 1+21+...+2n-1 = 2n - 1. För att få åtminstone 1000 gryn behövs alltså 10 rutor, då 1010 - 1 = 2023 > 1000. Eftersom 1000 = 29+28+27+26+25+23, så skall man välja rutor 10, 9, 8, 7, 6 och 4 för att få exakt 1000 gryn.

Om vi istället lägger 3n-1 gryn på n-te rutan, så har vi 1000 = 729+243+27+1 = 36+35+33+30. Summan på 1:a, 4:e, 6:e och 7:e rutan blir alltså 1000.

Här har vi alltså skrivit 1000 i bas 3 som (2011)10 = (1101001)3. Vi gör likadant med (2011)10 = (2202111)3 och ser att 2011 kan inte skrivas som en summa av potenser av 3 med koefficienter endast 0 och 1. Vi kan alltså inte få summan på några rutor att vara exakt 2011 gryn i det här fallet. Låt oss se hur man kan få (2011)10 = (2202111)3. Vi vill skriva 2011 i bas 3 och behöver alltså veta rester vid division med potenser av 3. Vi delar upprepade gånger med 3:
2011 = 3 · 670 + 1
670 = 3 · 223 + 1
223 = 3 · 74 + 1
74 = 3 · 24 + 2
24 = 3 · 8 + 0
8 = 3 · 2 + 2
2 = 3 · 0 + 2.
Siffrorna för 2011 i basen 3 läser vi av i sista kolonnen.

Om vi lägger potenser av k på varje ruta, så vill vi kunna skriva 2011 i basen k med bara siffror 0 och 1. I den första divisionen med k skall vi alltså ha antingen 2011 = k · A + 0 eller 2011 = k · A + 1. I det första faller måste k dela 2011 och eftersom 2011 är ett primtal, så skall k = 1 eller 2011. Vi får 2011 gryn genom att lägga ett gryn på 2011 rutor eller genom att lägga 2011 gryn på 2:a rutan.

I fallet 2011 = k · A + 1 måste k dela 2010. Här skulle vi kunna ta alla delare till 2010 och studera hur 2011 ser ut i motsvarande bas, som ovan. En kortare lösning är så här: Som förut, så kan vi ha k=2010, i.e. gryn på 1:a och 2:a rutan. Om fler rutor skall få vara med, så måste 2011 > k2, alltså k < 45. Eftersom k också skall dela 2010 = 2 · 3 · 5 · 67, så återstår k = 2, 3, 5, 6, 10, 15 och 30.

Eftersom varje tal kan skrivas binärt med bara 0:or och 1:or, så går även k=2 bra: (2011)10 = (11111011011)2. Vi har redan sett att k=3 går inte och självklart går inte k=10 heller, då 2011 har andra siffror än 0 och 1.

För k=5 och k=6 har vi 2011 < k5, alltså kan vi använda högst 5 rutor på vilka det kan ligga högst 1+k+k2+k3+k4 = 781 eller 1555 gryn (men inte 2011). k=5 och k=6 går alltså inte. För k=15 och k=30 kan vi ha högst 3 rutor med högst 1+k+k2 = 241 eller 931 gryn (men inte 2011). k=15 och k=30 går inte heller.

Svaret är alltså att man kan ha k=1, 2, 2010 och 2011.



Sidansvarig: jana.bjorn@liu.se
Senast uppdaterad: 2015-01-27