Nio prickar pussel

Pusslet "nio prickar". Pusslet ber att länka alla nio prickarna med fyra raka linjer eller färre, utan att lyfta pennan.

Niopunktspusslet är ett matematiskt pussel vars uppgift är att förbinda nio kvadratiskt arrangerade punkter med en penna med fyra (eller färre) raka linjer utan att lyfta pennan.

Pusslet har dykt upp under flera andra namn genom åren.

Historia

År 1867, i den franska schacktidskriften Le Sphinx , dök en intellektuell föregångare till pusslet med nio prickar upp till Sam Loyd . Nämnda schackpussel motsvarar ett "64 punkters pussel", dvs att markera alla punkter i ett 8 x 8 kvadratgitter , med en extra begränsning.

The Columbus Egg Puzzle från The Strand Magazine , 1907

År 1907 dyker pusslet med nio punkter upp i en intervju med Sam Loyd i The Strand Magazine :

"[...] Plötsligt kom ett pussel i mitt sinne och jag skissade upp det åt honom. Här är det. [...] Problemet är att rita raka linjer för att koppla ihop dessa ägg i minsta möjliga antal drag. Linjerna kan passera genom ett ägg två gånger och kan korsa. Jag kallade det Columbus Egg Puzzle."

Samma år dök pusslet även upp i A. Cyril Pearsons pusselbok. Det var där som hette ett charmigt pussel och involverade nio prickar.

Båda versionerna av pusslet dök därefter upp i tidningar. Från åtminstone 1908 körde Loyds äggversion som reklam för Elgin Creamery Co i Washington, DC. , omdöpt till The Elgin Creamery Egg Puzzle . Från åtminstone 1910 dök Pearsons "nio prickar"-version upp i pusselavsnitt.

Christopher Columbus äggpussel i Sam Loyds Cyclopedia of Puzzles , 1914

År 1914 publiceras Sam Loyds Cyclopedia of Puzzles postumt av hans son (även kallad Sam Loyd). Pusslet förklaras däri enligt följande:

Den roliga gamla kungen försöker nu lägga ett andra pussel, som går ut på att dra en kontinuerlig linje genom mitten av alla ägg för att markera dem med minsta möjliga antal slag. King Puzzlepate utför bedriften i sex slag, men utifrån Tommys uttryck ser vi det som ett väldigt dumt svar, så vi förväntar oss att våra smarta pussellistor ska göra det bättre; [...]

Sam Loyds namngivning av pusslet är en anspelning på historien om Egg of Columbus .

I 1941 års sammanställning The Puzzle-Mine: Puzzles Collected from the Works of the Late Henry Ernest Dudeney , tillskrivs pusslet till Dudeney själv och inte Loyd. ^{[ sida behövs ]}

Lösning

En lösning av pusslet med nio punkter.

Det är möjligt att markera de nio prickarna på fyra rader. För att göra det går man utanför gränserna för det kvadratiska området som definieras av de nio prickarna själva. Frasen tänka utanför ramarna , som användes av managementkonsulter på 1970- och 1980-talen, är en omformulering av lösningsstrategin. Enligt Daniel Kies verkar pusslet svårt eftersom vi vanligtvis föreställer oss en gräns runt kanten på prickarrayen.

Den inneboende svårigheten med pusslet har studerats inom experimentell psykologi .

Att ändra reglerna

Olika publicerade lösningar bryter mot pusslets implicita regler för att uppnå en lösning med ännu färre än fyra rader. Till exempel, om prickarna antas ha en viss ändlig storlek, snarare än att vara oändligt små matematiska rutnätspunkter, är det möjligt att koppla ihop dem med endast tre lätt lutande linjer. Eller, om linjen tillåts vara godtyckligt tjock, kan en linje täcka alla punkter.

Ett annat sätt att använda endast en enda linje innebär att rulla papperet till en tredimensionell cylinder , så att prickarna riktar in sig längs en enda spiral (som, som en geodetisk av cylindern, skulle kunna anses vara en rak linje) . Således kan en enda linje ritas som förbinder alla nio prickarna - som skulle visas som tre parallella linjer på papperet, när de är tillplattade. Det är också möjligt att vika papperet platt , eller att skära papperet i bitar och ordna om det, på ett sådant sätt att de nio prickarna ligger på en enda linje i planet.

Tre linjer förbinder tjocka prickar

Enrads rullad cylinder

Generalisering

Cykliska lösningar för 4-av-4-versionen

Om vi istället för 3 x 3 kvadratgitteret betraktar det $n$ -by- $n$ kvadratiska gittret, vad är då det minsta antalet linjer som behövs för att koppla ihop prickarna utan att lyfta pennan? Eller, uttryckt i matematisk terminologi, vad är den minsta segmenterade enkursala polygonala banan som täcker $n \times n$ -matrisen av punkter?

Olika sådana tillägg angavs som pussel av Dudeney och Loyd med olika tillagda begränsningar.

1955 visade Murray S. Klamkin att om $n > 2$ så räcker $2 n - 2$ linjesegment och förmodade att det också var nödvändigt. 1956 bevisades gissningen av John Selfridge .

1970 visade Solomon W. Golomb och John Selfridge att den unikursala polygonala banan av $2 n - 2$ segment finns på $n \times n$ -matrisen för alla $n > 3$ med den ytterligare begränsningen att banan är stängd , dvs. den börjar och slutar vid samma punkt. Dessutom kan den ytterligare begränsningen att den stängda banan förblir inom det konvexa skrovet av arrayen av punkter uppfyllas för alla $n > 5$ . Slutligen bevisas olika resultat för $a \times b -matrisen av punkter.$

Nio punkters pris

Nio prickar-priset, uppkallat efter pusslet, är ett tävlingsbaserat pris för "kreativt tänkande som tar itu med samtida samhällsfrågor." Det sponsras av Kadas Prize Foundation och stöds av Cambridge University Press och Center for Research in the Arts, Social Sciences and Humanities vid University of Cambridge .

Se även

Anteckningar