Finurliga frågor. Är detta olösligt?

[ronny]

det e det ju

inte på din första skiss...

 

på den andra så var vi väl överens om att det var fusk att dra ledningar

genom husen... då kan man ju dra alla tre ledningar genom samtliga hus

[Hinkebo]

 

????????

[ClCdCm]

En komponent i Kabos problem har ett användningsområde inom GIS (geografiska informationssystem) när man arbetar med vektorbaserade kartor.

 

En vanlig operation inom GIS är att man har två lager med information som man vill lägga samman till ett lager. Det kan vara exempelvis vektoriserade kommungränser (som polygoner) i ett lager och i ett annat lager har man punktdata i vektorformat, som visar platser en viss växt har hittats. Vill man ha reda på hur många växtplatser som finns i varje kommun, lägger man det ena lagret över det andra och sorterar efter det, kan man säga.

 

Hur kan man på ett enkelt sätt avgöra inom vilken kommungräns (vilken polygon) varje punkt befinner sig? Jo, man låter en beräkningsmodul få punkten att "falla" från sin ursprungsposition, ner genom kartlagret, tills punkten når kanten av lagret. Sen registreras varje tillfälle som en viss kommuns gräns passeras. Den kommuns gräns som passerades ett udda antal gånger är också den kommun som punkten befinner sig i. Alla andra polygoner måste man passera ett jämnt antal gånger.

 

Med den här metoden kan man klara av att mycket snabbt bedöma inom vilken polygon en punkt är lokaliserad, även om polygonen har en mycket komplicerad form. Det sparar enormt med processorkraft och tid att göra så. I vissa fall kan man behöva göra det här i mer än en riktning för att undvika vissa precisionsfel, men det tar ändå mycket kortare tid.

 

Inte helt off topic ändå!

[Semmelman]

Fast Kabos grej var så enkel - ang min lösning - så det måste va nåt fel i instruktionen…

[ronny]

Så här tolkade jag det

 

aha hus 2 var en el central

[Kabo]

jag kanske gav vaga instruktioner

[ronny]

Sorry- men alla blå utgår inte från samma hus!

ja det var det som var hållhaken

[ClCdCm]

Var tvungen att göra en liten illustration till, på det jag nyss nämnde...

 

Kartan här visar tre kommuner (de drog kommungränserna efter en svår firmafest...) som illustreras med lila, gult och blått, med gröna gränser mellan och runt.

Den gröngula punkten befinner sig i en kommun, och vi vill veta vilken. Låt punkten falla längs den röda linjen, ut genom kartgränsen till det vita tomrummet. För varje gränspassage passeras två kommuners gränser. Man lämnar en och går in i en annan. Räkna antalet gränspassager per kommun, så får man det antal gränspassager per kommun som de svarta siffrorna i kommunerna visar.

 

Eftersom talet i den lila kommunen är udda, måste punkten befinna sig där.

 

[Semmelman]

Nu förstår jag än mindre Kabo. Är det där röda dörrar som man måste gå igenom? De verkar vara godtyckligt utkastade, en del rum har tre dörrar och nåt bara en, klart det går att göra problem som inte går att lösa då…

Måste man börja och sluta vid den röda punkten?

Nä du får nog ta och börja om och göra om, vi vill ha klara precisa instruktioner! Tur att du och den där läraren inte är arkitekter, hade inte blivit några dörrar och fönster rätt nånstans. Förstår att den där läraren ville ha hela dagen ledig och inte bara rökpaus.

[jakob.bohem]

Äh, jag slängde ihop en skiss i alla fall.

 

Den här ytan utgör en torus som är utvikt till ett platt plan.

 

Lila kanter utgör de kanter som fogas samman för att bilda cirkelformen. Gula kanter utgör de kanter som fogas samman för att bilda rörformen.

 

Ledningar som går mot kanterna fortsätter runt, ska det tolkas som.

 

På det sättet får problemet en lösning, men det funkar bara i det här specialfallet.

 

Fungerar det inte med en sfär med då?

Finns det något bevis för att problemet inte går att lösa i planet?

[Kabo]

Nu förstår jag än mindre Kabo. Är det där röda dörrar som man måste gå igenom? De verkar vara godtyckligt utkastade, en del rum har tre dörrar och nåt bara en, klart det går att göra problem som inte går att lösa då…

Måste man börja och sluta vid den röda punkten?

Nä du får nog ta och börja om och göra om, vi vill ha klara precisa instruktioner! Tur att du och den där läraren inte är arkitekter, hade inte blivit några dörrar och fönster rätt nånstans. Förstår att den där läraren ville ha hela dagen ledig och inte bara rökpaus.

Man ska gå igenom alla linjer men bara en gång- på skissen du gjorde markerade jag de linjer du inte passerat.

[treebeard]

Fungerar det inte med en sfär med då?

Finns det något bevis för att problemet inte går att lösa i planet?

Ja, det finns bevis för att det inte går lösa, åtminstone går det ganska lätt att visa. Tyvärr hinner jag inte sätta mig och måla nått nu, men i princip går det ut på att om man placerar ut 2 hus och el samt vatten, bildar det en sluten ring av ledningar. För att sedan kunna koppla in det tredje huset, bildas ytterligare en ring (ungefär som en åtta). Det är då 3 avdelade områden (inne i ringarna samt utanför), och i ett av dom ska sopporna sättas. För att placera ut det sista kraftverket går inget av dessa områden att använda utan att ledningarna ska korsa varandra.

Kommer jag ihåg fixar jag en figur ikväll

[ClCdCm]

Fungerar det inte med en sfär med då?

 

Nix. Om du tittar på min skiss, ser du att den blå och den röda linjen måste korsa varandra i samma plan om man placerar dem på en sfär. På en torus, däremot, kan den blå linjen gå på utsidan ringen, medan den röda går runt röret, så att säga. Helt olika platser och inga korsade ledningar.

[Semmelman]

Man ska gå igenom alla linjer men bara en gång- på skissen du gjorde markerade jag de linjer du inte passerat.

Jaha, alla dellinjer… men du missade markera en linje till vänster i din rättelse.

 

Men då ska jag försöka. Fast nu vet jag det är meningslöst så jag får se.

[Semmelman]

Ger upp.

[Pocahontas]

Eftersom ingen bygger sina hus på en torusring så får vi hålla oss till två dimensioner

[katzenklavier]

Man ska gå igenom alla linjer men bara en gång- på skissen du gjorde markerade jag de linjer du inte passerat.

Så här?

 

 

EDIT: F*n, ser nu att jag missat några ställen, men det går ju också att ta de

[Semmelman]

Nåt på G kanske fast du missade fyra till fem väggar tror jag.

[ronny]

Ja ni får fundera ett par dagar till

[Bille10]

Är detta rätt??

namnlös.bmp

[Pocahontas]

Är detta rätt??

 

Inte när det gäller att bifoga bilder...

[royzon]

nej

[friend]

Inte när det gäller att bifoga bilder...

[royzon]

så då

[Telly82]

så då

Du glömde (minst) en (del)vägg.