Here's a poser for any mathematician. If a "valid route" between any two stars "A" and "B" is defined as one where for every successive waypoint the distance to "B" is always less than the distance at the previous waypoint, how many valid routes are there between Sol and Sag A*? I have no idea what the answer is to this or even how to go about estimating it, but I suspect it is going to be some number than makes 400 billion look small. What are the odds of any two commanders following the same route? (I think we can forget about that!)
Mathematical Challenge
- Thread starter DMFW
- Start date
Zero, but approaching one the more it's talked about. Say it's impossible long enough and two people will wing up and Buckyball it.
I think the definition you're using allows for the possibility of spiralling around the galaxy repeatedly, moving almost entirely orthogonal to a line towards the Core; to properly estimate I guess we'd need a lot of measurements of density and a better understanding of the virtual galaxy's large-scale structure (I'm working on these... slowly, like everything else I'm working on
); you're right that it would be immense. The question is sensible but the solution isn't, if that makes sense...
Last edited:
Actually, I think it's 47 when accounting for inflation...and routes that take you through beagle point first.
If I understand you correctly, the question is A->A', A'->A'',...,A-A(n+1). Such that A(n-1)->A > A->A(n+1)
If this is the case, then you'd need to start out with much larger jump range than is currently possible, otherwise your trip would end very quickly.
Assume for a moment that your range is decreasing in 0.1 LY increments and your jump range is 40 LY. After 399 jumps, you'd be stuck at a max range of 0.1LY. You'd be trapped inside a single system long before then!
Actually given the average exploration range of 32 LY, and the fact that jump range differential between available nearby systems is usually a bit larger than 0.1 LY, particularly as the range decreases and the options narrow, and even more so if you are headed in a general direction, Whiterose is pretty close to the mark with his initial guess of 42. But only because that is the number of jumps you could make before you were stuck.
-A(n+1). Such that A(n-1)->A > A->A(n+1)If this is the case, then you'd need to start out with much larger jump range than is currently possible, otherwise your trip would end very quickly.
Assume for a moment that your range is decreasing in 0.1 LY increments and your jump range is 40 LY. After 399 jumps, you'd be stuck at a max range of 0.1LY. You'd be trapped inside a single system long before then!
Actually given the average exploration range of 32 LY, and the fact that jump range differential between available nearby systems is usually a bit larger than 0.1 LY, particularly as the range decreases and the options narrow, and even more so if you are headed in a general direction, Whiterose is pretty close to the mark with his initial guess of 42. But only because that is the number of jumps you could make before you were stuck.
Last edited:
I believe it is a number so big only Brian Cox can attempt to say it.
If I understand you correctly, the question is A->A', A'->A'',...,A
If this is the case, then you'd need to start out with much larger jump range than is currently possible, otherwise your trip would end very quickly.
Assume for a moment that your range is decreasing in 0.1 LY increments and your jump range is 40 LY. After 399 jumps, you'd be stuck at a max range of 0.1LY. You'd be trapped inside a single system long before then!
Actually given the average exploration range of 32 LY, and the fact that jump range differential between available nearby systems is usually a bit larger than 0.1 LY, particularly as the range decreases and the options narrow, and even more so if you are headed in a general direction, Whiterose is pretty close to the mark with his initial guess of 42. But only because that is the number of jumps you could make before you were stuck.
Nice answer, but actually I wasn't thinking of anything quite so complicated
- merely trying to express the constraint that the journey must make progress at every step i.e. that it is an invalid route if for any given jump we are further away from our target after the jump than we were before and so eliminating "stupid" routes. I believe this is also necessary to result in a finite answer. Having said that as Jackie Silver says, it would include routes where progress was as slow as you like provided it was progress and therefore all sorts of very big spirals. There is some number out there which categorises this but I think it is incalculable (actually of course it does depend on maximum jump range; the larger the range the MORE routes there are because all routes containing shorter jumps are still possible for the longer range jumping ship but not visa versa)
Last edited:
Yep. I just like thinking about big numbers and how they might be calculated or even estimated to an order of magnitude. And when 400 billion seems small you can always contemplate possible routes
Haven't a clue how you would start with estimating this though...
Last edited:
Tbh, what you are asking is far more complicated. That is why the route plotter only does max or economical, and not a mix of the two. What you are suggesting would probably require a super computer to calculate.
A simpler pathing algorithm would be to simply draw a straight line between A and B and bias the waypoints closest to that line along the path at the longest jump range available.
A simpler pathing algorithm would be to simply draw a straight line between A and B and bias the waypoints closest to that line along the path at the longest jump range available.
Last edited:
When I was at school doing my Physics exam in the 4th year (year 10 now) there was a question asking what the critical angle of light entering glass was. I couldn't remember the answer so jokingly put 42; go look it up...
I came top of the year with 1/2% higher than the next person.
Thank you Douglas.
Zero divided by zero....
But seriously I would say the 'figure' would probably be approaching infinity.
But seriously I would say the 'figure' would probably be approaching infinity.
Last edited:
Theoretically you could enumerate them all. At each star, you just identify the possible jumps that are closer to the target and each one is a new branch... Then keep branching recursively for a very long time and count how many branches you have. I am going to guess that the answer might be close to the number of possible games of chess which you can think about in a similar way; each possible move generates a new branch until you reach checkmate, one of the draw conditions or importantly exceed the "50 move" rule which makes the answer finite (all be it mind boggling huge). The answer to that one is supposed to be the Shannon Number, currently estimated to be 10 to the power of 40:-
https://en.wikipedia.org/wiki/Shannon_number
I suspect that the "Elite Sol to Sag A path number" is bigger but I might be wrong. It's probably comparable. Of course for any given maximum jump distance only one route would be the shortest and one the longest possible. I wonder what those would be...
https://en.wikipedia.org/wiki/Shannon_number
I suspect that the "Elite Sol to Sag A path number" is bigger but I might be wrong. It's probably comparable. Of course for any given maximum jump distance only one route would be the shortest and one the longest possible. I wonder what those would be...
Last edited:
With no restriction on jump range, the longest route could take in every single star system within the radius of Sol's galactic orbit, ranked in order of descending distance to Sadge.
Here we are 20,000 ly away, we jump right across the galaxy to one 19,999.9 ly away, repeat...
Here we are 20,000 ly away, we jump right across the galaxy to one 19,999.9 ly away, repeat...
Dammit, make me do math while I'm racing back to inhabited space...!
Anyway, I can give an upper bound on that by saying what the number of routes could be with a ship with infinite jump range: in that case, it would be 2^(N), with N being the number of stars between your origin and destination. Since the order of the stars is fixed, it simply becomes a case of whether a star is on the route or not.
Now, we can reduce that somewhat with some assumptions: that a ship has a limited jump range, that a ship will almost certainly jump within 10 ly of that jump range, and that, as a result, there is likely to be a certain number of jumps - which we designate as J. (J would be somewhere around 650-675 for a racing Anaconda, depending on whether or not your name is Alot.) For the ith jump, with i having a value between 1 and J, there will be a set of stars within that 10ly band; we can assume that, for that number jump, the number of stars will remain relatively constant, regardless of the origin star (in other words, there's not a lot of difference in star density between 13,000 north of Sol, and 13,050 north of Sol). In this case, we designate n[SUB]i[/SUB] stars for the ith jump. Now, n[SUB]i [/SUB]can vary depending on i anywhere between 1 (if we were out beyond the Abyss) to several dozen (likely for the areas near Sol) to many thousands (the Core). But, once that number is estimated for each jump, then the number of different routes simply becomes the product, for i=1:J, of n[SUB]i
[/SUB]There is a tendency to want to overcomplicate this problem, worrying that choosing one star will affect the choices from that point. Well, yes, they will. However, it should not have a significant effect on the number of choices from that point - which is what we are most concerned with.
Hope this helps!
Anyway, I can give an upper bound on that by saying what the number of routes could be with a ship with infinite jump range: in that case, it would be 2^(N), with N being the number of stars between your origin and destination. Since the order of the stars is fixed, it simply becomes a case of whether a star is on the route or not.
Now, we can reduce that somewhat with some assumptions: that a ship has a limited jump range, that a ship will almost certainly jump within 10 ly of that jump range, and that, as a result, there is likely to be a certain number of jumps - which we designate as J. (J would be somewhere around 650-675 for a racing Anaconda, depending on whether or not your name is Alot.) For the ith jump, with i having a value between 1 and J, there will be a set of stars within that 10ly band; we can assume that, for that number jump, the number of stars will remain relatively constant, regardless of the origin star (in other words, there's not a lot of difference in star density between 13,000 north of Sol, and 13,050 north of Sol). In this case, we designate n[SUB]i[/SUB] stars for the ith jump. Now, n[SUB]i [/SUB]can vary depending on i anywhere between 1 (if we were out beyond the Abyss) to several dozen (likely for the areas near Sol) to many thousands (the Core). But, once that number is estimated for each jump, then the number of different routes simply becomes the product, for i=1:J, of n[SUB]i
[/SUB]There is a tendency to want to overcomplicate this problem, worrying that choosing one star will affect the choices from that point. Well, yes, they will. However, it should not have a significant effect on the number of choices from that point - which is what we are most concerned with.
Hope this helps!
With no restriction on jump range, the longest route could take in every single star system within the radius of Sol's galactic orbit, ranked in order of descending distance to Sadge.
Here we are 20,000 ly away, we jump right across the galaxy to one 19,999.9 ly away, repeat...
Very nice, because that not only simplifies the problem, it also creates an upper bound. If there is no restriction on range, then the problem is reduced to single dimensional set with the dimension being "individual distance from Sgr A*". Every sequential jump reduces the range and thus population of stars to jump to.
Hence the solution is to find the total possible unique linear pairings of the numbers in the set in order of distance from Sgr A* is simply
N = (n-1) + (n-2) + (n-3) +... + (1-0) = n(n-1)/2
Since n ~= 140,000,000,000 stars
Which is N ~ 0.5*(140,000,000,000)^2 ~ 10^22
Now if we have limited range, then the total number of sequential pairings based on range is a number less than 10^22. Because each subsequent pairing will be a tiny fraction of (n-1).
However this still isn't the answer, since you'd have to iterate the problem again to come up with solutions that excluded all the possible rejected pairings. And now my head hurts, so I'll pass the baton.
An upper bound
That's good analysis from everyone. I'm liking this team work maths thing! So following along with the unlimited jump range as an upper bound (which definitely simplifies things) another way of thinking about it would be if there are a set of N stars, the number of routes resolves to the total number of subsets that can be constructed from this set. Any subset is valid but crucially it is only valid ONCE when it is ordered from greatest to shortest distance. This takes away the problem of ordering the elements and we just have to count the number of possible sets of two stars in N, then add the number of possible sets of three stars in N, then four stars in N, etc... etc... up to all N stars (just 1). Every possible route is then counted once and only once.
So isn't this just the sum of a series of combination formulae?
http://www.mathwords.com/c/combination_formula.htm
Totally cribbing the answer for a combination from that web site (since I'd forgotten that formula for a combination) the upper bound for the answer is then :-
The sum of N!/2!(N - 2)! + N!/3!(N - 3)! + N!/4!(N - 4)! +.... where the constant 1,2,3,4 etc... increases from 1 to N until we reach + N!/N!(N - N)!
That last term looks a bit odd but evaluates to 1 because 0! is 1 (see this if you don't believe me https://www.youtube.com/watch?v=Mfk_L4Nx2ZI), so the combination calculation just tells us there is only one way of making a subset of the full set of stars which includes all the stars. That is kind of obvious and what we'd expect.
The whole series probably simplifies to something if your maths is better than mine but now my brain is hurting. It's a huge number because it has 400 billion additions of numbers that start out as 400 billion factorial before they are divided by something different in each term of the series.
It's DEFINTELY less than 400 billion * factorial of (400 billion) though, since that would be the answer without any of the dividing. So that is a relatively simple real number to calculate (for some value of simple) that is well above the upper bound, in the worst case where we are looking for routes from the furthest star to the core and with unlimited jump distances.
Someone should be able to get the smaller number that is the real sum of the series. Possibly
That's good as far as it goes but then I think to reduce the numbers for real jump distances the strategy Hanikura Shizuka was suggesting is probably the way to go...
That's good analysis from everyone. I'm liking this team work maths thing! So following along with the unlimited jump range as an upper bound (which definitely simplifies things) another way of thinking about it would be if there are a set of N stars, the number of routes resolves to the total number of subsets that can be constructed from this set. Any subset is valid but crucially it is only valid ONCE when it is ordered from greatest to shortest distance. This takes away the problem of ordering the elements and we just have to count the number of possible sets of two stars in N, then add the number of possible sets of three stars in N, then four stars in N, etc... etc... up to all N stars (just 1). Every possible route is then counted once and only once.
So isn't this just the sum of a series of combination formulae?
http://www.mathwords.com/c/combination_formula.htm
Totally cribbing the answer for a combination from that web site (since I'd forgotten that formula for a combination) the upper bound for the answer is then :-
The sum of N!/2!(N - 2)! + N!/3!(N - 3)! + N!/4!(N - 4)! +.... where the constant 1,2,3,4 etc... increases from 1 to N until we reach + N!/N!(N - N)!
That last term looks a bit odd but evaluates to 1 because 0! is 1 (see this if you don't believe me https://www.youtube.com/watch?v=Mfk_L4Nx2ZI), so the combination calculation just tells us there is only one way of making a subset of the full set of stars which includes all the stars. That is kind of obvious and what we'd expect.
The whole series probably simplifies to something if your maths is better than mine but now my brain is hurting
. It's a huge number because it has 400 billion additions of numbers that start out as 400 billion factorial before they are divided by something different in each term of the series. It's DEFINTELY less than 400 billion * factorial of (400 billion) though, since that would be the answer without any of the dividing. So that is a relatively simple real number to calculate (for some value of simple) that is well above the upper bound, in the worst case where we are looking for routes from the furthest star to the core and with unlimited jump distances.
Someone should be able to get the smaller number that is the real sum of the series. Possibly
That's good as far as it goes but then I think to reduce the numbers for real jump distances the strategy Hanikura Shizuka was suggesting is probably the way to go...
Last edited:
OK, I've cheated again, since I reckoned the internet would have the answer to the total number of subsets in a set question and sure enough:-
https://www.boundless.com/algebra/textbooks/boundless-algebra-textbook/sequences-series-and-combinatorics-8/the-binomial-theorem-58/total-number-of-subsets-245-5545/
The answer is 2^N (which is what Hanekura Shizuka said above, only I've just caught up with why!)
So the upper bound answer as above is 2 to the power of 400 billion. That's quite big. It must get cut down to something much smaller when jump distances are realistic.
https://www.boundless.com/algebra/textbooks/boundless-algebra-textbook/sequences-series-and-combinatorics-8/the-binomial-theorem-58/total-number-of-subsets-245-5545/
The answer is 2^N (which is what Hanekura Shizuka said above, only I've just caught up with why!)
So the upper bound answer as above is 2 to the power of 400 billion. That's quite big. It must get cut down to something much smaller when jump distances are realistic.
Last edited: