Mattebloggen

Lösningar, som vi väljer – del 1

Den här matematiska sagan är skriven av Victor Ufnarovski och publiceras här med hans tillåtelse.

Vi måste välja. Vi måste fatta beslut. Vi gör det varje dag. Och beklagar ibland hela livet. . .

Men man måste veta att det finns några situationer, som har icke-triviala lösningar. Matematiker har upptäckt dem. Och ibland kan dessa lösningar hjälpa oss att välja våra lösningar.

Problemet med att dela

Två rövare delar ett byte. Det var så enkelt och trevligt att röva, men det är så svårt att dela! Varje rövare tror att han själv kan dela bytet mitt itu, men tror inte att hans kollega kan. Till slut sa den äldre rövaren:

”OK, jag har en idé. Får jag försöka dela bytet mitt itu?”

”Du kan inte!” ropade den yngre rövaren.

”Men vänta litet grann! Jag ska bara försöka” svarade den gamla rövaren och delade bytet. ”Så, jag har delat det och tror att dessa två delar är lika. Tror du också att de är lika?” ”Nej, det är ojämnt!”

”OK, vilken del är större?” frågade den gamla rövaren.

”Denna!” svarade den yngre utan att tveka.

”Ta den då! Är du nöjd?” ”Javisst, men är du nöjd? ” ”Utan tvivel! Jag är säker på att vi har jämna delar. Det var jag, som delade det!”

Så var båda två nöjda. Men nästa gång var de tre, som rövade. Nu behövde de dela bytet i tre delar, och det var mycket svårare nu. Hur skulle de göra?

Först försökte den gamla rövaren att använda samma idé.
Han delade bytet i tre (som han trodde) lika delar och föreslog dem andra att välja. Han hoppades att de andra skulle välja var sin del och han själv skulle ta den tredje så att alla skulle bli nöjda. Men de två rövarna valde samma del.

”OK”, sa han. ”Ni tror att denna är den bästa delen. Välj då den sämsta. Jag tar den och ni kan dela resten utan mig. ”

Det var en bra idé, men tyvärr valde de nu olika delar. Och ingen visste vad de skulle göra. De var rövare och de började att skjuta…

Polisen kom snart och de var nöjda att de lyckades undkomma. Men alla tre funderade på hur de kunde ha delat bytet?

Nästa gånger var de 10 som rövade. Det var underbart! Men nu behövde de dela bytet i 10 delar. Den äldsta rövaren berättade för de andra hur svårt detta problem var med bara 3 delar och föreslog:

”Jag tror att vi ska be en matematiker att lösa det här problemet. Jag är god vän med en av dem. ”

”Ska vi betala honom?” frågade de andra. ”Nej, han kan göra det gratis. Han tycker mycket om att lösa svåra problem. Och han blir nöjd om han skriver en matematisk artikel om det. ” ”Utan våra namn?” ”Utan.” ”Då ska vi försöka” beslutade rövarna.

Matematikern var mycket intresserad av detta problem.
Till slut hittade han en lösning.

”Ni är rövare”, sa han. ”Var och en av er är säker på att han (och bara han) vet hur mycket 1/10 av detta skräp är. ”

”Javisst!” svarade alla. ”OK då. Kan du”, han pekade på en rövare, ”mäta upp 1/10 del av detta?” Rövaren gjorde det.

”Du”, nu pekade matematikern på en annan rövare. ”Tror du att det där är större än 1/10?” ”Nej, det tror jag inte”, svarade han.

”Bra. Och du”, frågade han nästa rövare, ”tror du att det är större än 1/10? ” ”Ja, det tror jag.”

”OK, minska då det, gör 1/10! ”

Rövaren tog bort en del av godset. ”Nu är det verkligen 1/10 av bytet”, kommenterade han.

”Men ni”, frågade matematikern de två första rövarna, ”är ni säkra på att det inte är större än 1/10?” ”Vi är säkra på att det är mindre än 1/10.” ”OK då. Nu frågar jag nästa. Är denna nya del större än 1/10?”

Och på sådant sätt frågade han varje rövare och tvingade dem att minska delen, om de tyckte att den var större än 1/10.

”Finns det någon som tycker att det här är större än 1/10?” frågade matematikern när den sista rövaren var tillfrågad. ”Nej”, svarade rövarna. Alla, som hade tänkt att den var för stor hade redan minskat den.

”Bra. Vem var den sista som minskade delen? ” ”Jag”, svarade en av dem.

”När du gjorde det var du då säker på att det är exakt 1/10 av bytet.” ”Jag är säker på det nu också. Ingen har minskat det efter mig. ”

”Ta det då! Du är säker på att du har 1/10 av bytet och ingen tror att du har mer.” ”Är det sant!” ”Ja”, ropade rövarna: de började att förstå.

”OK. Men nu har vi ett litet enklare problem. Vi ska dela resten i 9 delar. Vi börjar på samma sätt. Du, gör 1/9 av . . . ”

Och så delade matematikern bytet. Alla var nöjda. De köpte en stor flaska av ett gott gammalt vin (rövarna är också människor!) och gjorde en fest.

Plötslig föreslog matematikern: ”Ska vi dela vinet också?” ”Nej, det tar för lång tid. Vi ska dricka kvickt!” ”Det ska jag göra snabbt!” ”Hur då?”

”Mycket enkelt. Jag själv dricker inte alkohol. Så vi ska dela vinet i tio delar. Är varje och en av oss säker på hur mycket 1/10 av denna aska blir?” ”Inget problem.”

”Så, jag börjar långsamt hälla upp i denna stora bägare. När någon av er ser att det är 1/10 måste han genast säga ”Stopp!” Går det bra?” ”Ja, det gör det”, svarade rövarna med förvåning: de hade aldrig druckit så konstigt.

Han började att hälla upp i bägaren. Den blev mer och mer full. Till slut skrek en av rövarna: ”Stopp! Det blir för mycket. Nu är det exakt 1/10 av askan.”

”Men de andra tror det inte?” frågade matematikern. ”Nej. De tror att det är mindre än en tionde del. De var tysta.” ”Bra. Ta denna skål. Det är din del! Och vi ska fortsätta på samma sätt”, och han började att hälla upp i en ny bägare.

Rövarna funderade litet gran. ”Genialt! Så enkelt” sa till slut den duktigaste av dem, ”Men varför kunde vi inte dela bytet på samma sätt?”

Vad tänker du om det, läsare?

Problem vecka 19

Uttrycket (3 poäng).
Man utvecklade uttrycket (x+y)^n med hjälp av binomialsatsen. Den andra termen i summan blev lika med 240, den tredje blev lika med 720 och den fjärde blev lika med 1080. Hitta x, y och n.

Ön (7 poäng).
a) På en platt cirkelformad ö finns 4 hamnar (i den ordningen): 1, 2, 3 och 4. Mellan dem finns vägar där det kan finnas korsningar, det vill säga punkter där vägarna möts, korsas eller grenas. På alla sträckor är trafiken enkelriktad, på så sätt att man aldrig kan komma tillbaka till en hamn eller korsning om man startar därifrån. Låt f_ij beteckna antalet vägar som går från hamn i till hamn j.
Visa olikheten f₁₄f₂₃≥f₁₃f₂₄
b)

Visa att om det finns 6 hamnar (1, 2, 3, 4, 5, 6 i den ordningen) så gäller

f₁₆f₂₅f₃₄+f₁₅f₂₄f₃₆+f₁₄f₂₆f₃₅≥f₁₆f₂₄f₃₅+f₁₅f₂₆f₃₄+f₁₄f₂₅f₃₆

Visa lösningar

Uttrycket (Toomas lösning, kompletterad):
Vi har alltså en utveckling av ett binom (x+y) upphöjt i ett tal n enligt binomialsatsen sådant att den andra termen är lika 240, den tredje 720 och den fjärde lika 1080.

Vi förnimmer oss att binomialsatsen kan skrivas

$(x+y)^n = {n \choose 0}x^n y^0 + {n \choose 1}x^{n-1}y^1 + {n \choose 2}x^{n-2}y^2 + \cdots + {n \choose n-1}x^1 y^{n-1} + {n \choose n}x^0 y^n$

Detta innebär att om vi ersätter den retoriska notationen i problemtexten med symbolisk algebra får ekvationssytemet

${n \choose 1}x^{n-1}y^1=240$

${n \choose 2}x^{n-2}y^2=720$

${n \choose 3}x^{n-3}y^3=1080$

som förstås kan förenklas till

$nx^{n-1}y=240$

$\frac{1}{2}(n^2-n)x^{n-2}y^2=720$

$\frac{1}{6}(n-2)(n-1)nx^{n-3}y^3=1080$

Dividera den andra ekvationen med den första, samt den tredje ekvationen med den andra:

$\frac{1}{2}(n-1)\frac{y}{x}=3\ \ \Rightarrow \ \ (n-1)y=6x$

$\frac{1}{3}(n-2)\frac{y}{x}=\frac{3}{2}\ \ \Rightarrow \ \ (n-2)y=\frac{9}{2}x$

Subtrahera den andra ekvationen från den första

$y=\frac{3}{2}x$

och gör en ersättning i en av ekvationerna för att få n:

$(n-1)\frac{3}{2}x=6x\ \ \Rightarrow \ \ n-1=4 \ \ \Rightarrow \ \ n=5$

Nu kan vi göra ersätta n med 5 i den första ursprungliga ekvationen:

$5x^4\frac{3}{2}x=240 \ \ \Rightarrow \ \ x^5=32 \ \ \Rightarrow \ \ x=2$

$y=\frac{3}{2}\cdot 2=3$

Den enda lösningen är alltså n=5, x=2 och y=3.

Ön (Skäggets lösning, något modifierad):

a) Vi noterar att f₁₃*f₂₄ kan ses som antalet sätt man kan gå från 1 till 3 och sedan från 2 till 4, och att f₁₄*f₂₃ är antalet sätt man kan gå från 1 till 4 och sedan från 2 till 3.

En väg från 1 till 3 delar vår ö i två delar, med 2 och 4 på olika sidor. Således måste en väg från 2 till 4 korsa varje väg från 1 till 3 vid minst en punkt.

Tag en godtycklig väg som går från 1 till 3 (kalla den A) och sedan magiskt fortsätter vid 2 och går till 4 (via en väg B). A och B måste korsa varann i någon punkt X (vi kan exempelvis välja den första korsningen på A).

Antag att vi börjar från 1 och följer A tills vi når X. Sedan fortsätter vi längs väg B tills vi når 4. Sedan hamnar vi på något magiskt vis i 2 och följer B tills vi når X, och följer sedan A till 3.

Vi ser att för varje sammansättning A och B får vi en väg från 1 till 4 och sedan 2 till 3. Detta ger upphov till en funktion som uppenbart är injektiv (två vägar måste ju ha identiska vägsegment såväl före som efter X för att ett vägskifte vid X ska ge samma resultat, och då är de samma väg).

Således har vi en injektiv funktion från mängden av vägar 1-3-2-4 (med magiskt hopp från 3 till 2) och mängden av vägar 1-4-2-3 (med magiskt hopp från 4 till 2). Dessas mängders storlekar är som vi noterat f₁₃*f₂₄ respektive f₁₄*f₂₃, och således har vi visat olikheten i fråga.

b)Vi ser att vänsterledet kan ses som unionen av alla vägar 1-6-2-5-3-4 och 1-5-2-4-3-6 och 1-4-2-6-3-5 (med magiska hopp), sådana vägar kallar vi udda. Högerledet kan ses unionen av alla vägar 1-6-2-4-3-5 och 1-5-2-6-3-4 och 1-4-2-5-3-6, sådana vägar kallar vi jämna. Om två hamnar med nummer 4, 5 eller 6 byter plats i en väg, byter vägen paritet.

Tag en väg 1-x-2-y-3-z, där {x,y,z} är en permutation av {4,5,6}. Om delsträckorna skär varandra någonstans, kalla skärningspunkten närmast 1 för M (det vill säga skärningspunkten som kommer först på sträckan 1-x om den sträckar korsar andra, annars skärningspunkten närmast 2 på sträckan 2-y). Byt plats på vägsluten efter punkten M, precis som i punkt a). (Om alla delsträckorna går genom M bestämmer vi en regel om att alltid byta plats på vägsluten av desträckorna 1-i och 2-j.)

Om man byter två stycken vägslut byter vägen paritet. På så sätt har vi bestämt en bijektion mellan udda och jämna vägar som har korsningar. Varje väg som inte har korsningar är dessutom en udda väg av typ 1-6-2-5-3-4. Därför finns det minst lika många udda vägar som jämna. Av det följer olikheten.

Prinsessan eller tigern? Dag 4 (den sista dagen)

Den här interaktiva berättelsen har skrivits av Raymond Smullyan och ingår i boken ”The Lady or the Tiger?” Översättningen till svenska är min egen.

Notera att ”eller” är matematiskt (”A eller B” är sant även ifall både A och B är sant), likaså ”och” (”A och B” är sant endast om båda är sanna, i alla andra fall är det falskt).

Gå till första kapitlet

Dag 4

“Hemskt!”, kungen var förbannad. “Vi lyckades inte lura någon alls, så gåtorna måste har varit alldeles för enkla. Nåväl, en fånge är kvar, han ska minsann få!”

Logiklabyrinten

Kungen höll alltid vad han lovade. Fången var tvungen att välja inte bland tre rum, utan bland hela nio! Dessutom förklarade kungen att en prinsessa satt i bara ett rum, alla de andra innehöll antigen en tiger eller ingenting alls. Utöver det tillade kungen att påståendet på skylten till prinsessans rum var en sanning, påståenden till tigrarnas rum var lögner, samt att påståenden till tomma rum kunde vara vad som helst.

Dessa var skyltarna:

I Prinssesan sitter i ett rum med ett udda nummer	II Det här rummet är tomt	III Påstående V är sant eller påstående VII är falskt
IV Påstående I är falskt	V Påstående II eller påstående IV är sant	VI Påstående III är falskt
VII Rum I har ingen prinsessa	VIII I det här rummet sitter en tiger och rum IX är tomt	IX I det här rummet sitter en tiger och påstående VI är falskt

Fången funderade en stund.
“Det här problemet går inte att lösa!”, utropade han plötsligt med ilska, “Det är inte rättvisst!”
“Jag vet det mycket väl”, skrattade kungen.
“Väldigt roligt!”, sade fången förargat, “Men berätta åtminstone en sak, om ni vill behålla hedern, är rum VIII tomt eller finns det någon i det?”
Kungen hade heder att svara på ifall rum VIII var tomt. Med hjälp av det kunde fången bestämma var prinsessan fanns.

Så var fanns prinsessan?

Visa svaret

Problem vecka 18

Cirkelkonstruktion (2 poäng).
Du har en passare, som du kan rita cirklar med (så länge du känner till cirkelns mittpunkt och dess radie) samt en ograderad linjal, som du inte kan mäta något med, men som du kan rita en linje med genom två valfria punkter.

Du har fått ett papper där en cirkel c är ritad (och dess mittpunkt är markerad) och där en punkt A utanför cirkeln är markerad.

Hur kan du med hjälp av dina verktyg rita en ny cirkel, som har A som mittpunkt och som precis tangerar den redan ritade cirkeln c? Bevisa att din konstruktion ger korrekt resultat.

Cosinussumman (5 poäng).
Visa att ifall summan av cosinusar på vinklarna hos en fyrhörning är lika med 0, så måste fyrhörningen antingen vara cyklisk, en parallellogram eller ett parallelltrapets.

Visa lösningar

Cirkelkonstruktion (Davids lösning):
Låt B vara mittpunkten i cirkeln c. Drag sträckan AB. Låt X vara punkten där AB skär c. Rita en cirkel med mittpunkt i A och som går genom X. Jag vill visa att denna cirkel tangerar c. De har ju en gemensam punkt X, så jag vill visa att de inte har någon annan gemensam punkt.

Antag att de har en annan gemensam punkt Y. Då finns det två sätt att gå från A till B: via X (vägens längd är |AX|+|XB|) eller via Y (vägens längd är |AY|+|YB|). AX och AY är radier i vår konstruerade cirkel, alltså |AX|=|AY|. XB och YB är radier i c, alltså |XB|=|YB|. Alltså |AX|+|XB|=|AY|+|YB|. Men när vi går via X följer vi en rät linje enligt vår konstruktion, så ingen annan väg från A till B kan vara lika kort. Vilket motsäger att vägen via Y är lika kort. En motsägelse som visar att vår cirkel och c har en och endast en gemensam punkt, alltså tangerar de varandra.

Cosinussumman (Skäggets lösning):
Vi börjar med att konstatera att ett parallellogram är ett specialfall av en parallelltrapets, så vi visar bara att en fyrhörning är antingen cyklisk eller en parallelltraptes om summan av cosinus av vinklarna är 0.

Låt oss kalla vinklarna i vår fyrhörning för A, B, C och D (med ordningen än så länge godtycklig).

Vi vet att summan av vinklarna i en fyrhörning är 360 grader, och vi kommer använda följande identitet för cosinus:

$cos X + cos Y = 2\ cos(\frac{X+Y}{2})\cdot cos(\frac{X-Y}{2})$

Vi antar nu att summan av cosinus av alla vinklar är noll, det vill säga:

$cos A + cos B + cos C + cos D = 0$

$\iff 2\ cos(\frac{A+B}{2})\cdot cos(\frac{A-B}{2})+2\ cos(\frac{C+D}{2})\cdot cos(\frac{C-D}{2})=0$

$\iff cos(\frac{A+B}{2})\cdot cos(\frac{A-B}{2})=-cos(\frac{C+D}{2})\cdot cos(\frac{C-D}{2})=0$

Vi vet att D = 360 – A – B – C, samt att cos (180 – X) = – cos X. Detta ger oss:

$cos(\frac{A+B}{2})\cdot cos(\frac{A-B}{2})=-cos(\frac{360-A-B}{2})\cdot cos(\frac{C-D}{2})$

$\iff cos(\frac{A+B}{2})\cdot cos(\frac{A-B}{2})=cos(\frac{A+B}{2})\cdot cos(\frac{C-D}{2})$

Lås oss anta att cos (A + B)/2 är skiljt från 0. Då får vi:

$cos(\frac{A-B}{2})=cos(\frac{C-D}{2})$

$\Rightarrow cos(A-B)=cos(C-D)$

$\Rightarrow A-B=\pm(C-D)$

Eftersom C och D är godtyckliga kan vi ignorera vårt +/- i högerledet, och vi får:

$A-B=C-D \iff A+D=B+C$

Vi får alltså att ifall cos (A + B)/2 är nollskiljt så kommer A,D och B,C vara par av supplementära vinklar.

Vi noterar att cos (A + B)/2 = 0 implicerar att (A + B)/2 = 90 eller 180, och alltså att A + B = 180 (ty A + B + C + D = 360, och alla vinklar är positiva, så A + B = 360 är ingen möjlighet).

Med andra ord, tar vi två godtyckliga vinklar i vår fyrhörning och kallar dem A och B, då gäller att A + B = 180 eller så är A + D = 180, där D är någon annan vinkel. Alltså är vi garanterade att vinklarna i vår fyrhörning är parvis supplementära.

Vi får två möjligheter, att intilliggande vinklarna är supplementära eller att motstående vinklar är det. Ifall de är intilliggande får vi att två sidor i vår figur är parallella, och vi har alltså en paralleltrapets. Och ifall motstående vinklar i en fyrhörning är supplementära, då är fyrhörningen cyklisk.

Sammanfattningsvis har vi alltså funnit att om summan av cosinus av alla vinklar är 0, då gäller att antingen så är varje vinkel supplementär till en intilliggande vinkel (och då är fyrhörningen en parallelltraptes) eller så är motstående vinklar supplementära (och där är fyrhörningen cyklisk), vilket skulle bevisas.

Problem vecka 17

Nötter (1 poäng).
I tre högar finns 22, 14 respektive 12 nötter. Du får göra tre förflyttningar, så att högarna får lika många nötter. Under en förflyttning får du flytta ett antal nötter från en hög till en annan, men antalet nötter man flyttar måste vara lika med antalet nötter i högen man flyttar till. Vilka förflyttningar ska du göra?

Äpplen (3 poäng). Några lådor innehåller sammanlagt 2000 äpplen. Du får antingen ta bort lådor eller ta bort äpplen från lådor. Visa att du kan med hjälp av sådana operationer få kvar lådor med samma antal äpplen i varje, så att det sammanlagt finns minst 100 äpplen kvar.

Visa lösningar

Nötter (Axels lösning):
Start:
22 14 12
flyttar från 22 till 14

8 28 12
flyttar från 28 till 12

8 16 24
flyttar från 24 till 8

16 16 16

Äpplen (Skäggets lösning):
Låt oss försöka hitta ett motexempel, alltså någon fördelning av äpplen i lådor så att det inte går.

Ifall vi har hundra lådor som inte är tomma, då tar vi bort alla andra lådor och sedan alla äpplen utom 1 i varje av dessa lådor. Då får vi 100 lådor med 1 äpple i varje och är klara.

Om någon låda har 100 eller fler äpplen, då tar vi bort alla andra lådor, och alla äpplen i denna låda utöver 100, och är då klara.

Ett eventuellt motexempel måste alltså vara en fördelning där ingen av fallen ovan inträffar. Antag att vi har en sådan fördelning. Betrakta då den låda som innehåller flest äpplen (eller en av dem, ifall det är fler). Den innehåller färre än 100 stycken, ty annars har vi ett av fallen ovan. Den låda som innehåller näst mest måste innehålla färre än 50 äpplen, ty annars har vi två lådor som båda har minst 50 äpplen, och då kan vi ta bort alla andra lådor och sedan ta bort tillräckligt många äpplen i den låda som har flest äpplen för att lådorna ska vara lika, och då är vi klara.

På samma sätt, den låda som innehåller tredje mest måste ha mindre än en tredjedel av 100 stycken äpplen, eftersom annars har vi tre lådor med minst 100/3 äpplen var. I allmänhet måste den n:te lådan i ordningen (sorterat efter antalet äpplen) innehålla mindre än 100/n äpplen (avrundat nedåt till närmaste heltal).

Efter 49 lådor måste vi alltså ha högst 1 äpple i varje kvarvarande låda, annars har vi 50 lådor med minst 2 äpple i varje.

Låt oss nu vara generösa och säga att de första 10 lådorna alla innehåller högst 100 äpplen snarare än 99, 40, 32, 24, …, 10. Låt sedan de nästa 40 lådorna vara uppåt begränsade av 10. Då har vi i de första 50 lådorna högst 10*100 + 40*10 = 1400 äpplen (egentligen väldigt mycket färre). Bland de kvarvarande lådorna, som alla innehåller ett äpple var ska vi ha sammanlagt 600 äpplen. Alltså har vi 600 lådor med ett äpple var, och således även 100 lådor med ett äpple var, och för det fallet har vi redan konstaterat att det finns en lösning.

Alltså, om vi försöker fördela våra äpplen på ett sådant sätt att inga n lådor innehåller 100/n äpplen vardera, då kommer vi garanterat ha 100 lådor som har minst 1 äpple var, och därför kan vi vara säkra på att vi har något av dessa fall, och för båda fallen kan vi uppnå önskat resultat med våra givna operationer, så inga motexempel finns.

Problem vecka 16

Hexagonen (1 poäng).
Fyll i rutorna i ”hexagonen” nedan med heltalen från 1 till 19, så att summan av talen i varje kolonn och i varje diagonal blir densamma. Varje tal får utnyttjas exakt en gång, och vissa tal är redan på sin plats:

Siffersumman (3 poäng). Hitta alla tal som är 12 gånger större än sin siffersumma.

Visa lösningar

Hexagonen (Thomas lösning):

Siffersumman (Toomas lösning):
Vi börjar med att göra en definition och att visa ett lemma och därefter bestämma alla tal med den givna egenskapen.

Definition: Låt högstagradsiffran mena den siffra vars tiopotensfaktor har högst grad multiplicerat med den givna tiopotensen och beteckna detta med a*10^n.

Lemma: Alla tal med 4 siffror eller fler är större än 12 gånger deras siffersumma.

Bevis:

Antag att talet har t siffror. För att maximera siffersumman maximerar vi varje ingående term. Vi kan då notera att var sådan högst kan vara 9, varav vi ser att den maximerade siffersumman fås av den tecknade produkten 9t. Siffersumman multiplicerat med 12 blir då 12*9t=108t.

Denna produkt blir alltid mindre än talet, ty det alltid blir mindre en högstagradsiffran, då t≥4. För att minimera värdet av högstagradssiffran sätter vi a=1 och får att högstagradssiffran är 10^n. Vi kan också se att n=t-1 och få utsagan 108t<10^(t-1) för t≥4. Detta kan inses av att för varje t≥4 ökar det vänstra uttrycket med en faktor av 108, då det högra ökar med en faktor av åtminstone 1000.

HSB.

Vi ser nu att talet antingen är en-, två eller tresiffrigt.

Om det är ensiffrigt och siffran är a, får vi ekvationen
12a=a, som har lösningen a=0.

Om talet är tvåsiffrigt och siffrorna är a och b, får vi ekvationen
12(a+b)=10a+b

och finner att

a=-(11b)/2.

Då a och b måste vara positiva har denna ekvation inga lösningar.

Om talet är tresiffrigt med siffrorna a, b och c, får vi ekvationen
12(a+b+c)=100a+10b+c

varav vi finner att

88a=2b+11c

Om a≥2 får vi

2b+11c≥88*2=176

För att maximera vänster led sätter vi b=c=9, och får

2b+11c=2*9+11*9=117≥176

vilket är en motsägelse. Alltså gäller att a<2.

Då a är hundratalssiffran måste a≠0, vilket med den föregående utsagan ger att a=1. Insatt i ekvationen blir detta

88=2b+11c.

Om vi gör några algebraiska omskrivningar får vi att

11(8-c)=2b.

Detta betyder att b är en multipel av 11. Vi har dock att 0≤b≤9, vari den enda multipeln av 11 är 0, vilket betyder att b=0. Sätter vi detta i ekvationen får vi

88=11c

vilket förstås ger

c=8

Det enda tresiffriga talen med den givna egenskapen är alltså 108.

Prinsessan eller tigern? Dag 3

Den här interaktiva berättelsen har skrivits av Raymond Smullyan och ingår i boken ”The Lady or the Tiger?” Översättningen till svenska är min egen.

Gå till första kapitlet

Dag 3

“Attans”, utropade kungen, “även denna gång kom alla fångar iväg! Jag tycker att vi ska ha tre rum istället för två imorgon. I ett av rummen sätter vi en prinsessa och de andra två ska ha tigrar. Får se hur våra genier klarar sig då!”
“Utmärkt idé, ers majestät!”, sade rådgivaren.
“Dina synpunkter är smickrande för mig, om än något ensidiga”, kungen ryckte på näsan.
“Utmärkt sagt, ers majestät!”, utropade rådgivaren.

Nionde prövningen

Tredje dagen genomförde kungen allt enligt planen. Fången fick välja mellan tre rum, där bara ett innehöll en prinsessa, som kungen berättade, och två andra hade tigrar.

På rummen satt följande skyltar:

I
I det här rummet sitter en tiger

II
I det här rummet sitter en prinsessa

III
En tiger sitter i rum II

I detta fall tillade kungen att inte mer än en av dessa påståenden är sant. Var är prinsessan?

Visa svaret

Tionde prövningen
Återigen satt man in i rummen bara en prinsessa och två tigrar. Nu förklarade kungen för fången att skylten på prinsessans rum talar sanning, medan minst en av de andra skyltarna är felaktig. Själva skyltarna såg ut så här:

I
En tiger sitter i rum II

II
En tiger sitter i det här rummet

III
En tiger sitter i rum I

Vad ska fången göra?

Visa svaret

Tre möjligheter
Denna prövning var ännu klurigare. Kungen förklarade för fången att ena rummet hade en prinsessa, annan hade en tiger och ett av rummen var tomt. Dessutom vet man att skylten på prinsessans rum är sann, skylten på tigerns rum är falsk och skylten på det tomma rummet kan både vara sann eller falsk. Dessa var skyltarna:

I
Rum III är tomt

II
Tigern sitter i rum I

III
Det här rummet är tomt

Fången hade sett prinsessan förut och skulle inte ha något emot att gifta sig med henne. Så även om det tomma rummet inte var ett dåligt alternativ, så ville han ändå gissa rätt på prinsessans rum.

Var finns prinsessan och i vilket rum sitter tigern? Om du kan svara på dessa frågor kan du lätt lista ut vilket rum som är tomt.

Visa svaret

Gå till fjärde kapitlet

Problem vecka 15

Papper (3 poäng).
Man tog ett rektangulärt papper och vikte ihop det så att ena hörnet hamnade i mitten på kortsidan (se bilden). Det visade sig att trianglarna I och II var kongruenta.

Hur lång var papprets långsida om kortsidan var 8 cm lång?

Brickor (7 poäng). En kvadrat med storlek 6×6 ska övertäckas med 12 brickor (utan hål och överlapp). Vissa brickor (k stycken) får vara vara ”hörn” bestående av tre rutor och resten (12-k brickor) måste vara tre rutor stora rektanglar.

För vilka k är uppdelningen möjlig?

Visa lösningar

Papper (Thomas lösning):
På grund av kongruensen är sidorna markerade x lika långa, och samma sak gäller för de markerade y, och z. Vi ser att höjden h = x + y + z och x = 8/2 = 4, och y + z = 8 eftersom kortsidorna hade längd 8, så att h = 4 + 8 = 12 cm.

Brickor (Skäggets lösning):
Med två hörn kan vi bilda en 2×3-rektangel, och vi kan bilda en likadan rektangel med två 1×3-rektanglar. Hela brädet går trivialt att fylla med 2×3-rektanglar, och således kan vi för jämna k bilda k/2 sådana rektanglar med bara hörn och låta resten vara 1×3-rektanglar. Således kan brädet fyllas för jämna k.

För udda k större än 3, betrakta Bild 1 som visar en täckning med 5 hörn, en 1×3-rektangel och tre 2×3-rektanglar. Genom att välja hur de sistnämnda rektanglarna byggs upp (antingen med två hörn eller två 1×3-rektanglar) kan vi alltså täcka brädet för k = 5, 7, 9 och 11.

För k = 1 kan vi utan inskränkning anta att hörnet är sådant att det passar in i det övre-vänstra hörnet på brädet. Låt oss då numrera rutorna som i Bild 2. Vårt hörn kommer inte kunna täcka en av varje siffra, men hur man än placerar ut 1×3-rektanglar på brädet täcker de exakt en av varje siffra. På slutet ska lika många av varje siffra ha täckts, men det är omöjligt, eftersom antalet av de siffror som täckts av hörnet alltid kommer vara fler. Alltså existerar ingen lösning för k = 1.

För k = 3, låt oss dela in hörnen i två kategorier: De som passar in i övre-vänstra och undre-högra hörnen och de som passar in i de övriga två hörnen. Antag att det finns en övertäckning, och att våra tre hörn inte alla är av samma kategori. Då finns det två ur den ena kategorin och en ur den andra. Vi kan utan inskränkning anta att det finns exakt en ur den första kategorin, och vidare utan inskränkning anta att den passar in i övre-vänstra hörnet. Med samma resonemang som för k = 1 får vi nu att detta hörn inte täcker alla tre siffror enligt vår numrering av brädet, medans alla hörn ur den andra kategorin, samt alla 1×3-rektanglar, täcker exakt en av varje. Således finns det ingen lösning för k = 3 om vi har hörn ur båda kategorier.

Så antag att det finns en lösning för k = 3 där alla tre hörn är av samma kategori. Vi vet att de tre hörnen måste täcka lika många av varje siffra enligt vår numrering, det vill säga tre av varje. Låt hörn av typ 1 vara sådana som passar in i övre-vänstra hörnet av brädet och de andra vara av typ 2. Hörn av typ 1 kan täcka punkter (1, 2, 2) eller (2, 3, 3) eller (3, 1, 1) medans hörn av typ 2 kan täcka (3, 2, 2) eller (1, 3, 3) eller (2, 1, 1). Vi kan väldigt lätt verifiera att ingen kombination som har något hörn ur båda kategorier kan täcka exakt tre av varje siffra, eftersom varje par med ett hörn av varje typ ger antingen fyra av någon siffra, inget av en siffra, eller två av varje siffra, och det finns inget hörn som kan utvidga detta till att täcka tre av varje siffra. Således måste varje hörn vara av samma typ om någon lösning finns. Vi kan utan inskränkning anta att de är av typ 1.

Vi visar nu med induktion att ingen rektangel på formen 6xN (sex rutor bred) kan täckas med exakt tre hörn av samma typ. Basfallet med en 6×1-rektangel är trivialt eftersom hörnen inte ens får plats. Antag nu att det är omöjligt för alla rektanglar upp till 6xN, så ska vi visa att det inte finns någon lösning för 6xN heller.

Det nedre-högra hörnet i en 6xN-rektangel måste uppenbart täckas av en rektangel och inget hörn. Vi kan utan inskränkning anta att den ligger horisontellt (annars kan vi spegla brädet så att den gör det, eftersom det hörn vi valt är symmetriskt längs den diagonalen).

Det finns nu tre möjliga fall:

1) Till vänster om vår utlagda rektangel har vi en till horisontell rektangel. Då har vi täckt hela understa raden och ska därmed fylla en (N-1)x6-rektangel med tre hörn av samma typ. Det har vi antagit är omöjligt.

2) Till vänster om vår utlagda rektangel har vi en vertikal rektangel. Då har vi ett utrymme till vänster om den rektangeln, av måtten 2×3, som uppenbart bara kan fyllas med två vertikala rektanglar. Då får vi tre vertikala rektanglar bredvid varandra. Antag nu att resten av brädet går att fylla.. Då existerar det nödvändigtvis även en lösning där vi istället för tre vertikala rektanglar har tre horisontella (de täcker ju samma 3×3-kvadrat). Men om vi bortser från den understa raden har vi då även en lösning för en (N-1)x6-rektangel, vilket vi antagit är omöjligt.

3) Till vänster om vår utlagda rektangel har vi ett hörn. Då har vi ett 2×2-utrymme till vänster om hörnet som måste fyllas på något vis. Det går uppenbart bara med två vertikala rektanglar. Nu har vi en trappa från höger till vänster, med trappsteg av längd 2 och höjd 1. På det understa trappsteget har vi ett 2×1-uttrymme som bara kan fyllas med två vertikala rektanglar. Detta lämnar ett liknande utrymme på mittentrappsteget som även det bara kan fyllas med två vertikala rektanglar. Slutligen måste vi även placera två vertikala rektanglar i det lediga 2×2-utrymmet som bildas på översta trappsteget. Nu har vi en likadan trappa som tidigare, fast tre rutor högre upp. Om resten går att fylla med två rektanglar, då skulle vi kunnat flytta ner den resterande biten tre steg och fyllt en (N-3)x6-rektangel. Men det är ju omöjligt från induktionsantagandet.

Våra tre möjliga fall visade sig samtliga vara omöjliga, och alltså existerar det ingen lösning för k = 3. Sammanfattningsvis har vi alltså hittat lösningar för alla k utom 1 och 3, och för dessa existerar det inga lösningar.

Tangent

När jag säger ”tangentlinje” tänker du kanske på någon av dessa bilder:

En tangentlinje nuddar precis en kurva i en viss punkt. Ofta har jag tänkt att en tangent aldrig är en sekant, det vill säga att tangenten aldrig kan skära kurvan.

Men vad är då detta för något?

Nu skär ju uppenbarligen den röda linjen kurvan. Det går inte att rita en linje som precis nuddar kurvan i origo, utan att det blir skärning!

Det förklaras med att definitionen på en tangent baserar sig på sekanter, det vill säga vanliga linjer som skär kurvan i några punkter, minst två:

Tangent

En tangent till en kurva i en punkt A är vad sekanterna genom A närmar sig mot, då en annan av sekantens skärningspunkter med kurvan (punkten B) närmar sig A.

Därför blir tangenten i origo till grafen för $y=x^3$ horisontell och vi har en så kallad terasspunkt i origo.

Tangenter till cirklar är speciella: de är vinkelräta mot radien, som ritas från cirkelns mittpunkt till tangeringspunkten!

Lutningen på tangenten är viktig, för att den ger oss derivatan i den punkten. Låt oss kolla på lutningen på radien först. För enkelhets skull antag att det är enhetcirkeln vi tittar på.

Lutningen är lika med förändringen i y-led delat på förändringen i x-led. Det blir $\frac{sin x}{cos x}$ , det vill säga $tan x$ .

Tangentens lutning måste då vara $\frac{-1}{tan x}$ eftersom tangenten är vinkelrät mot radien. Undrar om det är härifrån namnet ”tangens” kommer ifrån?

Problem vecka 14

Fången (2 poäng).
Kungen tänker på tre stycken tvåsiffriga tal: a, b och c. Fången måste hitta på tre tal själv och säga dem högt: X, Y och Z. Därefter säger kungen högt summan aX+bY+cZ. Då måste fången gissa rätt på vilka tre tal kungen tänkte från början, annars blir han avrättad.

Vilka tal X, Y och Z ska fången säga för att behålla livet?

Speciellt tal (5 poäng). Existerar det ett naturligt tal, som är större än 101000, som inte är delbart med 10 och som har åtminstone två olika siffror, och om man byter plats på dessa två siffror så förändrar inte talet mängden av sina primtalsdelare?

Visa lösningar

Fången (Lisas lösning):
Jag skulle rekommendera honom att välja talen X=10000, Y=100 och Z=1. Då kommer fången kunna räkna ut talen a, b och c genom att bara dela upp siffrorna i resultatet två och två. Antag t.ex. att summan aX+bY+cZ blir 235982. Då räknar fången lätt ut att a=23, b=59 och c=82.

Detta kan jämföras med vårt decimalsystem. Vi vet t.ex. att talet 512=5*100+1*10+2*1. Om talen a, b och c hade varit ensiffriga så hade fången kunnat välja talen 100, 10 och 1. Om dessa tal istället är tvåsiffriga måste vi låta talen X, Y och Z ha dubbelt så många nollor. På så sätt kommer inga siffror att adderas med annat än noll i multiplikationsalgoritmen och kommer alla vara skilda från varandra.

Speciellt tal (Skäggets lösning):
Låt oss finna ett naturligt tal som uppfyller de efterfrågade egenskaperna:

Betrakta talet 13 * 11…111 för någon följd av ettor. Det kommer vara på formen 144…4443.

Talet 31*11…111 för samma följd av ettor är lika med 344…44441, med samma antal fyror som ovan.

Vi observerar att det ena talet kan nås från det andra genom att byta plats på första och sista siffran. Från hur vi konstruerat talen vet vi att de har gemensamt alla primtalsdelare av 11…111. Om de, som vi vill, ska ha exakt samma primtalsdelare så måste både 13 och 31 dela 11…111, det vill säga att produkten av dem, 403, delar 11…111.

Så om vi lyckas visa att det finns någon sådan följd av ettor som delar 403, och som multiplicerat med 13 är större än 101000, då är vi klara.

Betrakta tal på formen 10^6x. Från Dirichlets lådprincip får vi att det garanterat finns två olika sådana tal som är lika modulo 403. Låt 10^6a och 10^6b vara ett sådant par av tal, där a > b. Differensen mellan dem är

10^6a – 10^6b = 99…900…0 = 9 * 11…1 * 10^6b

Eftersom 403 inte delar vare sig 9 eller 10^6b måste 403 dela 11…1. Antalet ettor är 6a-6b, alltså minst 6 stycken.

Alltså finns det en följd av ettor som är större eller lika med 111111 som är delbar med 403, och som därmed även är större än 101000. Därför har 13 gånger denna följd exakt samma primtalsdelare som 31 gånger den, och därmed har vi visat det vi ville.

I Sanning	II Lögn	III Lögn
IV Lögn	V Lögn	VI Sanning
VII Sanning	VIII Lögn	IX Lögn