Roliga mattegåtor – Sida 16

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.

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.

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.

Problem vecka 13

Kaniner (1 poäng).
En kaninmamma köpte 7 olika stora trummor och 7 olika stora trumpinnar-set åt sina 7 kaninbarn. Om en kanin ser att någon av syskonen har både mindre trumma och mindre trumpinnar, börjar den slå på trumman väldigt högt. Annars sitter kaninen tyst.

Vad är det största antalet kaniner som kan trumma högt?

Staket (3 poäng). I en liten stad finns 100 hus. Man får bara bygga slutna staket som omringar åtminstone ett hus. Olika staket får inte korsa varandra. Man får aldrig bygga flera staket som omsluter samma samling av hus.

Vilket är det största antalet staket som kan finnas i staden?

Visa lösningar

Kaniner (Toomas lösning):
Det optimala fallet är att alla kaniner trummor högt, de vill säga sju stycken. Den med minst trumma och trumpinne kan dock inte trumma högt, enligt villkoren. Nästkommande fall är då att sex kaniner trummar högt. Vi ser att detta går att göra, genom att ge den minsta trumman och de minsta trumpinnarna till en kanin, de näst minsta trumman och de näst minsta trumpinnarna till en annan kanin, och på detta sätt fortsätta, tills alla har en trumma och ett par trumpinnar. Alla utom kaninen med den minsta utrustningen kommer då trumma högt.

Staket (Skäggets lösning):
Vi låter ett stakets storlek beteckna antalet hus det innesluter, och S(n) får beteckna det maximala antalet staket som kan byggas i en stad med n hus. I ett sådan staketuppsättning observerar vi att bland annat varje enskilt hus ett staket runt bara sig.

I en stad med n hus kan vi alltid bygga ett till hus precis bredvid något annat (det vill säga så att inget staket finns mellan dem). Vi kan då bygga ett staket runt enbart det nya huset och ett staket runt det nya huset och dess granne. Alltså är S(n+1) större eller lika med S(n)+2.

Antag att S(n+1) är större än S(n)+2. Betrakta då en stad med n+1 hus och en maximal staketuppsättning, och bortse från alla triviala staket av storlek 1. Vi väljer där ett staket av minimal storlek. Detta måste vara storlek 2, ty annars kan vi välja 2 hus innanför staketet och bygga ett nytt staket som innesluter dem. Vi river att av de 2 hus det innesluter. I och med detta måste vi riva de staket av storlek 1 som innesluter de båda husen var för sig, ty annars bryter vi mot staketreglerna att inget staket får vara tomt och att inga två staket får innehålla samma samling hus (vårt staket av storlek 2 blir ju nu ett staket av storlek 1). Alltså har vi en uppsättning staket i en stad med n hus som innehåller S(n+1) – 2 hus. Men eftersom S(n+1) antagits vara större än S(n)+2 innebär detta att vi har fler staket än S(n) i vår stad med n hus, vilket motsäger vår definition av S(n).

Alltså har vi likhet: S(n+1) = S(n)+2. En stad med ett enda hus kan bara ha ett staket, och således är S(1) = 1. Vi får alltså att S(n) = 1 + 2(n-1) = 2n – 1.

För 100 hus gäller alltså att maximalt 2*100 – 1 = 199 staket kan byggas i enlighet med de angivna reglerna.

Problem vecka 12

Syskon (1 poäng). I en familj finns sex barn. Fem av barnen är 2, 6, 8, 12 respektive 14 år äldre än det minsta barnet. Alla åldrarna i familjen är primtal. Hur gammalt är det minsta barnet?

Primtal

Ett primtal är ett positivt heltal som har exakt två delare: 1 och talet självt.

Till exempel är 2, 3, 5 och 7 primtal.

Men 1, 4, 6, 8 och 9 är inte primtal: 1 har endast en delare (1), 4 har tre delare (1, 2, 4), 6 har fyra delare (1, 2, 3, 6), 8 har fyra delare (1, 2, 4, 8) och 9 har tre delare (1, 3, 9).

Sannolikheter (3 poäng). Två vänner singlar slant: den första singlar 10 gånger och den andra singlar 11 gånger. Hur stor är sannolikheten att den andra vännen får klave fler gånger än den första vännen?

Visa lösningar

Problem vecka 11

Nu kommer de svåraste problemen hittills! Nästa vecka återkommer jag till normal svårighetsgrad.

Skicka in lösningsförslag genom att klicka på länken under uppgifterna senast måndagen den 28 mars. Glöm inte att kolla reglerna och aktuella poängställningen.

Punkter (3 poäng). Sätt ut så många punkter på ett papper som möjligt, på så sätt att ingen trippel av punkter ligger på en och samma linje, utan utgör hörn till en likbent triangel. Du behöver inte bevisa att det inte går att sätta ut fler punkter med samma egenskap.

Likbent triangel

En likbent triangel är en triangel med två lika stora vinklar. En ekvivalent definition är att det är en triangel som har två lika stora sidor.

Här är några exempel:
Likbenta trianglar
Notera att en liksidig triangel är också likbent.

Trasig våg (7 poäng). Du har 3^2k mynt som ser likadana ut, men bland dem finns ett falskt mynt som väger lite mindre än alla andra. Du har också tillgång till tre balansvågar (varje balansvåg har två skålar). Du vet att två vågar är i gott skick, men en är trasig och du vet inte vilken det är. Den trasiga vågen kan visa både jämvikt och ojämvikt åt ena eller andra hållet oberoende av vad du lägger på skålarna.

Hur bestämmer du vilket mynt som är falskt på 3k+1 vägningar?

Visa lösningar

Punkter (Arvids lösning):
Det maximala antalet punkter är 6 i form av en liksidig pentagon (femhörning) med en sjätte punkt mitt i centrum av pentagonen.

Trasig våg (Davids lösning): vi börjar med k=1, alltså 9 mynt och 4 vägningar. Jag ser det som välkänt (för matteintresserade) hur man hittar det falska myntet bland 3^n mynt på n vägningar med en fungerande våg. Observera att om två vågar påstår samma sak så måste påståendet vara sant. Om två vågar motsäger varandra måste en av dessa vara trasig, så den tredje vågen fungerar.

Lägg mynten i 3×3-formation. Väg första raden mot andra i våg 1. Väg första kolumnen mot andra i våg 2. Nu har vi ett misstänkt falskt mynt, i rad A kolumn B säger vi. Vi kan kalla myntet AB :) Vår tredje vägning blir (rad A men inte kolumn B) mot (kolumn B men inte rad A) i våg 3.

Om (rad A men inte kolumn B) visas som lättast: våg 2 säger att falska myntet finns i kolumn B men våg 3 säger att det inte finns i kolumn B. Motsägelsen visar att våg 1 fungerar, falska myntet finns alltså i rad A och med vår sista vägning kan vi hitta det falska myntet bland de tre kandidaterna.

Om (kolumn B men inte rad A) visas som lättast: på samma sätt vet vi att våg 2 fungerar och kan hitta det falska myntet med vår sista vägning.

Om jämvikt visas: det finns tre alternativ på vilka två vågar som fungerar. Om 1 och 2 fungerar är AB såklart falskt. Om 1 och 3 fungerar vet vi att det falska myntet finns i (rad A men inte (rad A men inte kolumn B)), en mängd bestående endast av AB. Om 2 och 3 fungerar får vi också AB som falskt. Alltså måste AB vara falskt och vi har endast använt tre vägningar.

Slutsats: antingen har vi hittat myntet på tre vägningar eller så har vi hittat en fungerande våg och kan använda den för att hitta myntet på den fjärde vägningen. Så för k=2 kan vi stapla mynten i högar om 9. Har vi hittat den falska högen efter tre vägningar så kan vi hitta det falska myntet på resterande 4 vägningar. Annars blir det lätt med hjälp av den fungerande vågen. Vi kan fortsätta med samma princip upp till godtyckligt höga värden på k.

För godtyckligt k=p, stapla i högar om 3^(2p-2). Om vi hittar den falska högen på tre vägningar har vi reducerat problemet till k=p-1. Annars har vi en fungerande våg, vi har 3p-2 vägningar kvar (vilket är större än 2p för p>2) och 3^(2p) mynt att väga = lätt.

Problem vecka 10

Skicka in lösningsförslag genom att klicka på länken under uppgifterna senast måndagen den 21 mars. Glöm inte att kolla reglerna och aktuella poängställningen.

Blommor (2 poäng). Längs med vägen mellan Kalles och Kajsas stugor växte blommor på rad: 15 prästkragar och 15 tussilago huller om buller. När Kajsa var på väg till Kalle, vattnade hon alla blommor i rad. Men efter den 10:e tussilagon tog vattnet slut och 10 blommor förblev ovattnade.

Nästa dag gick Kalle hem till Kajsa och plockade blommorna i rad. Efter den 6:e tussilagon tyckte han att buketten var lagom stor. Hur många blommor fick växa kvar längs med vägen?

Familjealbum (5 poäng). I ett familjealbum finns 10 foton. Varje foto föreställer tre personer: i mitten står en man, på hans vänstra sida har han sin son och på hans högra sida har han sin bror.

Alla männen som står i mitten är olika personer. Vilket är det minsta antalet olika människor som kan finnas på bilderna i albumet?

Visa lösningar

Blommor (Daniels lösning):
Eftersom det sammanlagt finns 30 blommor (15+15) och efter den 10:e tussilagon så finns det 10 blommor kvar på raden. Kvar finns där 5 tussilagos och 5 prästkragar på raden. När Kalle plockar den 6:e tussilagon från andra hållet så blir det alltså samma tussilago som den 10:e från Kajsas håll.

De tio blommorna som är kvar efter den 10:e från Kajsas håll + den tionde tussilagon blir 10+1=11 blommor i buketten och 30-11=19 blommor kvar på raden.

Familjealbum (Johans lösning): Vi kan anta att på varje bild så är sonen den äldste sonen, och brodern den ”ett steg yngre” brodern (där den ett steg yngre bordern till den yngsta brodern i en grupp är det äldsta syskonet). Vi kan också anta att för varje broderssyskonskara som är med så är alltid det äldsta syskonet med som fader på något foto.

Antag att det går att skapa ett sådant familjealbum med endast 15 personer. På varje foto förekommer 2 typer av ”relationer”, nämligen X är äldste sonen till Y och X är ett steg yngre brodern till Y. Mellan två personer X, Y så kan endast en av dessa relationer försigkomma. Totalt så har vi 20 relationer i bilden.

Vi ritar en graf med de 15 personerna som noder och vi bildar kanter där vi har en relation (vi kan anta att grafen är sammanhängande). Ifall vi inte ritar ut relationerna där den äldste brodern anses ett steg yngre än den yngste så har vi en riktad graf utan loopar, dvs ett träd. Ett träd med 15 noder har 14 kanter.

Vi behöver alltså 6 relationer till. Dessa kan nu bara komma från yngste->äldste brodersrelationer, och vi kan bara få en sådan från varje syskongrupp. Vi måste alltså ha minst 6 syskongrupper, där varje person i syskongruppen är avbildad som fader på något foto (pga relationsegenskapen). En sådan grupp måste bestå av minst 2 personer. Då har vi minst 12 personer som är fäder på något foto. Detta motsäger att vi har 10 foton.

Här är exempel på ett släktträd med 16 män:

Problem vecka 9

Skicka in lösningsförslag genom att klicka på länken under uppgifterna senast måndagen den 14 mars. Glöm inte att kolla reglerna och aktuella poängställningen.

Rebusen (1 poäng). Försök att läsa av ordet genom att använda nyckeln:
Rebus

Schackcirkeln (3 poäng). Det finns ett vanligt schackbräde med storleken 8×8. Hur stor radie har den största cirkeln man kan rita, som bara går igenom svarta rutor (det vill säga cirkelns rand finns aldrig i de vita rutornas inre)? Visa varför det inte går att hitta en större sådan cirkel.