Problems & Puzzles: Puzzles

Puzzle 311. Sum to a cube Generalizing another Nobuyuki Yoshigahara's puzzle from his previously mentioned beauty book, 'Puzzles 101', I propose this week the following puzzle: Find the least integer n such that you can arrange all the numbers from 1 to n, in a row such that the sum of every two adjacent numbers is a cube. Example of part of a row as that: ....-25-2-6-21-43-...

 

---

Anurag Sahay found one solution for n=386. He says this is the minimal value.

The minimal n is 386 . The permutation is(only the few
terms):

256 87 38 305 207 136 376 353 159 184 328 15 201 311
32 93 250 262 81 44 299 213 130 382 347 165 178 334 9
18 325 187 29 314 198 145 367 362 150 193 319 24 192
320 23 4 339 173 43 300 212 131 381 348 164 52 291 221
122 94 249 263 80 45 298 214 129 383 346 166 177 335 8
19 324 188 28 315 197 146 366 363 149 194 318 25 191
321 22 103 240 272 71 54 289 223 120 96 247 265 78 138
374 355 157 186 326 17 108 235 277 66 59 284 228 115
101 242 270 73 143 369 360 152 64 279 233 110 106 237
275 68 148 364 365 147 196 316 27 189 323 20 105 238
274 69 56 287 225 118 98 245 267 76 49 294 218 125 91
252 260 83 133 379 350 162 181 331 12 113 230 282 61
155 357 372 140 203 309 34 30 313 199 144 368 361 151
65 278 234 109 107 236 276 67 58 285 227 116 100 243
269 74 142 370 359 153 63 280 232 111 14 329 183 160
352 377 135 208 304 39 86 257 255 88 128 384 345 167
176 336 7 57 286 226 117 99 244 268 75 50 293 219 124
92 251 261 82 134 378 351 161 182 330 13 51 292 220
123 2 341 171 172 340 3 5 338 174 42 301 211 132 380
349 163 180 332 11 205 307 36 89 254.....
 

***

Giovanni Resta found one week later a smaller solution than the obtained by Anurag.

Resta also thinks that this new solution is the minimal one. But the more interesting of his solution is the method he has employed, a method that links this problem to another more general, named 'TSP' (Traveler Sales Problem):

I think I found the minimal solution for Puzzle 311. If I'm not wrong, it is not n=386 as A.Sahay stated, but n=305, in a row. The solution is the following:

256 87 129 214 298 45 171 172 44 299 213 130 86 257 255 88 128 215 297
46 170 173 43 300 212 131 85 258 254 89 127 216 296 47 169 174 42 301
211 132 84 259 253 90 126 217 295 48 168 175 41 302 210 133 83 260
252 91 125 218 294 49 167 176 40 303 209 134 82 261 251 92 33 183 160
56 287 225 118 98 245 267 76 140 203 13 14 202 141 75 268 244 99 26 190 153 63 280 232 111 105 238 274 69 147 196 20 7 1 124 219 293 50
166 177 39 304 208 135 81 262 250 93 32 184 159 57 286 226 117 8 19
197 146 70 273 239 104 112 231 281 62 154 189 27 37 179 164 52 291
221 122 3 5 22 194 149 67 276 236 107 109 234 278 65 151 192 24 101
242 270 73 143 200 16 11 205 138 78 265 247 96 120 223 289 54 162 181
35 29 187 156 60 283 229 114 102 241 271 72 144 199 17 108 235 277 66 150 193 23 4 121 222 290 53 163 180 36 28 188 155 61 282 230 113 103 240 272 71 145 198 18 9 116 227 285 58 158 185 31 94 249 263 80 136 207
305 38 178 165 51 292 220 123 2 6 21 195 148 68 275 237 106 110 233 279
64 152 191 25 100 243 269 74 142 201 15 12 204 139 77 266 246 97 119 224
288 55 161 182 34 30 186 157 59 284 228 115 10 206 137 79 264 248 95

I have attached a small Excel file which contains the solution and also shows all the sums and all the cubic roots of the sums, so that one can easily check that this is indeed a solution.

In the case someone is interested here is how I proceeded.
First of all I've tried a very simple recursive program which given a certain n exaustively (by backtracking) construct the longest possible sequence which satisfy the constraint.
That program was very short and fast to write, but unfortunately not able to find a solution, since around n=200 it became too slow.

The program itself was correct and I was able to find solutions for different easier constraint. For example, if we want that the sum is a square, then the minimal solution is n=15.
if we want that the sum is triangular number then the minimal n is
9 (5 1 9 6 4 2 8 7 3).
if we want that the sum is a power with exponent greater of equal to 3, then n=23 (8 19 13 3 5 22 10 17 15 1 7 20 12 4 23 9 18 14 2 6 21 11 16).

When I've seen the solution of Sahay I understood that a different approach was in order.
After a little thought, I've seen that indeed this problem can be reduced to a TSP problem which is a well know problem for which good codes can be found on internet (I used the one named Concorde).

A TSP problem (Traveling salesman problem) consists in a number of cities whose mutual distances are known. We want to find a tour that touches all the cities exactly once (returning to the city of origin) and has minimal length.

Our problem can be reduced to TSP in this way:
given n, we consider a TSP with n cities.
The distance of city x from city y is 1 if x+y is a cube and
2 otherwise. The reason of the weight 2 will be clear soon.
So, if given n we construct a TSP and we solve it exactly we can have 3 possibilities, with respect to the length of the optimal tour.

If the optimal tour has length n, then
we have used only edges of lenght 1 (in the circuit there are always n
edges) this means that not only we have a solution to the problem, but also the fist and last number have a sum which is a cube.

If the optimal tour has length n+1 then we have n-1 edges of length 1 and one edge of length 2 (which does not satisfy the constraint). To obtain the wanted solution it is enough to "open" the TSP solution breaking the edge with weight 2: its nodes will correspond to the first and last number of the solution we want.

If the optimal tour has a length greater than n+1 this means the solver was forced to use more than one edge with length 2: hence there are no solutions of our problem with that n.

Up to the dimension n=386, the Concorde TSP Code is fast enough to find optimal solutions in few seconds, so in very little time, repeating the search for the various n, I was able to find the above solution for n=305, which, errors apart, should be the minimal one.
 

On my request, Giovanni also solved the minimal solution for n numbers in a circle:

n minimal, in a circle, = 473
==========================================================
1 7 209 303 426 86 130 382
347 165 178 334 395 117 226 286
443 69 56 456 273 239 104 408
321 191 25 2 6 210 302 427
85 131 381 348 164 52 460 269
243 100 412 317 195 21 43 469
260 252 91 421 308 204 139 373
356 156 187 325 404 108 235 277
452 60 65 447 282 230 113 399
330 182 34 30 313 416 96 247
265 464 48 77 435 294 218 125
387 342 170 173 339 390 122 221
291 438 74 51 461 268 244 99
413 316 27 189 154 358 371 141
202 14 13 203 309 420 92 251
261 468 44 81 431 298 214 129
383 346 166 177 39 473 256 87
425 304 208 135 377 352 160 183
329 400 112 231 281 448 64 152
360 369 143 73 439 290 222 121
391 338 174 169 343 386 126 217
295 434 78 47 465 264 248 95
417 312 200 16 11 205 138 374
355 157 186 326 403 109 234 278
451 61 155 357 372 140 76 436
293 219 124 388 341 171 172 340
389 123 220 292 437 75 50 462
267 245 98 414 315 197 19 8
335 394 118 225 287 442 70 146
366 363 149 67 445 284 228 115
397 332 180 163 349 380 132 211
5 22 194 318 411 101 242 270
459 53 72 440 289 223 120 392
337 175 168 344 385 127 216 296
433 79 46 466 263 249 94 418
311 32 184 328 401 111 232 280
449 63 62 450 279 233 110 402
327 185 31 33 310 419 93 250
262 467 45 80 432 297 215 128
384 345 167 49 463 266 246 97
415 314 29 35 181 162 350 379
133 83 429 300 212 4 23 320
409 103 240 272 457 55 161 351
378 134 82 430 299 213 3 24
192 151 361 368 144 199 17 10
206 137 375 354 158 58 454 275
237 106 406 323 20 196 147 365
364 148 68 444 285 227 116 396
333 179 37 306 423 89 254 258
471 41 84 428 301 42 470 259
253 90 422 307 36 28 188 324
405 107 236 276 453 59 66 446
283 229 114 398 331 12 15 201
142 370 359 153 190 322 407 105
238 274 455 57 159 353 376 136
207 9 18 198 145 367 362 150
193 319 410 102 241 271 458 54
71 441 288 224 119 393 336 176
40 472 257 255 88 424 305 38
26
 

***

On October 2005, Anurag Sahay wrote:

This is the year 2005 and here is a solution for n=2005( takes around 45 minutes on a 1GHz cpu). To find a solution for n=4000 , I need 3 GB of RAM !.[solution available on request]

***

 

---