AspergerForum

Här presenterar jag ett problem sisådär en gång i veckan. De kräver normalt inte att man kan speciellt mycket matte men de är kluriga.

Problem 1: Geometri - Många cirklar och en triangel.

Beskrivning: Inuti triangeln finns oändligt många cirklar. Den nedersta är störst och vi kallar den för c1 och har diametern 2 meter. Den näst nederst kallar vi c2 osv. c2 har hälften så stor diameter som c1 och c3 har hälften så stor diameter som c2 osv.

Fråga 1: Hur stor är cirklarnas totala omkrets?

Fråga 2: Hur stor är cirklarnas totala area?

Jag kommer ge ut ett bildillustrerat svar om ca. 1 vecka så om ni löser problemet så kan ni hålla lite på det så att fler får chansen att lösa det själva. Lycka till!

4*Pi meter skulle jag tro...

Det råkar inte vara så att du avslöjade lite för mycket info för att det skulle bli nåt klurigt problem?

Bara

Triangeln är 4 m hög och basen är kvadratroten ur 8

och inte haft med

Den nedersta är störst och vi kallar den för c1 och har diametern 2 meter. Den näst nederst kallar vi c2 osv. c2 har hälften så stor diameter som c1 och c3 har hälften så stor diameter som c2 osv.

skulle väl ha räckt för att lösa det?

Tror jag. Eller så är det här redan nu klurigare än vad jag ser det som...

Fråga 2 är lite roligare, eller egentligen bara jobbigare. Frågan är om det finns något enkelt och smart sätt att lösa den som jag har förbisett? Eller handlar det mest om att inse att uppgiften innehåller en massa villospår som är irrelevanta eller ointressanta?

Något slags ekvationssystem är sannolikt lösningen. Cirklar och trianglar är rätt givna hur de modelleras matematiskt. Hur dessa kopplas ihop är däremot lite svårare. Men det finns ju skärningspunkter..

Förutsatt figuren stämmer, så triangeln verkligen tangerar alla cirklarna utan att skära dem, så handlar det bara om serier. Att det är cirklar och en triangel är ointressant, förutom att cirklarna orsakar ett pi i svaret.

Arean = (4pi)/3 m^2 ?


Vit text nedan med hur jag tänkt:


Om man tänker sig att man kapar triangeln horisontellt mellan cirklarna så går det att "vika ned" övre delen så att det blir ett parallellogram där den nedvikta delen är en fjärdedel av hela parallellogramet. Basen på den övre triangeln blir halva basen på den stora triangeln så det är uppenbart att det blir en "fjärde tredjedel" man viker ned.

Det största cirkeln har arean PI längdenheter och som jag ser det så borde det vara uppenbart att arean på resten av cirkelarna då är 1/3 av den största. Alltså 4/3 PI areaenheter.

Det här är mer visualisering än matte från min sida men jag är ganska säker på att jag har rätt?

Jo, du kom nog på tricket med hur det var tänkt, Moggy. Ditt resonemang håller nog, även om man skulle vilja fylla på med lite mera detaljer i argumentationen. Svaret stämmer dessutom med vad jag räknade fram utgående från enbart serien av cirklar.

Här kommer lösningarna till problem 1.

I båda fallen kan man använda en s.k. geometrisk serie som säger att den oändliga summan av 1 + x + x² ... = 1/(1-x) , för 0 < x < 1. I fråga 1 ser man lätt att x=½ och i fråga två x=(1/2)²=1/4. Det ger svaren att omkretsen av cirklarna är 2•2π=4π och arean är π•4/3=4π/3. Den här metoden är iof lite tråkig eftersom den kräver matematiskt kunnande och inte är varken vacker eller kreativ så nu går vi över till de mer geometriska metoderna.

Fråga 1: Vi noterar att omkretsen av två cirklar med diametrarna x och y är πx + πy=π(x+y), alltså samma som en cirkel som precis innesluter båda cirklarna om de tangerar varandra. Således kan vi lösa problemet genom att rita en cirkel som precis innesluter alla cirklarna i triangeln och denna större cirkel har uppenbarligen omkretsen 4π.

Fråga 2: Det finns i alla fall 2 sätt att lösa denna. Areametoden som kräver att man beräknar (eller känner till triangelns bredd) och vikmetoden som Moggy använde. Båda metoderna går ut på att man noterar att varje cirkel befinner sig i en form som kallas parallellpiped (se figur 1) och att dessa är likformiga så cirklarna upptar lika stor del av arean i varje.



I areametoden använder vi detta för att beräkna hur stor del av arean av en parallellpiped som är täckt av cirkeln, vilket är det lika stor del som alla cirklarna täcker av triangeln. Vi beräknar den nedersta parallellpipedens area: Nedre sidan är 2√2 och den övre sidan är hälften då den når precis till halva triangelns höjd. Vi noterar att vi kan flytta en av sidotrianglarna till andra sidan (figur 2) och få en raktangel med samma höjd och bredden (2√2 + √2)/2 så arean blir 3√2 (eftersom höjden är 2). Hela triangelns area är (4•2√2)/2=4√2. Så alla cirklars area är 4/3 • nedersta cirkelns area, som är π. Vi får 4π/3.



Vikmetoden går ut på att man noterar att om man kapar av den nedersta parallellpipeden så är har den samma höjd som det som är kvar av triangeln. Vi viker ned den kvarvarande delen av triangeln (figur 3) och ser att om vi slår ihop sidotrianglarna så har dessa samma area som den nedvikta delen och den nedvikta delen upptar halva arean av rektangeln i mitten. Således är arean av hela triangeln 4/3 gånger arean av den nedersta parallellpipeden och via likformighet gäller samma sak för cirklarna så vi får svaret 4π/3.

Säg att man inte hade fått reda på hur stor nån av cirklarna var utan bara triangels bas och höjd som jag skriver om ovan. Och att man får reda på att cirklar är i traingeln på så sätt att dom är staplade på varann och är så stora som dom kan vara och därmed tangerar triangelns sidor. Som det är i figuren.

Hur skulle man göra för att komma fram till hur stor cirklarna är och hur dom förhåller sig till varann?

Funderade lite på det men kom inte speciellt långt. Tänkte nåt att man delar cirkeln i tre delar där den tangerar triangeln och så får man nya tänkta trianglar där sidan är lika med radien på cirkeln...men stopp där ungefär...

Om triangelns toppvinkel är 2v så får vi att cos²v=1-r²/(h-r)² (kommer fram till detta med hjälp av pytagoras sats och definitionen för sinus och cosinus). Så om vi vet v så kan vi räkna ut cos v och därmed 1-r²/(h-r)² så att vi får fram förhållandet mellan r och h. Om z=1-r²/(h-r)² så har vi y=1-z=r²/(h-r)², men vi vill få fram x=c₁/c₂. Exempel: y=1/16. r²/(h-r)²=1/16 ⇒ h-r=4r ⇒ h=5r ⇒ r/h=1/5. Vi löser med areametoden. första cirkeln upptar då (1+3/5)(2/5)/2=8/25 mot 1/2 av cirklarnas totala area så vi får multiplicera arean med 25/16. Första cirkelns area är π(2h/5)²=4h²π/25 så den totala arean för alla cirklar är h²π/4.

Hoppas detta duger som svar.

EDIT: r är radien för den första (nedersta/största) cirkeln, c₁, och h är höjden på triangeln.

Ja det här var ju inte snyggt... För det första räknade jag fel på arean i exemplet som är h²π/16 egentligen och dessutom är det uppenbart att sin(v)=r/(h-r). Se figuren.

Tack för förklaringarna! Kul att läsa.

Problem 2: Kombinatorik - Tornen i Hanoi

Beskrivning: Man ska flytta de röda klossarna till den tredje pinnen. Reglerna är att man endast får flytta en i taget och att man inte får lägga en större ovanpå en mindre men det finns inga restriktioner till vart man får flytta klossarna dvs. klossarna får flyttas till vilken annan pinne som helst. Det här kan verka vara ett enkelt problem men läs frågorna innan ni avgör den saken.

Fråga 1: Om man har 50 st klossar, hur många förflyttningar måste man då minst göra för att nå målet att flytta alla klossar till den högra pinnen?
b. Hitta den perfekta strategin för att flytta klossarna till önskad position.

Fråga 2: Om man k pinnar, hur många förflyttningar måste man då göra för att flytta de 50 klossarna?
b. Hitta den perfekta strategin för detta.

Fråga 2 var riktigt klurig att ens få grepp om....det var inte helt lätt att hitta nåt system i det.

Moggy skrev:Fråga 2 var riktigt klurig att ens få grepp om....det var inte helt lätt att hitta nåt system i det.

Jag ska nog lägga upp lösningar imorgon (eller möjligtvis på söndag) (idag är fortfarande fredag eftersom jag inte brutit sömnbarriären ännu) så en ledtråd till tvåan kan vara på sin plats.

Fråga 2 väntar jag spänt på att få se ett svar på. Såvitt jag vet är det fortfarande ett öppet problem för k > 3.

Kvasir skrev:Fråga 2 väntar jag spänt på att få se ett svar på. Såvitt jag vet är det fortfarande ett öppet problem för k > 3.

Det var ju rätt enkelt att lösa det manuellt med få antal plattor och pinnar?

Tänkte först att man kunde göra nåt i stil med ((2^x1)-1)-((2^x2)-1) där x2 kunde vara nåt med hur många fler pinnar än klossar. Men märkte att det inte gick att lösa det så enkelt.

Lösningsförslag på problem 2:

Fråga 1:
Säg att det vi behöver F(x) förflyttningar om vi har x klossar. Vi noterar först att för att flytta sista klossen så måste vi först flytta alla utom sista klossen till mitten pinnen. Det tar F(x-1) förflyttningar. Sedan flyttar vi sista klossen vilket ger ytterligare 1 förflyttning. Nu måste vi flytta alla på mitten pinnen till sista pinnen vilket tar F(x-1) förflyttningar så vi ser att F(x)=2F(x-1)+1. Det är lätt att se att F(1)=1 och vi kan också konstatera att F(x)=2^(x)-1. Den bästa strategin är att lätt att hitta genom att följa resonemanget i hur många förflyttningar man behöver men man måste se till så att man bygger tornen på rätt pinne. För 50 klossar får vi lösningen F(50)=2^(50)-1 vilket är ett tal i storleksordningen 10^15. Om man gjorde en förflyttning varje sekund skulle det ta ungefär 100000 generationer att bli färdig.

Fråga 2:
Vi noterar att precis som i fråga ett måste vi först lägga alla klossar utom den sista på pinnarna i mitten. Vi låter F(x,k)=[antal förflyttningar för x klossar på k pinnar]. Vi noterar (som i fråga 1) att F(x,k)=2(F(x_1,k)+F(x_2,k-1)+...+F(x_m,3))+1 eftersom vi måste bygga k-2 torn och för varje torn vi byggt upp så har vi en pinne mindre att bygga de övriga på. Vi noterar också att om k>x få är F(x,k)=2x-1. Läsaren kan bekräfta detta själv genom att lägga ut klossarna på en rad istället för på höjd. Om vi har x=k så börjar vi med att lägga ut de k-2 första klossarna på rad, en på varje pinne. Sedan flyttar vi den minsta (till den näst minsta exempelvis) och lägger ut den näst största. Vi kommer fram till att vi flyttar den största klossen 1 gång, den minsta 4 gånger och övriga 2 gånger. Med en kloss mer än ser vi att F(k,k)=F(k-1,k)+4. Vi tittar på specialfallet k=4 och konstaterar att F(1,4)=1, F(2,4)=3 och F(3,4)=5 men F(4,4)=4+F(3,4)=9 så vi lägger till 2 två gånger. Vi ser också att F(5,4)=4+F(4,4) och F(6,4)=4+F(5,4) men F(7,4)=8+F(6,4). Vi lägger alltså till 4 tre gånger och vi kommer lägga till 8 fyra gånger, 16 fem gånger osv. Att det är så kan vi se i pascals triangel:



Pascals triangel fungerar så att de två talen ovanför läggs ihop till talet under. Vi kan se att vi lägger till 2 två gånger och sedan kan vi bygga upp ett torn med höjd 3 och ett med höjd 2. Vi får F(6,4)=2(F(3,4)+F(2,3))+1=2(2*3-1+2*2-1)+1=2(5+3)+1=17. Om vi lägger till en kloss till får vi F(7,4)=2(F(3,4)+F(2,3)+4)+1=17+8. Tornet med höjd 3 motsvaras i pascals triangel av summan längs den röda diagonalen (4 då vi studerar 4 pinnar) alltså 1+2. Vi befinner oss då på den andra blå diagonalen men vi måste göra denna förflyttning 2 gånger. Likaså kan vi bygga upp ett torn med höjd två på de tre pinnar som är kvar vilket motsvarar 1+1 längs den första röda diagonalen (3 diagonalen) så att den också hamnar på den andra blå diagonalen. Om vi lägger till en kloss måste ett torn ner på den tredje blå diagonalen och när vi fyllt den tredje diagonalen måste vi ner på den fjärde osv. För fem pinnar eller mer kan man resonera på samma sätt och lägga ihop tal i pascals triangel. Man kan visa att det stämmer med matematisk induktion (som går ut på att man visar att man kan fortsätta ett påbörjat mönster) utifrån det vi har lärt oss om specialfallet med 4 pinnar. Man kan annars bara räkna ihop hur många förflyttningar som krävs och se att det stämmer med pascals triangel om man vill undvika ett induktionsbevis. Läsaren får själv räkna ut hur många förflyttningar det krävs om man har 50 klossar och k pinnar.

Om ni har frågor på detta så fråga på. Fråga 2 är ganska seriös matematik och jag har försökt förklara så pedagogiskt jag kan men det kanske inte är så lätt att följa i alla fall.

Du bevisar inte att din lösning på fråga 2 är optimal. Frame-Stewart-algoritmen förmodas ge en optimal lösning, men det är inte heller bevisat.

Både Wikipedia och Wolfram math hävdar att detta fortfarande är en öppen fråga. Jag har vid tidigare tillfällen sökt i litteraturen vad som är känt för fallet 4 pinnar och inte lyckats hitta något som tyder på att detta fall skulle vara löst.

Kvasir skrev:Du bevisar inte att din lösning på fråga 2 är optimal. Frame-Stewart-algoritmen förmodas ge en optimal lösning, men det är inte heller bevisat.

Både Wikipedia och Wolfram math hävdar att detta fortfarande är en öppen fråga. Jag har vid tidigare tillfällen sökt i litteraturen vad som är känt för fallet 4 pinnar och inte lyckats hitta något som tyder på att detta fall skulle vara löst.

Ok. Jag har kommit fram till Frame-Stewart algoritmen utan att känna till den verkar det som. Jag ska se om jag kan hitta ett sätt att bevisa att den stämmer. Intuitivt verkar det inte så svårt att bevisa. Jag ska kolla lite på problemet men får tills vidare inse att jag kanske förhastat mig. Ursäktar mig en smula för att ha lagt ut ett öppet problem i så fall.

Krake skrev:

Kvasir skrev:Du bevisar inte att din lösning på fråga 2 är optimal. Frame-Stewart-algoritmen förmodas ge en optimal lösning, men det är inte heller bevisat.

Både Wikipedia och Wolfram math hävdar att detta fortfarande är en öppen fråga. Jag har vid tidigare tillfällen sökt i litteraturen vad som är känt för fallet 4 pinnar och inte lyckats hitta något som tyder på att detta fall skulle vara löst.

Ok. Jag har kommit fram till Frame-Stewart algoritmen utan att känna till den verkar det som. Jag ska se om jag kan hitta ett sätt att bevisa att den stämmer. Intuitivt verkar det inte så svårt att bevisa. Jag ska kolla lite på problemet men får tills vidare inse att jag kanske förhastat mig. Ursäktar mig en smula för att ha lagt ut ett öppet problem i så fall.

Intuition är farligt i sådan här lägen. Det är väldigt lätt att tänka fel och tro att man bevisat något fast man inte har det. Just optimalitetsbevis kan vara väldigt knepiga dessutom.

Ledsen att jag inte lagt ut något problem denna vecka. Det får bli till nästa vecka istället.

Angående Problem 2 så finns faktiskt ett bevis på att Frame-Stewart algoritmen är optimal. Artikeln är från 3 december 2011 så den är ganska ny och bevisar det här på samma sätt som jag hade tänkt försöka bevisa det här på innan jag hittade den här artikeln. Jag kunde inte hitta några fel i den. Det bärande beviset är lemma 2 och följer precis den naturliga intuitionen. Det är lite synd att någon annan gjorde det här före mig bara eftersom jag bara var en vecka eller 2 från att bevisa samma sak... Problemet är fortfarande öppet för mer än 4 pinnar men det borde vara lätt att generalisera.

Beviset

Lite undrande om det alltid är v53, varje år.

Siffermässigt borde det väl bli 50*7 + 2*7 = 364 först och främst.

Men en extradag vanligtvis skall ju med. Och jag är då mest osäker på hur dom gör veckonumreringen?

(Halvmatematiskt.)