Linje mellan motsatta hörn på ytan av en hyperkub?

Jäklar... Tror jag börjar förstå det här.

Naturligtvis ska man tänka sig att man har "vikt upp" alla genomkorsade kvadrater så att de ligger i samma plan! När man väl har gjort det är det uppenbart att den kortaste sträckan måste gå genom alla dessa på samma räta linje -- därför att en sicksack-linje skulle bli längre!

För n=2k+1 kan man lägga ut kvadraterna inom en (k+1)×k area, och dra linjen från nedre vänstra hörnet upp till det övre högra. Denna linjes längd blir
s = √((k+1)²+k²) = ... = √((n²+1)/2) !
Tittar du sen på de genomkorsade kvadraterna kommer du snabbt att kunna identifiera alla stegen i din lösning!

För n=2k lägger man istället ut kvadraterna inom ett k×k område. Avståndet mellan motsatta hörn blir
s = k•√2 = n/√2.

---

Detta kan dessutom generaliseras till [n,3]!
För n=3k+1 tänker vi oss kuber inom en
(k+1)×k×k volym. Sträckan blir nu
s = √((k+1)²+k²+k²) = ... = √((n²+2)/3)
Även här bör vi kunna identifiera koordinaterna i varje steg genom att titta på genomkorsade kuberna. Etc.

Liknande bör kunna göras för [n,d] för alla d...

Lånar denna formatering för att visa vad min nya insikt leder till med [11,3]. 11=4+4+3. Vi drar en rät linje i R^3 från (0,0,0) till (4,4,3) med
(x,y,z) = t•(4,4,3) ; 0 ≤ t ≤ 1
och söker alla t-värden där minst någon av koordinaterna är heltal. Detta händer i turordning för t = 0, ¼, ⅓, ½, ⅔, ¾, 1.
Vi identifierar också (hur det ser ut innan "uppvikning"):
0≤x≤1: x1=x
1<x≤2: x1=1, x4=x-1
2<x≤3: x1=1, x4=1, x7=x-2
3<x≤4: x1=1, x4=1, x7=1, x10=x-3
0≤y≤1: x2=y
1<y≤2: x2=1, x5=y-1
2<y≤3: x2=1, x5=1, x8=y-2
3<y≤4: x2=1, x5=1, x8=1, x11=y-3
0≤z≤1: x3=z
1<z≤2: x3=1, x6=z-1
2<z≤3: x3=1, x6=1, x9=z-2

Vi får då följande tabell för [11,3]:
Längd = √(2•4²+3²) = √41 ~ 6.40.

Metoden ovan går säkert att skriva snyggare på något sätt, samt direkt ge formler för resultaten.

Notera att det med denna metod är lätt att hitta andra lokala minima som dock är längre än den givna metoden.

T ex för [11,3] har vi att 11=5+4+2. Vi kan dra en rät linje från (0,0,0) till (5,4,2) med
(x,y,z) = t•(5,4,2)
med t mellan 0 och 1. Mellan de givna punkterna är den räta linjen förstås kortast.
Och sen söka de t-värden där minst ett av x eller y eller z är heltal. Varje gång x eller y eller z kommer över något heltal så är linjen inne i nästa kub, och vi måste byta till ny koordinat. Exakt i vilken ordning man identifierar x1, x2, x3, etc från x, y, z är egentligen inte så viktigt. Bara om man vill ha en snygg diagonalform i tabellen.

Längden i detta fall blir förstås
√(5²+4²+2²) = 5•√2 = ca 7.07

Dvs [n,d] har lokala minima för alla kombinationer av heltalskombinationer
(x1,x2,...,xd) där x1+x2+...+xd=n. Och dessa längder är √(x1²+x2²+...+xd²).

När jag funderar lite mer på det måste xi även vara positiva och skilda från 0, för att linjen ska röra sig genom d dimensioner och inte mindre i varje steg.

Kan ju också ta ett exempel som INTE är lokalt minimum. Förut trodde jag att den kortaste sträckan för [5,2] kunde ges av
(0,0,0,0,0) --> (1,1,0,0,0) --> (1,1,1,½,0) --> (1,1,1,1,1).
Men enl mitt nya synsätt motsvaras detta av en bruten linje i R^2 mellan (0,0) och (3,2):
Först från (0,0) till (1,1)
Sen från (1,1) till (3,2).
Detta är ju inte den kortaste linjen mellan (0,0) och (3,2) och alltså varken ett lokalt eller globalt minimum.

Smart! För exempelvis n = 3k + 2 och d = 3 blir det alltså raka spåret genom ett rätblock med dimensionerna (k+1)×(k+1)×k, eftersom det har kortast diagonal av alla a×b×c-block där a + b + c = n? Så

(k + 1)² + (k + 1)² + k² = 3*k² + 4*k + 2 = 3*k² + (k*2 + 1)*2 = d*(n/d)^2 + ((n/d)*2 + 1)*(n%d),

i enlighet med formeln Rolvaag0 föreslog. Jag kan se hur samma resonemang leder till den generella formeln.

Det stämmer överens med mina numeriska beräkningar.

Kul att nerdnerd verkade hitta lösningen också. Jag ber om ursäkt för att jag inte hann mer än citera min kompis formel utan att gå igenom hans resonemang. (Jag förstod ändå inte allt han sa så värst väl, för honom var det tydligen uppenbart...).

Applicering av sqrt( M *(N/M)^2 + (N/M * 2 + 1) * (N%M) )
med
N=11, M=3
N%M=2
N/M=3

N=10, M=3
N%M=1
N/M=3

ger också de resultat ni nämnt, e.g. sqrt(3*3^2+(3*2+1)*1)=sqrt(34)~5.83

"
From (0,...) to (1,...) is distance N along the edges -- there are N coordinates that need to be changed.
If all shortcuts are along two-dimensional surfaces, then the best you can do is to move on the diagonal of a rectangle whose two edge lengths add up to N.
And the best such rectangle will be floor(N/2) by ceil(N/2).
So, that would establish a lower bound. To show that it's an upper bound, just demonstrate an unfolding that achieves it.
...
"

(sen generaliserade han det)

Det som iaf är lite intuitivt är fallet för jämna N och M=2, för om man rör sig i kordinatrummet (x1,x2,x3,...,x_n) och bara kan röra två kordinater åt gången kan man förstå att summan av koordinaterna kan öka med max sqrt(2) per enhetssteg av samma anledning som en rak linje är kortaste avståendet mellan (0,0) och (1,1) (och för jämna N kan man bibehålla den vinkeln ända in i mål (0,0,0,0,...) -> (1,1,0,0,...) -> ...)

Precis så! Fast det här vill jag verkligen inte ta åt mig hela äran för. Du lyfte verkligen den här tråden till nya nivåer med dina undersökningar med slumptal och steepest descent. Nu senast var det ffa detta som fick mig på rätt spår:


Tack till dig med! Om inte annat för påminnelsen om att there is always a bigger fish (Qui-Gon Jinn i Star Wars, Episode 1). Han verkar ha varit snabb på att förstå detta. Hälsa gärna.

Jag håller helt med att numeriska undersökningar är bra. De flesta matematik-relaterade problem jag har stött på i verkligheten har sällan haft några enkla analytiska lösningar och då gäller det att vara bra på att programmera. Det är ju rätt bra generell metod. 1) simulera problemet med en dator 2. leta efter mönster 3. förklara mönstret analytiskt om ens möjligt... Ni gjorde ju lite var... jag var också noga med att inte claima credit för andras arbete

Ok, här kommer lösningen i det allmönna [n,d] fallet, för den kortaste banan mellan motsatta hörn i en n-dimensionell hyperkub (n-kub), som bara får gå genom d-dimensionella hyperkuber (d-kuber) på n-kubens hyperyta, med d<n.

k = heltalsdivisionen mellan n och d
m = resten
n = k•d + m = m•(k+1) + (d-m)•k
Den sökta sträckan
s = √(m•(k+1)²+(d-m)•k²)
vilket också motsvarar hyperdiagonalen i ett d-dimensionellt hyperrätblock, med m kanter som är k+1 långa, och d-m kanter som är k långa. Detta rätblock motsvarar en uppvikning till samma R^d hyperyta av alla d-kuber som banan går igenom (motsvarande att t ex klippa upp sidorna runt en kub och platta ut dem på samma plan).

Om m≠0 passerar banan lite snett genom 2k d-kuber. Om m=0 bara k st längs deras hyperdiagonaler. I båda fallen i samma riktning genom alla d-kuber i hyperrätblocket (dvs längs rätblockets hyperdiagonal). Så i DEN meningen (dvs i detta uppvikta läge) har banan samma riktning genom alla passerade d-kuber.

Banan runt n-kuben ges av följande tabell, där varje rad representerar koordinaterna efter varje steg som minst en koordinat har nått sitt max = 1:
där a=1/(k+1), b=1/k och 1≤i≤k. m resp d-m är varje kolumns multiplicitet. Dvs t ex varje m-kolumn står egentligen för m likadana kolumner. Antalet kolumner är alltså egentligen m+k•(d-m+m)=n.
Notera att man i varje steg (varje ny rad) ändrar på m+(d-m)=d koordinater, medan alla de övriga är 0 eller 1. Dvs banan går genom d-kuber som ligger på n-kubens hyperyta.
I vart annat steg når m koordinater maxvärdet 1, och de andra stegen når d-m koordinater maxvärdet 1.
Beräknar man summan av alla 2k delsträckor
Δs = √(Δx₁²+Δx₂²+...+Δxₙ²)
blir det förstås samma resultat som ovan för s.

----

Prydlig lösning. Den här vägen är alltså raka vägen på den utveckling av kuben som Rolvaag0s vän menade behövde demonstreras. Har man svårt att se en sådan utveckling framför sig så är det ju i alla fall tydligt utifrån tabellen att riktningen är samma i varje steg.

Så varför platsar inte svaren sqrt(2+1)=sqrt(3) för 1 dimensioner respektive sqrt(2+0)=sqrt(2) för 0 dimensioner?

Därför att det kan inte finnas -1 eller -2 riktningar.
("I n-2 riktningar går man ett steg och i en går man 2...")

Gammal tråd f ö. Men det var kul att fundera och räkna på! Känns dock som vi uttömde ämnet. Men det kan nog utvidgas ännu mer än det redan gjorts. (Vi fann ju dessutom alla lokala minimal för banor banor som går i d-dimensionella "sid"-kuber runt den n>d-dimensionella hyperkuben.)