Göm meny

Septemberproblemen 2003

1. I en restaurang behövs 9 eller 10 servitörer varje kväll. Det är 33 servitörer som arbetar där och det visade sig att efter ett antal kvällar så har alla jobbat precis lika mycket. När kan det tidigast ha inträffat?

2. Funktionen x5 kan beräknas med 3 multiplikationer genom att man i tur och ordning beräknar x2=x*x, x4=x2*x2 och x5=x*x4. Hur många multiplikationer krävs för att beräkna x15, x77 respektive x128?

Lösningar

1. Alla ska ha jobbat lika många kvällar. Går det att ordna redan när de jobbat 1 kväll var? Nej, eftersom 9*4 > 33 och 10*3 < 33, går det inte. Efter tre nätter har inte alla arbetat, medan efter fyra kvällar måste några ha jobbat mer än en gång.

Däremot går det att fixa så att alla samtidigt har jobbat exakt två gånger och det sker efter sju kvällar, tre med nio servitörer och fyra med tio: 9*4+10*3 = 66 = 2 * 33.

Alltså är svaret en vecka.

/Erik

2. Med en multiplikation kan vi som mest fördubbla exponenten för x. Det betyder att exponenten 128=27 kräver minst 7 multiplikationer. Detta är också tillräckligt, eftersom om vi hela tiden multiplicerar den högsta potensen av x med sig själv får vi x2=x*x, x4=x2*x2, x8=x4*x4, ..., x128=x64*x64.

Exponenten 15 kan vi beräkna med 5 multiplikationer: x2=x*x, x3=x*x2, x6=x3*x3, x12=x6*x6, x15=x3*x12. Om det hade gått med 4 måste vi efter 3 steg ha en exponent som är minst 8. Enda sättet att få detta är att beräkna x2, x4 och x8 i de 3 första stegen, men sen är det omöjligt att få x15 i nästa steg. Alltså är 5 det minsta antalet multiplikationer som krävs för beräkning av x15.

Exponenten 77 kräver 8 multiplikationer: x2=x*x, x4=x2*x2, x8=x4*x4, x9=x*x8, x17=x8*x9, x34=x17*x17, x43=x9*x34, x77=x34*x43. För att inse att det inte räcker med 7, observerar vi först att i så fall måste vi efter 6 steg ha en exponent som är minst 39, och efter 5 steg en som är minst 20. Om den största exponenten efter 5 steg är högst 24 ligger den största exponenten efter 6 steg mellan 39 och 48. Eftersom 24+48<77<2*39 är det omöjligt att få exponenten 77 i det 7:e steget. Om å andra sidan den största exponenten efter 5 steg är större än 24, så måste vi i de 5 första stegen beräkna x2, x4, x8, x16 och x32. I det 6:e steget måste vi då beräkna x40, x48 eller x64, och det är enkelt att se att i inget av dessa fall kan vi beräkna x77 i nästa steg.

/Pontus


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