Jaha kan man tänka. Ännu en tråd av en nästan inaktiv medlem som skapar fler trådar än poster (om det nu skulle vara möjligt). Hur som helst så är detta fallet. Jag tänkte man skulle kunna diskutera rolig matte i den här tråden. Anledningen till dess tillkomst är att jag precis, dvs för en kvart sen, började fundera på ett geometriskt problem. Problemet beskrivs som följer:

1 Givet ett antal, k, punkter på något sätt, vilket som helst, utslängda i planet, kan man då hitta en ny punkt så att avståndet mellan den nya punkten och varje ursprunglig punkt är precis lika stort?

2 Svaret på 1 är generellt nej men hur många nya punkter behöver man då placera ut för att det minsta avståndet mellan någon av dessa nya och var och en av de ursprungliga är lika stort? Alltså om U är mängden av ursprungliga punkter och ett godtyckligt enskilt element i U kallas u och N är de nya punkterna och n är ett godtyckligt element i N, då vill vi att dist(u,N) = C för alla u och där C är en konstant. Givet att U består av k punkter, vad är då N(k)?

Jag tog mig friheten att lägga till en liten omröstning också.

"Jag mår plötsligt dåligt"

KrigarSjäl skrev:"Jag mår plötsligt dåligt"

Jag mår genast lite bättre.

Krake skrev:1 Givet ett antal, k, punkter på något sätt, vilket som helst, utslängda i planet, kan man då hitta en ny punkt så att avståndet mellan den nya punkten och varje ursprunglig punkt är precis lika stort?

Om alla k ligger i cirkel så fungerar origo oavsett hur många punkter k är.

Krake skrev:1 Givet ett antal, k, punkter på något sätt, vilket som helst, utslängda i planet, kan man då hitta en ny punkt så att avståndet mellan den nya punkten och varje ursprunglig punkt är precis lika stort?

Nix. Det är uppenbart att det inte går ifall man tänker sig en linjal som man ritar markeringar på. Man kan rita markeringarna så att några är närmare varandra än de andra.

2 Svaret på 1 är generellt nej men hur många nya punkter behöver man då placera ut för att det minsta avståndet mellan någon av dessa nya och var och en av de ursprungliga är lika stort?

Den här meningen är inte möjlig att förstå. Placerar man ut 1 ny punkt borde kriteriet uppfyllas eftersom det minsta avståndet är konstant?

Alltså om U är mängden av ursprungliga punkter och ett godtyckligt enskilt element i U kallas u och N är de nya punkterna och n är ett godtyckligt element i N, då vill vi att dist(u,N) = C för alla u och där C är en konstant. Givet att U består av k punkter, vad är då N(k)?

dist(u,N)? Om u är en punkt och N är en mängd kan det inte fungera. Det är som att fråga vad är avståndet mellan London och {Tokyo, Moskva, New York}.

En kärleksaffär.

Ingendera.

KrigarSjäl skrev:"Jag mår plötsligt dåligt"

Ha ha, akademikern(?) KrigarSjäl slår till igen!

Själv är jag fascinerad av matte och kan (då jag mår bra och inte är för trött) komma på problem som jag tycker är kul att lösa.

Björne skrev:dist(u,N)? Om u är en punkt och N är en mängd kan det inte fungera. Det är som att fråga vad är avståndet mellan London och {Tokyo, Moskva, New York}.

dist(u,N) är minsta avståndet mellan punkten u och mängden N. Vi vill hitta en mängd punkter, nämligen N, så att dist(u,N)=C för något C oavsett vilket u vi väljer.

Trist

Jag var inte dålig på matte ens i gymnasiet (jag var bra på allt utom idrott), men jag tyckte det var så himla tråkigt att jag bara blev trött på det hela. Gick samhäll, var ett par poäng från att få godkänt i B+C (jag läste dem parallellt), kunde gjort omprov men jag "orka, tar det till hösten" då hann jag glömma allt. Sattyg. Var så nära, varför gorde jag inte omprov? Jag skulle garanterat fixat det...

Praktiskt och bra.

Men samtidigt fascinerande, som expertkunskaper ofta är. Titta på BBC-dokumentären om mannen som löste "Fermat's Last Theorem". Det tog honom 7 år av arbete i hemlighet, och ha gjorde just inget annat under den tiden.

(Finns i två upplagor. Den med 4 avsnitt har bättre bild än den med 5. Samma annars.)

Mattenördar kan läsa mer på [WikiEng]Wiles' proof of Fermat's Last Theorem[/WikiEng].

Krake skrev:

Björne skrev:dist(u,N)? Om u är en punkt och N är en mängd kan det inte fungera. Det är som att fråga vad är avståndet mellan London och {Tokyo, Moskva, New York}.

dist(u,N) är minsta avståndet mellan punkten u och mängden N. Vi vill hitta en mängd punkter, nämligen N, så att dist(u,N)=C för något C oavsett vilket u vi väljer.

Då fattar jag (fast det var inte självklart för en novis som mig). Om man sätter N=U borde kravet uppfyllas? Har en känsla av att det räcker ifall N innehåller en färre punkt än U men jag har ingen aning om hur man ska visa det.

Det stämmer att N alltid är mindre än U om det finns minst 2 punkter i U. En förmodan är att man alltid klarar sig med hälften så många punkter i N som i U avrundat nedåt oavsett hur punkterna i U är placerade. Det är uppenbart om punkterna i U ligger på en rak linje eller i en cirkel. Det svåra med problemet är att lägger man till en punkt i U måsta man vanligtvis omplacera alla punkter i N också. Av den anledningen är induktionsbevis inte helt lätta i det här fallet.

<a href="http://en.wikipedia.org/wiki/Towers_of_hanoi">Tornen i Hanoi</a> är ett känt problem. Det är ganska lätt att hitta lösningsalgoritmen för det. Emellertid är det svårare att lösa om man har mer än 3 pinnar. Så vilken är algoritmen för fyra pinnar?

Krake skrev:<a href="http://en.wikipedia.org/wiki/Towers_of_hanoi">Tornen i Hanoi</a> är ett känt problem. Det är ganska lätt att hitta lösningsalgoritmen för det. Emellertid är det svårare att lösa om man har mer än 3 pinnar. Så vilken är algoritmen för fyra pinnar?

Inte alls. Du kan bortse från den fjärde pinnen och använda samma lösning som för tre pinnar.

Krake skrev:dist(u,N) är minsta avståndet mellan punkten u och mängden N. Vi vill hitta en mängd punkter, nämligen N, så att dist(u,N)=C för något C oavsett vilket u vi väljer.

Är dist(u,N) = min dist(u,n) över alla n i N?

Är problemet då alltså följande?

Givet en mängd U av punkter i planet, finns det ett C och en mängd N av punkter i planet sådana att för alla u i U gäller dist(u,N)=C?

Och så är vi dessutom intresserade av att minimera |N|.



Innan du gissar för mycket om svaret, fundera på fallet då alla punkter i U ligger på x-axeln, med y-koordinater motsvarande de |U| första primtalen. Intuition är farligt i matematiken, men låt oss säga att jag i alla fall inte skulle bli förvånad om |N| >= |U|-1 i detta fall.

Jävlar vilka catfights min far och jag hade när det var dags för matteläxan. Okvädinsord och mattehäften regnade genom lägenheten. Man kan väl säga som så att jag är glad att jag gick humanistiska programmet och slapp matte sista året. Läste upp till matte B och blev faktiskt godkänd.

Kvasir skrev:Är dist(u,N) = min dist(u,n) över alla n i N?

Stämmer

Kvasir skrev:Är problemet då alltså följande?

Givet en mängd U av punkter i planet, finns det ett C och en mängd N av punkter i planet sådana att för alla u i U gäller dist(u,N)=C?

Och så är vi dessutom intresserade av att minimera |N|.



Innan du gissar för mycket om svaret, fundera på fallet då alla punkter i U ligger på x-axeln, med y-koordinater motsvarande de |U| första primtalen. Intuition är farligt i matematiken, men låt oss säga att jag i alla fall inte skulle bli förvånad om |N| >= |U|-1 i detta fall.

Ja det är det som är problemet. I specialfallet du beskriver kan man lätt bevisa att |N|<|U|. Beviset går som följer: Vi antar att punkterna i U ligger på x-axeln. Välj två punkter i, a och b, i U så att dist(a,U\a) = dist(b,U\b) = dist(a,b). Vi kan alltid välja två sådana punkter vilket är uppenbart men jag utelämnar beviset för detta. Vi kan placera en punkt mitt emellan dessa på avståndet c = dist(a,b)/2. Därefter kan vi lägga övriga punkter i N på en linje, L, med avståndet c från x-axeln. För varje punkt, u, i U utom a och b placerar vi nu en punkt på L med avståndet c från u. Det finns exakt en sådan punkt för varje u i U. Det är |U| - 2 punkter och vi har en punkt till för a och b så |N| är aldrig större än |U| - 1 om U består av mer än en punkt placerade på en linje. Man kan använda detta konstruktiva bevis på ett klurigt sätt för att få ner storleken på |N| ytterligare till |U|/2 om |U| är jämnt och |U+1|/2 om |U| är udda men då ligger inte punkerna i N på en linje längre.

Teckenförklaring: |U| antalet punkter i mängden U
U\a alla punkter i U utom punkten a

Jag hoppas det är svar på frågan Kvasir. Med tornen i Hanoi söker man givetvis efter den effektivaste metoden. Om man har fler pinnar än block blir antalet förflyttningar alltid antalet block*2 - 1.

Matte är underbart!!! Logiskt och roligt!

och jag som tänkte på kvinnliga hundägare först...

Krake skrev:Ja det är det som är problemet. I specialfallet du beskriver kan man lätt bevisa att |N|<|U|. Beviset går som följer: Vi antar att punkterna i U ligger på x-axeln. Välj två punkter i, a och b, i U så att dist(a,U\a) = dist(b,U\b) = dist(a,b). Vi kan alltid välja två sådana punkter vilket är uppenbart men jag utelämnar beviset för detta. Vi kan placera en punkt mitt emellan dessa på avståndet c = dist(a,b)/2. Därefter kan vi lägga övriga punkter i N på en linje, L, med avståndet c från x-axeln. För varje punkt, u, i U utom a och b placerar vi nu en punkt på L med avståndet c från u. Det finns exakt en sådan punkt för varje u i U. Det är |U| - 2 punkter och vi har en punkt till för a och b så |N| är aldrig större än |U| - 1 om U består av mer än en punkt placerade på en linje.

Så långt trivialt.

Man kan använda detta konstruktiva bevis på ett klurigt sätt för att få ner storleken på |N| ytterligare till |U|/2 om |U| är jämnt och |U+1|/2 om |U| är udda men då ligger inte punkerna i N på en linje längre.

Men det är ju den delen av beviset som är det intressanta och viktiga.

Men jag tänkte till lite mera och kom på att min intuition var fel (vad var det jag sade om att intuition är farligt i matematik? ). Naturligtvis kan man klara sig med |U|/2 extra punkter, och detta oavsett var i planet punkterna i U ligger.

Bevisskiss:
Para ihop punkterna i U två och två på godtyckligt vis. Låt C vara det största avståndet inom ett sådant par. För varje par av punkter p och q i U lägger vi till en tredje punkt r så att de tre punkterna bildar en triangel där sträckorna pr och qr båda är av längden C.

Jag hoppas det är svar på frågan Kvasir. Med tornen i Hanoi söker man givetvis efter den effektivaste metoden. Om man har fler pinnar än block blir antalet förflyttningar alltid antalet block*2 - 1.

Jag svarade på vad du frågade, som i stort sett alla matematiker skulle ha gjort. Om du menade något annat än du frågade så ställde du fel fråga.

Du är fortfarande diffus in din formulering. Är vi intresserade av en specifik algoritm för att lösa problemet, eller är vi intresserade av hur själva lösningarna ser ut (dvs. sekvensen av förflyttningar)? Sistnämnda har t.ex. optimala lösningar som kan beskrivas med rekursiva scheman på rättframt sätt (åtminstone i fallet 3 pinnar). Eftersom du talar om metod och använder ordet effektiv så låter det dock som du snarare är ute efter en algoritm med låg komplexitet för någon rersurs.

En uppenbar observation är i alla fall att om vi kan lösa problemet för n diskar och 3 pinnar med högst f(n) drag, så kan vi lösa det med 4 pinnar i högst 4f(n/2) drag.

Någonting mellan "En kärleksaffär" och "Fascinerande"... Det beror på vad jag är på för humör, och vilken sorts matte vi talar. När det är matte som jag inte fattar, då är det fascinerande, och när det är något jag fattar och kan, då är det en kärleksaffär.

Arkimedes skrev:En kärleksaffär.

Visste väl jag kunde lita på dig Arkimedes i denna frågan.

Miche skrev:Själv är jag fascinerad av matte och kan (då jag mår bra och inte är för trött) komma på problem som jag tycker är kul att lösa.

+1!

s.cat skrev:Matte är underbart!!! Logiskt och roligt!

Har du asperger eller något?

Men du har så rätt så +1 på dig. Matten till skillnad från ex. människor är fullständigt logisk och kan endast bli på ett sätt. Det är alltid logiskt, och reaktionen blir densamma. Siffror kan jag handskas med mycket bättre än människor faktiskt, hur sjukt det än låter. Människor reagerar så konstigt ibland, och helt ologiskt och inte minst, så olika. Siffror däremot är underbara och reagerar alltid på samma sätt.