Trenger svar på en gåte

[dostojevski]

Nå får det være nok. Vet ikke hvor mange timer jeg har brukt på dette problemet det siste året, men det er altfor mange... Har derfor kommet opp med et lite innlegg som jeg håper kan være av almenn interesse.

 

Hvis vi forutsetter at denne oppgaven skal løses slik den er beskrevet, altså at jukseløsninger som streker som følger noen av strekene, tangerer en av strekene osv. ikke regnes som gyldige løsninger mener jeg nå å kunne slå fast med SVÆRT god sikkerhet at denne oppgaven ER uløselig. Altså i tråd med de matematiske forklaringene som er gitt her tidligere, men denne modellen burde være enklere å akseptere for folk med for mye kinderegg i lomma.

 

La meg forklare:

 

Vi kan betrakte denne modellen som en graf med noder og sider. En pasering av en strek vil da være en node i grafen. Imidlertid vil det ikke være likegyldig hvilken vei streken blir krysset, så vi har faktisk to grafer; en med seksten noder(som angir OM en side er krysset) og en med 32 (som også angir hvilken vei streken er krysset). Forhåpentligvis kan en tegning forklare dette bedre:

 

 

Hver pil har sitt nummer, og sammenhengen mellom pilene kan beskrives slik:

 

[bEGIN GRAPH]

1x3:5:7:14:23:28:30:31

2x8:9:16

3x10:11:18:20

4x2:5:7:14:23:28:30:31

5x12:13:21

6x2:3:7:14:23:28:30:31

7x1:9:16

8x2:3:5:14:23:28:30:31

9x4:10:11:18:20

10x1:8:16

11x6:13:21

12x4:10:18:20

13x2:3:5:7:23:28:30:31

14x6:12:21

15x1:8:9

16x17:24:25:29

17x4:10:11:20

18x18:24:25:29

19x4:10:11:18

20x22:26:27:32

21x19:26:27:32

22x6:12:13

23x15:17:25:29

24x2:3:5:7:14:28:30:31

25x19:22:27:32

26x15:17:24:29

27x2:3:5:7:14:23:30:31

28x19:22:26:32

29x2:3:5:7:14:23:28:31

30x15:17:24:25

31x19:22:26:27

32x2:3:5:7:14:23:28:30

[END GRAPH]

 

Den første linjen betyr feks. "hvis du følger pil 1 kan du neste gang følge en av følgende piler 3,5,7,14,23,28,30 eller 31. Du kan selvsagt IKKE følge pil 2 siden denne siden allerede er krysset, og du kan heller ikke følge en av de nevnte pilene hvis denne krysser en "oppbrukt" side.

 

Ved hjelp av denne definisjonen er det ikke så vanskelig å lage et program som sjekker ALLE mulige kombinasjoner. Dette har jeg nå gjort, og konklusjonen er entydig:

 

Dette problemet har 14.240.790 mulige veier, altså stier man kan følge helt til man ikke har flere ukryssede linjer å krysse, og INGEN av disse oppfyller kravene oppgaven stiller.

 

For å overbevise eventuelle tvilere har jeg sørget for å logføre alle disse mulige veiene, men siden denne teksfilen er på tett oppunder en gigabyte lar jeg være å legge den ut.

 

Imidlertid kan alle som ønsker å gjenta eksperimentet laste ned dette programmet her. Dette er en kjørbar .jar-fil, kjør den ved å skrive java -jar solver.jar (hvis du ikke har JRE installert regner jeg det som lite sansynlig at du gidder å surre med dette...)

 

Filen som genereres er som sagt på nesten 1 GB, og programmet drar ALT du har av cpukraft og en god del minne. Hele poeneget med denne løsningen var å gjøre det brute force, og følgelig er det snakk om sinsvakt mye regning. Min XP2500@XP3200 med 1GB ram og Win XP brukte cirka en halv time.

 

Så neste gang en eller annen suppegjøk legger frem denne lille "nøtten" og påstår det finnes en løsning: legg fjorten komma to millioner tekstlinjer i bordet og be ham gå og plage noen andre.

 

 

EDIT:

Problemet med graf.txt-filen er fikset. Funker å kjøre .jar-filen som beskrevet.

 

EDIT II:

Fant ut at ved å pakke loggfila litt hardt kom den ned i drøye 25 MB. Så hvis noen er interessert; her er den.

Endret 20. april 2004 av dostojevski

[Raggi]

husker vi sto i friminuttene på ungdomsskolen å prøvde os om og om igjenn på denne oppgaven... ingen som fikk det til...

 

har hørt att det ikke er noen som har klart det, men att det vistnok skal vere en datamaskin som har klart det.

[dostojevski]

Men les det jeg skriver da mann. Det FINNES ingen løsning! Min datamaskin har nettop prøvd, og den greide det IKKE. Og det er ikke fordi den er dårlig eller fantasiløs eller ikke liker matteoppgaver. Finner du en logisk feil i algoritmen min skal jeg gi meg...

[andm]

Så da har oppgaven verken en logisk eller matematisk rett løsning. Det kan kanskje være en spesiell måte å løse den på da. Takk for hjelpen så langt, matematikere. Jeg skal prøve i ny og ne og se om muligens det finnes et ulogisk løsning. Bare gi forslag til løsning! Det er forresten ikke nødvendig å gi flere bevis for å klargjøre at oppgaven er umulig, for det vet jeg nå...