+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: Little math problems July 2019 (/thread-13364.html)
Little math problems July 2019 - pier4r - 07-28-2019 07:28 PM
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
RE: Little math problems July 2019 - mfleming - 07-29-2019 12:51 AM
Any restriction on movement, that is, only N/S/E/W moves, or are diagonal moves also allowed?
RE: Little math problems July 2019 - pier4r - 07-29-2019 06:57 PM
Diagonal is allowed. Of course, one can also propose solutions to variants.
RE: Little math problems July 2019 - Jim Horn - 07-29-2019 10:18 PM
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!
RE: Little math problems July 2019 - pier4r - 08-01-2019 05:04 PM
(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!
RE: Little math problems July 2019 - Jim Horn - 08-02-2019 10:08 PM
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?
RE: Little math problems July 2019 - Albert Chan - 08-02-2019 11:23 PM
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)
RE: Little math problems July 2019 - Jim Horn - 08-07-2019 01:04 AM
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 -
RE: Little math problems July 2019 - John Keith - 08-07-2019 01:23 PM
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.
RE: Little math problems July 2019 - John Keith - 08-07-2019 01:46 PM
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.
RE: Little math problems July 2019 - Albert Chan - 08-08-2019 01:49 AM
(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%
RE: Little math problems July 2019 - Albert Chan - 08-08-2019 05:24 PM
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