Little math problems July 2019

[pier4r]

After quite an absence due to work and life, absence that may continue a bit more (I should read all the posts that got updated after the first week of May), I would like to drop a little problem that I find interesting.

You may know age of empires, well one can extract many interesting problems from strategy games. The problem is to see them.

One of those is the question: ok, there is a grid (a matrix), an object start in the middle of it (or in the 4 middle positions), then moves to the center of each other square, does an action for a certain time (chopping), and then comes back.

The problem is: how much time it takes to visit all the grid locations, provided that it goes always back to the center of the matrix/grid, and once returned to the center, it goes visiting the nearest non-visited square. The time problem is an indirect problem of the question I want to pose here. The sum of all distances.

Of course it can be done programmatically (it is a nice intensive task for the calculator), but is there a less "brute force" formula for it? Aside from basic ideas like computing the distances only for a quadrant of the matrix, that reduces the computation by a factor of four.

I tried with some friends and we didn't see any better than, at the end, a long list of terms in a summation. Even in a continuous case, we didn't make much progress. For example in the continuous case one can say "ok I have concentric circles, thus I have the sum of the radiuses multiplied by the number of the points on the circles" but, yeah, the points are infinite so it doesn't work.

If the problem is not clear, please ask so I'll try to clarify. Although the youtube video below can help plenty.

source: https://youtu.be/_UEPVFjNgfs

[mfleming]

Any restriction on movement, that is, only N/S/E/W moves, or are diagonal moves also allowed?

[pier4r]

Diagonal is allowed. Of course, one can also propose solutions to variants.

[Jim Horn]

If you restrict motion to orthogonality only, the total distance traveled is x^3 - x, where "x" is the number of squares on a side. Vielen Dank!

[pier4r]

(07-29-2019 10:18 PM)Jim Horn Wrote:  If you restrict motion to orthogonality only, the total distance traveled is x^3 - x, where "x" is the number of squares on a side. Vielen Dank!

May I ask you to expose the reasoning behind your result? Thanks for the contribution!

[Jim Horn]

My pleasure. As a first approximation, the total distance should approach a constant times the size cubed, as the number of cells approaches the size squared and the average distance to each approaches the size. Multiplied, that gives you the size cubed.

The distance for each cell is two identical distances, namely out and back. We can simplify by just counting one and doubling.

Similarly, each n x n square consists of four (n-1)/2 x (n+1)/2 areas that cover the square without overlap and only leave out the central square, for which no travel is needed. So if we find the distance out to each square in one area, we can multiply the sum of those by 8 to get the final number. Only having to count 1/8th of the steps makes doing so faster, easier and less error prone!

It's a quick task to do that for squares of size 1, 3, 5, 7 and 9. Then do a polynomial fit to that and you find that indeed, the coefficients are 0, 1, 0, -1 and 0, giving you x^3 - x, as mentioned.

In doing the area distances mentioned two paragraphs above, I noticed a simple recurrence relation that gave the total distance for any given size from the total of the next smaller size. Dropping that into the above polynomial gives the same result, confirming its validity.

Way back in the 1960s, Martin Gardner's "Mathematical Games" column in Scientific American (and one of his marvelous books) discussed the Calculus of Finite Differences. It's a simple and very effective tool for diving into many problems like this and finding their general solutions.

I suspect the same approach can be used to find the total distance if diagonal paths are allowed if the diagonals are limited to 45 degree ones. For any diagonal (i.e. straight line from center cell to any other), I suspect this won't give exact results but may help with a sufficient approximation. Anyone want to give it a try?

[Albert Chan]

Hi, Jim Horn

Thanks !

Consider only 1 of the 4 rectangle, size n x (n+1), total 1-way distance traveled f(n)

XCas> f(n) := sum(sum(a+b, a = 1 .. n), b = 0 .. n) // → n*(n+1)*(2n+1)/2
XCas> n := (x-1)/2         // since x = n + (n+1)
XCas> expand( 8*f(n) )   // → x³ - x

Trivia, f(n) happened to be 3 * sum(k^2, k=1 .. n)

[Jim Horn]

Hello, Albert,

Wow - great posting! I've not made use of the 50g's CAS and considered breaking out my Surface Pro and Mathematica to approach the problem much as you show. But I was in a slow meeting so pen, notepad and '50g matrix math did the job. I really like the elegance of your XCas solution! And would never have noted the "trivia" you found.

Best to you -

[John Keith]

Brute-force program for the diagonal case, odd sizes only. Exact mode for symbolic results:

Code:


\<< \-> n
  \<< n DUP NEG SWAP
    FOR x n DUP NEG SWAP
      FOR y x SQ y SQ + \v/
      NEXT
    NEXT n 2 * 1 + SQ \->LIST \GSLIST EVAL 2 * EVAL
  \>>
\>>

First few results:

3: '8+8*√2' ~19.314
5: '24+24*√2+16*√5' ~93.718
7: '48+48*√2+(16+16*√2)*√5+16*√13' ~259.94
9: '160+80*√2+(48+16*√2)*√5+16*√13+16*√17' ~554.72


I will leave it to the "big brains" here to derive a general formula.

[John Keith]

Diagonal case, even sizes assuming that all squares bordering the 4 center squares are considered to be a distance of 1 or √2 from the center:

Code:


\<< \-> n
  \<< 0 n 
    FOR x 0 n 
      FOR y x SQ y SQ + \v/
      NEXT
    NEXT n 1 + SQ \->LIST \GSLIST EVAL 8 * EVAL
  \>>
\>>

4: '16+8*√2' ~27.313
6: '48+24*√2+16*√5' ~117.72

...etc. Expressions are the same as for size n-1 except for the additive term being doubled.

[Albert Chan]

(08-07-2019 01:23 PM)John Keith Wrote:  Brute-force program for the diagonal case, odd sizes only. Exact mode for symbolic results:

First few results:

3: '8+8*√2' ~19.314
5: '24+24*√2+16*√5' ~93.718
7: '48+48*√2+(16+16*√2)*√5+16*√13' ~259.94
9: '160+80*√2+(48+16*√2)*√5+16*√13+16*√17' ~554.72

Compared against X^3-X, direct-route distance savings:

3: 19.53%
5: 21.90%
7: 22.64%
9: 22.96%

Distance saving plateaued after that, with maximum savings of 23.48% for huge X

Update: maximum saving rate calculated by switching sums to integral.
XCas> d := 8*int(int(sqrt(a*a+b*b), a= -1/2 .. x/2), b= 1/2 .. x/2)
XCas> limit(1 - d/(x^3-x), x=inf) → ln(√(2)-1)/3 + (-√(2)+3)/3 ≈ 23.48%

[Albert Chan]

If only orthogonal and 45 degree diagonal moves allowed:

total distance = k*(X³ - X), where k = (1+√2)/3 ≈ 80.47%

Compare against orthogonal moves only, distance saving = (2-√2)/3 ≈ 19.53%

Prove:
Trivia 1: total orthogonal moves = total diagonal moves
Trivia 2: diagonal move equivalent to 2 orthogonal moves
Trivia 3: from post #7, f(n) = (X³ - X)/8, divisible by 3

→ k = (1+√2) / (1+2) = (1+√2)/3