Terning og kvadrater

[LAMBRIDA]

Er det noen som vil bryne seg på denne oppgaven?


Et sett kubiske byggeklosser har akkurat så mange klosser som trengs for å bygge enten en serie av hele kvadrater som følger like etter hverandre i størrelse eller en stor terning.
Kva er det minste antall byggeklosser det kan være snakk om for å løse oppgaven?

[Nebuchadnezzar]

Vet du om oppgaven er løsbar, etter litt smart tenking. Og litt harbarket programmering, kom jeg frem til at det er ingen løsning om du bruker mindre enn en million blokker :p

Så utifra mine data tviler jeg sterkt på at oppgaven er løsbar. Forutsetter selvfølgelig at jeg har regnet riktig, oppfattet oppgaven på rett måte osv.

[LAMBRIDA]

Oppgaven er løsbar med den riktige programmering i Excel.,Dette fikk jeg en kollega av meg til å gjøre og det ble mange utskriftpapirer.,Kanskje kan man se løsningen uten utskrift, akkurat det vet jeg ikke.

[Knuta]

Har jeg forstått deg rett?

f.eks. en terning med sidelengde 65 (274625 klosser) kan legges ut i kvadrater som starter med sidelenge 90 og avslutter på 155 (90^2+91^2+ ......... +154^2+155^2) ?

I så fall er eksempelet er ikke den minste jeg fant.

[LAMBRIDA]

Du har forstått oppgave rett.
Jeg skal sjekke dette som du kom med her, men det er hvertfall ikke den minste løsningen.

[Knuta]

Det tok meg ca. 3 minutter å programmere en (elendig dårlig) snutt som kjørte i 1/2 sekund for å finne alle (2 stk.) løsninger med en kube med sideflater under 100.

Finnes det en løsning på problemet der det går ann å regne det ut i stedet for brute force? Problemet med tiden eskalerer sterkt når antallet i sidelengden øker. Det går ann å lage bedre rutiner men det er bare en forskyvning av problemet.

[LAMBRIDA]

Hvor mange byggeklosser har du på den minste løsningen da.,Etter som jeg fikk den forrige løsningen av deg , så gikk det opp for meg hvordan man finner enda flere slike løsninger.,Dette skal jeg se nærmere på.

[LAMBRIDA]

Jeg har undersøkt terningen med sider på 65.,Det viser seg at det antall byggeklosser i den tilsvarer ikke summen av kvadratene 90 til og med 155, for summen av disse er 1014365 mot terningen som har 274625.

[Knuta]

47 på sidelengde kube og kvadratene fra 22 til 68 i sidelengde. 103823 klosser totalt.

Etterhvert har jeg kommet fram til en ligning.
k^3 = ( b(b+1)(2b+1) - a(a-1)(2a-1) ) / 6
der
k = sidelenge på kuben
a = sidelengde på minste kvadrat
b = sidelengde på største kvadrat

Dersom det er av interesse så kan jeg modifisere programmet med hensyn til ligningen og kjøretiden blir redusert med en faktor som øker. Men igjen tiden blir et problem ved noe høyere tall. Så lang har jeg ikke funnet andre løsninger under 200 på sidelengden til kuben.

[LAMBRIDA]

Dette er riktig, men jeg har ikke funnet en formel eller metode som gir flere løsninger på dette ennå.,Så viss du har eller finner ut noe, så er jeg veldig interessert.

[Knuta]

Satte opp en liten kode i Mathematica:

Table[{x,
FindInstance[
x^3 == 1/6 (-(-1 + a) a (-1 + 2 a) + b (1 + b) (1 + 2 b)) &&
a > 1 && b > a, {a, b}, Integers]}, {x, 1, 1200}]

Resultatet ble 3 løsninger sidelengde kube <=1200
{47, {{a -> 22, b -> 68}}}
{65, {{a -> 90, b -> 115}}}
{921, {{a -> 2115, b -> 2276}}}

[LAMBRIDA]

Jeg takker og er veldig imponert.

[Knuta]

Mathematica er litt treg på slike oppgaver. Den brukte ca. 20 minutter på sjekke muligheten opptil 1200. Så jeg tok fra pascalkoden igjen, modifisert den og lot den kjøre i 20 minutter. Da fikk jeg 5 løsninger opp til 7000 på 20 minutter. Deretter begynte det å gå veldig tregt.

Hvis jeg oppgir k finner du da a og b?

k=47, a=22, b=68
k=65, a=90, b=115
k=921, a=2115, b=2276
k=2161, a=?, b=?
k=2820, a=?, b=?

For hvis du finner en effektiv metode som gir svaret på en enkel beregning, så kan programmet modifiseres til å bli mer effektiv og muligheten for å finne alle løsninger for k < 1664511. Tallet baserer seg på (Longint div 2)^(1/3)

[Knuta]

Fant du ut noe mer? Jeg effektiviserte koden litt og følgende tall dukket opp i løpet av 20 minutter:

47, 22, 68
65, 90, 115
921, 2115, 2276
2161, 989, 3149
2820, 261, 4067
12284, 23017, 26087
13156, 17354, 22930
16761, 24978, 30971
18340, 125090, 125482

[LAMBRIDA]

Virkelig interessant å se disse etterfølgende løsningene.,Dette imponerte meg enda mer.
Jeg har flere slike oppgaver, men før jeg kommer med en ny vil jeg helst spørre deg om det er av interesse, slik at jeg kan tenke på å poste ei til.