Hur enkel matematik flyttar nålen | Quanta Magazine

Föreställ dig att du rullar nerför gatan i en förarlös bil när du ser ett problem framför dig. En leveranschaufför från Amazon fick sin skåpbil halvvägs förbi en dubbelparkerad UPS-lastbil innan de insåg att de inte kunde ta sig igenom. Nu har de fastnat. Och så är du.

Gatan är för smal för att dra av en U-ey, så din AI-förbättrade bil initierar en trepunktssväng. Först tar bilen en kurvig väg mot en trottoarkant. Väl där styr den åt andra hållet och backar upp till motsatt trottoarkant. Sedan vrider den tillbaka ratten i riktning mot den första kurva, kör framåt och bort från hindret.

Denna enkla geometriska algoritm för att göra mellansvängar kan hjälpa dig att ta dig runt i trånga situationer. (Om du någonsin har parkerat parallellt, vet du vad den här vickningen fram och tillbaka kan göra för dig.)

Det finns ett roligt matematiskt problem här om hur mycket utrymme du behöver för att vända din bil, och matematiker har arbetat på en idealiserad version av den i över 100 år. Det började 1917 när den japanske matematikern Sōichi Kakeya utgjorde ett problem som låter lite som vår trafikstockning. Anta att du har en oändligt tunn nål med längd 1. Vilken yta har det minsta området där du kan vända nålen 180 grader och återställa den till sin ursprungliga position? Detta är känt som Kakeyas nålproblem, och matematiker studerar fortfarande varianter av det. Låt oss ta en titt på den enkla geometrin som gör Kakeyas nålproblem så intressant och överraskande.

Liksom många matematiska problem innefattar detta några förenklade antaganden som gör det mindre realistiskt men mer hanterbart. Till exempel spelar längden och bredden på en bil roll när du kör, men vi antar att vår nål har längd 1 och bredd noll. (Detta betyder att själva nålen har en area på noll, vilket spelar en viktig roll för att vi ska kunna lösa problemet.) Vi antar också att nålen, till skillnad från en bil, kan svänga runt sin främre ände, sin bakre ände , eller någon punkt däremellan.

Målet är att hitta den minsta regionen som gör att nålen kan vridas 180 grader. Att hitta den minsta sak som uppfyller en viss uppsättning villkor kan vara utmanande, men ett bra sätt att börja är att leta efter allt som uppfyller dessa villkor och se vad du kan lära dig på vägen. Ett enkelt svar är till exempel att bara rotera nålen 180 grader runt dess ändpunkt och sedan skjuta den uppåt igen. Detta återställer nålen till sin ursprungliga position, men den pekar nu i motsatt riktning, vilket Kakeyas nålproblem kräver.

Området som krävs för svängen är en halvcirkel med radie 1, som har en area på $latex A = frac{1}{2} pi r^2 = frac{1}{2} pi (1)^2 = frac{ 1}{2} pi = frac{pi}{2}$. Så vi har hittat en region som fungerar.

Vi kan bli bättre genom att dra fördel av vår magiska matematiska nåls förmåga att rotera runt vilken punkt som helst. Istället för att rotera den runt dess ändpunkt, låt oss rotera den runt dess mittpunkt.

Du kan kalla detta för Kakeyas kompass: Vår nål börjar peka norrut, men efter rotation är den på samma plats men pekar söderut. Detta område är en cirkel med radien $latex frac{1}{2}$, så dess area är $latex A=pi r^2 = pi (frac{1}{2})^2 = pi frac{1}{ 4} =frac{pi}{4}$. Det här är hälften av vår första region, så vi gör framsteg.

Vart ska du härnäst? Vi skulle kunna hämta inspiration från vårt förarlösa bildilemma och överväga att använda något som en trepunktsväng för nålen. Detta fungerar faktiskt ganska bra.

Regionen som svepas ut av nålen med denna teknik kallas deltoideus, och den uppfyller också Kakeyas krav. Att beräkna dess area kräver mer än den elementära geometrin vi diskuterar här (kunskap om parametriska kurvor hjälper), men det visar sig att arean för just denna deltoidea - den som svepas ut av ett linjesegment med längd 1 - är exakt $latex frac{pi}{8}$. Nu har vi en ännu mindre region där vi kan vända Kakeyas nål, och du kan bli förlåten för att du tror att det här är det bästa vi kan göra. Kakeya själv trodde att det kunde vara det.

Men detta nålproblem tog en stor vändning när den ryske matematikern Abram Besicovitch upptäckte att du kan göra oändligt mycket bättre. Han kom på en procedur för att skära bort onödiga delar av regionen tills den var så liten som han ville.

Processen är teknisk och komplicerad, men en strategi baserad på Besicovitchs idé bygger på två enkla idéer. Tänk först på den räta triangeln nedan, med en höjd på 1 och en bas på 2.

För tillfället kommer vi att glömma att vända nålen helt och hållet och bara fokusera på ett enkelt faktum: Om vi ​​placerar en nål med längd 1 i den översta vertexen är triangeln tillräckligt stor för att tillåta nålen att rotera hela 90 grader från ena sidan till den andra.

Eftersom arean av triangeln är $latex A=frac{1}{2}bh$, har denna triangel arean $latex A=frac{1}{2} gånger 2 gånger 1 = 1$.

Nu, här är den första viktiga idén: Vi kan minska områdets yta samtidigt som vi behåller 90-gradersrotationen. Strategin är enkel: Vi skär triangeln i mitten och trycker sedan ihop de två halvorna.

Arean av denna nya figur måste vara mindre än originalet eftersom delar av triangeln nu överlappar varandra. Faktum är att det är lätt att beräkna arean på figuren: den är bara tre fjärdedelar av kvadraten på sida 1, så arean är $latex A = frac{3}{4}$, vilket är mindre än arean av triangel vi började med.

Och vi kan fortfarande peka nålen i alla samma riktningar som tidigare. Det finns bara ett problem: den ursprungliga vinkeln har delats upp i två delar, så dessa riktningar är nu uppdelade i två separata regioner.

Om nålen är på vänster sida av den nya regionen kan vi rotera den 45 grader mellan syd och sydost, och om den är till höger kan vi rotera den 45 grader mellan syd och sydväst, men eftersom de två delarna är åtskilda , det verkar inte som om vi kan rotera den hela 90 grader som vi kunde tidigare.

Det är här den andra viktiga idén kommer in. Det finns ett lömskt sätt att få nålen från ena sidan till den andra som inte kräver mycket yta. I schack kanske du vet att riddaren rör sig i en L-form. Nåväl, vår nål kommer att röra sig i en N-form.

Så här går det till. Först glider nålen upp på ena sidan av N. Sedan roterar den för att peka längs diagonalen och glider nedåt. Sedan roterar den igen och avslutar sin resa genom att glida upp på andra sidan av N.

Till en början kanske det här N-formade draget inte ser så mycket ut, men det gör något väldigt användbart. Det låter nålen "hoppa" från en parallell linje till en annan, vilket hjälper oss att få vår nål från en region till en annan. Ännu viktigare, det gör det utan att kräva mycket yta. Faktum är att du kan få det att kräva så lite yta som du vill. Här är varför.

Kom ihåg att vår nål har noll bredd. Så varje linje som nålen rör sig längs, framåt eller bakåt, kommer att ha noll area. Detta innebär att området som krävs för att flytta nålen uppåt, nedåt eller diagonalt längs N-formen kommer att bestå av bitar med noll area.

Det lämnar bara rotationerna vid hörnen av N-formen.

Dessa rörelser kräver yta. Du kan se en liten sektor av en cirkel i varje hörn. Men här är den lömska delen: Du kan göra dessa regioner mindre genom att förlänga N.

Formeln för arean av en sektor av en cirkel är $latex A = frac{theta}{360} pi r^2$, där $latex theta$ är måttet på sektorns vinkel i grader. Oavsett hur högt N är, kommer sektorns radie alltid att vara 1: Det är nålens längd. Men när N blir högre, krymper vinkeln, vilket kommer att minska sektorns yta. Således kan du göra tilläggsytan så liten som du vill genom att sträcka ut N så mycket du behöver.

Kom ihåg att vi kunde minska arean av vårt triangulära område genom att dela det i två och få bitarna att överlappa varandra. Problemet var att detta delade upp 90-gradersvinkeln i två separata delar, vilket hindrade oss från att rotera nålen hela 90 grader. Nu kan vi lösa det problemet genom att slå på en lämplig N-form för att säkerställa att nålen har en väg från ena sidan till den andra.

I denna uppdaterade region kan nålen fortfarande rotera hela 90 grader som tidigare, det sker just nu i två steg. Först vänder nålen sig 45 grader och är i linje med den vertikala kanten till vänster. Därefter rör den sig längs N-formen för att komma till andra sidan. När den väl är där är det fritt fram att vända de andra 45 graderna.

Detta flyttar nålen 90 grader och för att hålla den vridande lägger du bara till roterade kopior av området.

Med tillägget av lämpliga N-former kan nålen hoppa från en triangulär halvö till nästa och vända sig själv bit för bit tills den kommer hela vägen runt, precis som en bil som utför en trepunktssväng.

Det finns mer djävulsk matematik i detaljerna, men dessa två idéer – att vi kontinuerligt kan minska den ursprungliga regionens yta genom att skära upp den och flytta runt den samtidigt som vi ser till att vi kan ta oss från bit till bit med hjälp av de godtyckligt små N-formerna – hjälper oss flytta nålen i en ständigt krympande region som i slutändan kan bli så liten som du vill.

Ett mer standardiserat tillvägagångssätt för att bygga den här typen av region börjar med liksidiga trianglar och använder "Perron-träd", som är smarta sätt att skära upp trianglar och sträcka och skjuta ihop bitarna igen. Resultatet är ganska fantastiskt.

Nyligen har matematiker gjort framsteg på nya varianter av detta gamla problem, satta i högre dimensioner och med olika föreställningar om storlek. Vi kommer förmodligen aldrig att se en AI-driven bil spåra en Kakeya-nålsspets, men vi kan fortfarande uppskatta skönheten och enkelheten i dess nästan ingenting.

övningar

1. Vilken yta har den minsta liksidiga triangeln som fungerar som en Kakeya-nålssats?

2. Du kan göra det lite bättre än den liksidiga triangeln i övning 1 genom att använda en "Reuleaux-triangel", en region som bildas av tre överlappande cirkulära sektorer. Vilken yta har den minsta Reuleaux-triangeln som fungerar?