Little math problems July 2019
07-28-2019, 07:28 PM
Post: #1
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
Little math problems July 2019
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

Wikis are great, Contribute :)
07-29-2019, 12:51 AM
Post: #2
 mfleming Senior Member Posts: 739 Joined: Jul 2015
RE: Little math problems July 2019
Any restriction on movement, that is, only N/S/E/W moves, or are diagonal moves also allowed?

Remember kids, "In a democracy, you get the government you deserve."
07-29-2019, 06:57 PM
Post: #3
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: Little math problems July 2019
Diagonal is allowed. Of course, one can also propose solutions to variants.

Wikis are great, Contribute :)
07-29-2019, 10:18 PM (This post was last modified: 07-29-2019 10:21 PM by Jim Horn.)
Post: #4
 Jim Horn Member Posts: 198 Joined: Dec 2013
RE: Little math problems July 2019
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!
08-01-2019, 05:04 PM
Post: #5
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: Little math problems July 2019
(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!

Wikis are great, Contribute :)
08-02-2019, 10:08 PM
Post: #6
 Jim Horn Member Posts: 198 Joined: Dec 2013
RE: Little math problems July 2019
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?
08-02-2019, 11:23 PM
Post: #7
 Albert Chan Senior Member Posts: 1,646 Joined: Jul 2018
RE: Little math problems July 2019
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)
08-07-2019, 01:04 AM
Post: #8
 Jim Horn Member Posts: 198 Joined: Dec 2013
RE: Little math problems July 2019
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 -
08-07-2019, 01:23 PM
Post: #9
 John Keith Senior Member Posts: 717 Joined: Dec 2013
RE: Little math problems July 2019
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.
08-07-2019, 01:46 PM
Post: #10
 John Keith Senior Member Posts: 717 Joined: Dec 2013
RE: Little math problems July 2019
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.
08-08-2019, 01:49 AM (This post was last modified: 08-08-2019 05:33 PM by Albert Chan.)
Post: #11
 Albert Chan Senior Member Posts: 1,646 Joined: Jul 2018
RE: Little math problems July 2019
(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%
08-08-2019, 05:24 PM (This post was last modified: 08-13-2019 11:59 AM by Albert Chan.)
Post: #12
 Albert Chan Senior Member Posts: 1,646 Joined: Jul 2018
RE: Little math problems July 2019
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
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)