Kvasir skrev:

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.

Även om skissen känns logisk är det inte så lätt att bevisa detta. Man måste nämligen visa att r inte lägger sig för nära en annan punkt i U. Tänk till exempel att punkterna p och q har avståndet C emellan sig. Om man tänker sig en linje mellan dessa punkter så ser vi att r befinner sig på avståndet (roten ur 3)/2 från linjen. Nu får vi dock problem eftersom det kan finnas en punkt, s, i U som är avståndet D<C ifrån r och vi måste göra om allting igen. Hur kommer du runt det hindret?

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.

Söker alltså efter en optimal algoritm. Antalet minimala drag man måste göra har en underlig relation till pascals triangel eller i fallet med 4 pinnar till en aritmetisk serie.

Krake skrev:Även om skissen känns logisk är det inte så lätt att bevisa detta. Man måste nämligen visa att r inte lägger sig för nära en annan punkt i U.

Ah, tusan, det glömde jag i hastigheten, att det handlade om minsta avståndet till någon punkt i N. Ja ja, det är som det brukar med knepiga problem, man måste göra ett antal misslyckade bevisförsök för att börja få grepp om problemet. Nå, då är det kanske trots allt så knepigt som jag misstänkte från början.

Finns det något ursprung till problemet, eller är det ett rent konstruerat teoretiskt problem? Jag skulle inte bli förvånad om det är sprunget ur någon tillämpning av något slag, men att det i så fall också (vanligen) finns ytterligare begränsningar i praktiska fall.

Söker alltså efter en optimal algoritm. Antalet minimala drag man måste göra har en underlig relation till pascals triangel eller i fallet med 4 pinnar till en aritmetisk serie.

Antalet drag i fallet 3 pinnar är 2^n - 1, vilket är tämligen rättframt att se genom att konstruera ett rekursivt schema. Dock är jag inte säker på att någon har visat att detta verkligen är även en undre gräns, även om det förefaller rimligt.

Jag har aldrig funderat över andra fall än det vanliga med 3 pinnar, men det skulle jag tro finns en del om i litteraturen också. Den observation jag nämnde tidigare visar på en omedelbar förättring, även om den inte säger något om undre gräns.

Edit:
En snabb googling ger några länkar om 4-pinsvarianten:

http://www.cs.uci.edu/bin/pdf/seminarseries2k8/KorfRichard.pdf
(Korf brukar vara insatt. Jag har bara tittat hastigt men de nämner något om en känd lösning men att den aldrig bevisats optimal. De nämner också en intressant anomali på slutet.)

http://www.scs.carleton.ca/research/tech_reports/2004/TR-04-10.pdf
(Hävdar att de visar optimalitet för en känd lösning.)

Punktproblemet kom jag att tänka på då jag satt i badrummet och kollade på klinkersen på golvet. Grundmönstret kommer av att golvet är täckta med kvadrater som ligger kant mot kant, hörn mot hörn. Det finns dock en större kvadrat med dubbla sidan som ligger diagonalt. Omkring denna finns därför 4 trianglar och 8 oregelbundna femhörningar. Jag noterade att mittpunkten i kvadraterna var lika långt från alla hörnen men i femhörningarna så var det inte så. Så jag började tänka och undrade hur många punkter jag behövde för att hitta ett gemensamt minsta avstånd till alla hörnen. Jag startade tråden direkt efteråt.

Krake skrev:Punktproblemet kom jag att tänka på då jag satt i badrummet och kollade på klinkersen på golvet. Grundmönstret kommer av att golvet är täckta med kvadrater som ligger kant mot kant, hörn mot hörn. Det finns dock en större kvadrat med dubbla sidan som ligger diagonalt. Omkring denna finns därför 4 trianglar och 8 oregelbundna femhörningar. Jag noterade att mittpunkten i kvadraterna var lika långt från alla hörnen men i femhörningarna så var det inte så. Så jag började tänka och undrade hur många punkter jag behövde för att hitta ett gemensamt minsta avstånd till alla hörnen. Jag startade tråden direkt efteråt.

Äkta matematisk nyfikenhet!

Fast det problem du definierade känns ändå ganska abstraherat från ursprungsfallet med klinkers. Inte för att det gör något, men om man försöker hålla sig kvar i klinkersvärlden och definiera något lite mera praktiskt intressant problem så kanske man kan hitta intressanta lösningar. Ofta är de begränsade fallen intressantare än de generella även matematiskt.

Jag tycker inte att matte är roligt, är så satans dålig på det.

Maldita skrev:Jag tycker inte att matte är roligt, är så satans dålig på det.

Om du lär dig att förstå matte blir det roligare, fast de som lider av [WikiSve]dyskalkyli[/WikiSve] har väldigt svårt att komma in i det, men jag tror att även de kan lära sig en del matematik genom att använda individuella tankesätt.

För k = 1 och k = 2 är N(k) = 1. De fallen är triviala.

För k = 3 är N(k) = 2. Man ser lätt att det krävs två punkter i N om de tre punkterna i U ligger på en rät linje.

För k >= 4 tror jag att är N(k) = k-2.

Bevis för att k-3 punkter inte räcker:
Sätt u1=(0,0) u2=(1,0) u3=(-1/2,sqrt(3)/2) och u4=(-1/2,-sqrt(3)/2). Man ser då att varje punkt utanför enhetscirleln, x^2+y^2=1, ligger närmare u2, u3 eller u4 än u1. Det betyder att minst en punkt i N måste ligga på eller innanför enhetscirkeln och att C är mindre än eller lika med 1. Placera nu övriga punkter i U så att avståndet till närmaste punkt i U är större än 2. Det kan man till exempel göra genom att placera um i (3m,0). Eftersom C är högst 1 krävs det en punkt i N för varje punkt i um, m > 4. u1 till u4 kräver uppenbart minst två punkter och man ser att två punkter räcker om man placerar dem till exempel i (1/2,sqrt(3)/2) och (-2,0).

Det som återstår är att bevisa att det alltid räcker med k-2 punkter för k >= 4.

Ser nu att jag har placerat den sista punkten fel. (-1,0) i stället för (-2,0) fungerar.

Du tog fallet med 4 punkter och då är det givet att det inte räcker med 1 (k-3) punkt eftersom det inte gör det om man har 3 punkter. Men om U ligger på en rak linje har vi N(k)=[(k+1)/2] där [] betyder avrundas nedåt. Man kan bevisa det på liknande sätt som mitt bevis för att N(k)<=k-1. Man kan anta att punkterna i U då ligger på x-axeln. Man parar ihop varje punkt (utom möjligtvis en punkt) i U med en av sina grannar (så att man får [(k+1)/2] par) och placerar punkterna i N ett fixt avstånd c ifrån varje par där c är större eller lika med halva det maximala avståndet mellan ett sådant par. För varje par i U med koordinater (p,0) och (q,0) placerar man tilldelad punkt i N med x-koordinaten (p+q)/2 och så har man precis [(k+1)/2] punkter i N.

Vad gäller klinkerplattorna så handlar det då bara om (o)regelbundna polygoner vilket endast utesluter fallet då alla punkter i U befinner sig på en linje, så det blir inte mycket bättre av det tyvärr.

Jag tror att bästa sättet att lösa problemet på är inte genom att studera U utan genom att hitta metoder för att en specifik lösning för ett godtyckligt U. Givet varje par ,p,q, i U finns en linje, som vi kan kalla för L, som uppfyller dist(p,L) = dist(q,L). Vi har nu en samling av alla möjliga linjer för varje par i U som vi kan kalla för E(U) eller bara E. Vi kan nu söka lösningar för på följande sätt: Låt O(U,r) vara alla punkter, o, som uppfyller dist(o,U)=r. Nu väljer vi alla punkter som tillhör både E och O(r) som vi kan beteckna som S(r). Det kan vara en tom mängd men om den är det så låter vi r växa tills S(r) innehåller minst en punkt. Om den punkten räcker är vi klara annars ökar vi r tills S(r) innehåller minst två punkter och så vidare. Nu ser vi att vi sannerligen inte behöver mer än [(k+1)/2] punkter i N eftersom varje linje i E matchar minst två punkter (fler där linjerna i E korsas). Nu återstår bara frågan när man klarar sig med mindre än [(k+1)/2] punkter.

Krake skrev:Du tog fallet med 4 punkter

Nej. Jag tog fallet med fyra eller fler punkter.

Krake skrev:Men om U ligger på en rak linje har vi N(k)=[(k+1)/2] där [] betyder avrundas nedåt.

Ointressant eftersom det inte är det svåraste fallet. Mitt exempel kräver k-2 punkter för k större än eller lika med 4.

Krake skrev:Nu ser vi att vi sannerligen inte behöver mer än [(k+1)/2] punkter i N eftersom varje linje i E matchar minst två punkter (fler där linjerna i E korsas). Nu återstår bara frågan när man klarar sig med mindre än [(k+1)/2] punkter.

Detta är en felaktig slutsats. Jag utmanar dig att visa hur man ska placera 3 punkter i N när k=6 och punkterna i U är enligt exemplet i mitt bevis (0,0) (1,0) (-1/2,sqrt(3)/2) (-1/2,-sqrt(3)/2) (15,0) och (18,0). Det går inte. Det krävs 4 punkter i N.

Ja du har förstås alldeles rätt. Man behöver restriktionen att max(dist(u,O(r))) = r vilket begränsar vilka radier man kan använda. Det stämmer dock att man kan använda min metod för att hitta N.

Vi kan förstås alltid hitta N så att N innehåller k-2 punkter eftersom vi alltid kan hitta en tre punkter i U så att cirkeln som går genom alla tre punkterna inte innehåller någon annan punkt i U (för om den gör det så gör vi en ny cirkel med hjälp av den punkten) eller så ligger U på en linje vilket är ett redan behandlat fall. Vi bugar och applåderar för mats som hittade lösningen.

Tack för applåderna! Men... jag hittade inte hela lösningen. Jag hittade den undre gränsen. Den övre gränsen hittade du själv.

Jag saknar alternativet "ologiskt och överflödigt".

tahlia skrev:Jag saknar alternativet "ologiskt och överflödigt".

På vilket sätt är matte ologiskt? Mycket är det, vissa former av matten är ytterst onödiga att kunna om man inte har speciellt jobb, men på vilket sätt är det ologiskt? Hela matematiken bygger ju på logik.

marxisten skrev:

tahlia skrev:Jag saknar alternativet "ologiskt och överflödigt".

På vilket sätt är matte ologiskt? Mycket är det, vissa former av matten är ytterst onödiga att kunna om man inte har speciellt jobb, men på vilket sätt är det ologiskt? Hela matematiken bygger ju på logik.

People keep saying that, men jag har aldrig lyckats hitta logiken i (vad man då skulle även skulle kunna kalla "nyckeln" till) matematik.
Det var faktiskt lite lustigt. Min utredning sa att jag var logisk men var helt värdelös på matematik.

Så har det varit sedan dag ett. Grejen är att det alltid handlar om addition, subtraktion, division eller multiplikation. Alltid. Men sedan ska man döpa om saker och ting, slänga in bokstäver, paranteser och begrepp åt höger och vänster vilket gör matematiken till ett enda stort virrvarr av galenskap och plötsligt blir det ett landskap där man bara krånglat till saker för att folk ska gå vilse (läs jag ska gå vilse).

Det är först de senaste månaderna jag har insett att det är där problemet ligger för min del. Att göra saker så mycket krångligare än de behöver vara ter sig inte logiskt någonstans i mina ögon, och gör matematikproblem till olösliga gåtor. Att man dessutom väldigt ofta kan ersätta en uträkning som just ingen människa förstår, med ett antal ord som alla förstår gör att matematiken känns vansinnigt onödig väldigt ofta.

Min felaktiga lösning (den med E och O) var faktiskt inte helt ute och cyklade. Den fungerar alldeles utmärk om man bara håller sig sådana Un som inte har instängda punkter. Kan man då landa på N någonstans mellan dessa lösningar med hänsyn till hur många instängda punkter det finns och med vilken radie relativt fördelningen av övriga punkter?

Hur ser det ut i andra rum i planet? i en dimension (en linje) har vi att N(k) = k - 1 för k större än 1. En gissning skulle vara att i R^n har vi N(k) = k - n för k större än n. Sedan finns andra rum som till exempel ytan på en sfär eller på en torus.

tahlia skrev:Grejen är att det alltid handlar om addition, subtraktion, division eller multiplikation. Alltid. Men sedan ska man döpa om saker och ting, slänga in bokstäver, paranteser och begrepp åt höger och vänster vilket gör matematiken till ett enda stort virrvarr av galenskap och plötsligt blir det ett landskap där man bara krånglat till saker för att folk ska gå vilse (läs jag ska gå vilse).

Matematiskt språk (tecknen, uttryck, konventioner för hur man skriver vad) görs inte för att vara lätt att förstå! Bakvänt nog.

Jag misstänker att den matematiska utvecklingen skulle ha nått mycket längre ifall man verkligen ständigt lagt ner ansträngningar på att härleda allting från samma lilla grundspråk. Istället utgår man ständigt från något tidigare, annorstädes härlett begrepp utan att visa härledningen fram till det.


Men poängen med det komplexa språket är väl rätt god, den är ju just att göra det möjligt att beskriva komplexa saker i få tecken/ord. Bara man alltid tog med hela härledningen också, så skulle jag vara helt med på noterna.

[EDIT] Kanske har jag svårare än vad de flesta har för att tro på eller "begripa" ett begrepp innan jag sett helt säkert att det passar in i något jag redan känner till. Vore jag smartare så skulle jag kunna hålla nya begrepp och deras påstådda betydelse i minnet tills jag fått ihop ett nytt pussel med det jag redan lagt men som det är så gör proffsmatematikerna det svårt för mig. Jag känner mig faktiskt rejält utefrusen.

jonsch skrev:Matematiskt språk (tecknen, uttryck, konventioner för hur man skriver vad) görs inte för att vara lätt att förstå! Bakvänt nog.

Jag misstänker att den matematiska utvecklingen skulle ha nått mycket längre ifall man verkligen ständigt lagt ner ansträngningar på att härleda allting från samma lilla grundspråk. Istället utgår man ständigt från något tidigare, annorstädes härlett begrepp utan att visa härledningen fram till det.

Men poängen med det komplexa språket är väl rätt god, den är ju just att göra det möjligt att beskriva komplexa saker i få tecken/ord. Bara man alltid tog med hela härledningen också, så skulle jag vara helt med på noterna.

Måste säga att du har fel Jonsch. Om man skulle härleda allt till ursprungskärnan skulle varje bevis på 3 rader bli 3 sidor och varje bevis på 3 sidor bli 300 sidor. Det skulle vara så otympligt att det inte gick att använda. Som det nu är bygger man småsaker på grunderna saker på småsakerna och storsaker på sakerna, så att säga. Det är betydligt lättare att samla på det sättet och kan beskrivas som att man samlar dokument i mappar istället för att lägga de över varandra mitt på golvet.

@tahlia
All matte bygger inte på räknesätten. I logik bygger man direkt från axiomen och definierar till och med de naturliga talen utan att ta deras existens för given på förhand. Logik kan sägas vara det område i matematiken där man på det mest direkta sättet använder ett sorts orsak-verkan tänkande utan att blanda in formler i det hela.

tahlia skrev:

marxisten skrev:

tahlia skrev:Jag saknar alternativet "ologiskt och överflödigt".

På vilket sätt är matte ologiskt? Mycket är det, vissa former av matten är ytterst onödiga att kunna om man inte har speciellt jobb, men på vilket sätt är det ologiskt? Hela matematiken bygger ju på logik.

People keep saying that, men jag har aldrig lyckats hitta logiken i (vad man då skulle även skulle kunna kalla "nyckeln" till) matematik.
Det var faktiskt lite lustigt. Min utredning sa att jag var logisk men var helt värdelös på matematik.

Så har det varit sedan dag ett. Grejen är att det alltid handlar om addition, subtraktion, division eller multiplikation. Alltid. Men sedan ska man döpa om saker och ting, slänga in bokstäver, paranteser och begrepp åt höger och vänster vilket gör matematiken till ett enda stort virrvarr av galenskap och plötsligt blir det ett landskap där man bara krånglat till saker för att folk ska gå vilse (läs jag ska gå vilse).

Det är först de senaste månaderna jag har insett att det är där problemet ligger för min del. Att göra saker så mycket krångligare än de behöver vara ter sig inte logiskt någonstans i mina ögon, och gör matematikproblem till olösliga gåtor. Att man dessutom väldigt ofta kan ersätta en uträkning som just ingen människa förstår, med ett antal ord som alla förstår gör att matematiken känns vansinnigt onödig väldigt ofta.

Bokstäver har man för att ersätta en siffra och de är helt logiska, om man vet vilken siffra de ska vara. Och för olika formler är de livsnödvändiga. Säg rötterna ur en andragradsekvation, är mycket enklare att minns hur man räknar ut via ett uttryck som är känt som P-Q formeln. X= p/2 +- roten ur ((p/2^2)-q), jämfört det hade stått med siffror istället för bokstäver, då hade det varit omöjligt att minnas. I formeln står nämligen P för en viss del av ett tal och Q för en annan.

Gällande parenteser så är de jätteviktiga. Ex. om du skriver a+b-a-b jämfört med (a+b)+(a-b) så får du helt olika resultat. Om A är 5 och B är 2 blir. Det förstnämnda blir då: 5+2-5-2=0... Om du däremot skriver det (a+b)-(a-b), blir det istället. (5+2)-(5-2)... Då räknar du ut de separat och får fram 5+2=7, 5-2=3... 7-3=4.

Hemligheten i matte är att se logiken...

Krake skrev:

jonsch skrev:Jag misstänker att den matematiska utvecklingen skulle ha nått mycket längre ifall man verkligen ständigt lagt ner ansträngningar på att härleda allting från samma lilla grundspråk. Istället utgår man ständigt från något tidigare, annorstädes härlett begrepp utan att visa härledningen fram till det.

Måste säga att du har fel Jonsch. Om man skulle härleda allt till ursprungskärnan skulle varje bevis på 3 rader bli 3 sidor och varje bevis på 3 sidor bli 300 sidor. Det skulle vara så otympligt att det inte gick att använda.

Det är väl en smal sak att skriva ett program som med några musklickningar kan förvandla ett 3 raders bevis till sin härledda 3 sidors eller 300 sidors?

Är logiken ett avslutat ämne där allt som finns att säga redan är sagt eller sker det en utveckling där fortfarande?