This was in a special Mind Games suppliment to Discover magazine. I couldn’t figure out the answer and the answer page didn’t give the full solution! To somewhat paraphrase the puzzle, seven adjacent star systems are at war. Each launches an atttack on it’s nearest neighbor. No two of the seven stars are the same distance apart. Will any of the seven be unscathed?
About all I could figure out was that of the 21 interstar routes, one would have to be the shortest, so those two systems would launch their atttacks at each other. All the answer page tells me is that given that, it can then by extension be shown that one star system won’t be attacked. But I haven’t a clue what the logic is. I can contrive a situation where one system gets ganged up on by all the others, but I don’t have a general solution.
Geez, that depends on a whole host of information not given. Are we thinking in three dimensions or two? Was there a drawing given?
But yes, it’s definitely possible. For instance.
a
b c x
d e
f
In this scenario,
A: B/C
B: C/D
C: A/D
D: C/F
E: C/F
F: B/C
X: E/A
In this scenario, nobody attacks X. Depending on the weighting of “adjacent” star systems, sure, it works.
ETA: Ack, bad way of illustrating the formulaic logic. But with the lack of information, I’m not sure there is one. I mean, there are 7 star systems, right? And 14 outgoing attacks - but since one route is the objectively “shortest” between two systems, those two systems are attacking each other, leaving 13 other attacks. Correct me if I’m wrong, but 13 is still logically speaking enough to cover the 5 other systems, right?
For each node on the graph, compute the distance of the nearest node, then compute the maximum of those distances. Either one or two nodes have that distance (if three do, then it’s clear than two internodal distances are the same, breaking an initial premise). If it’s one, then that node is unattacked. If it’s two, then they attack each other, so consider the same argument with the five remaining nodes.
It seems clear to me that, using mathematical induction, a system with an odd number of nodes will always have one node unattacked. Seven is just a particular case of this.
You can repeat the process with the remaining 5, then the remaining 3, leaving 1.
To elaborate: With 7 systems, we have 2 attacking each other. If any of the other 5 attacks that pair, then one of the pair is getting attacked twice which leaves one of the 5 unscathed (since there’s only 4 attacks left). If none of the other 5 attacks that pair, then the remaining 5 are all attacking each other, so we’ve now got the same problem only with 5 systems.
With 5 systems, we have a new shortest pair that will attack each other. Again, if any of the remaining 3 attacks that pair, then one of the remaining 3 will be left unscathed. If the remaining 3 attack each other, we’re now down to the 3 system problem.
With 3 systems, we have yet another shortest pair that will attack each other. That leaves one remaining system ready to swoop in and claim what’s left out of 6 devastated star systems. Score!
Your first step is correct. Say A,B shoot each other
After that, look at the shortest distance left over.
Case1: It is between C,D. Then they shoot each other. Iterate this process.
Case2: It is between A,C. Then C shoots A. Now you have a system of 5 star systems (C,D,E,F,G) and only 4 guns (D,E,F,G). One must survive.
If you have to keep iterating Case1, then you get 3 pairs that shoot each other and 1 survivor left over.
With an even number of stars, you could pair them off and everyone would be attacked. But if you have an odd number of stars, the only way everyone gets attacked is if you have a triangle were A is closest to B, B is closest to C, and C is closest to A. That’s impossible. So logically, any odd numbered group of stars will have at least one star that isn’t attacked.
That argument works for three stars, but you’ve got to deal with more cases with a larger number. For example, if they were in order on a straight line, you could have A closest to B, B closest to C, C closest to D, D closest to E, E closest to F, and F closest to G, so there’s no pairing off. Now, if you bend that line into a circle, what stops G being closest to A? Obviously, it can’t be, but you have more possible cases to deal with than just pairing off. You need some sort of a inductive argument, where you take the stars out of contention two at a time, without assuming any pairing off in the original arrangement. And the beauty of the inductive argument is that it works for any odd number, so you could restate the puzzle as involving 1,000,000,001 stars, and it still works.
Yes, but Little Nemo’s post assumed that you only have to deal with pairs and one triangle left over. To give a complete argument, you need to deal with other possible polygons (which is not too bad in the case of 7, but becomes difficult with a large number) or you have to have an explicit method of taking out stars two at a time.
** Erasmus Darwin**, that’s it! The reasoning that was eluding me was that there are a given number of attacks (seven), and so you can have more survivors than attacks left. Thanks!
Yes, but there will always be two that are closest together. In your example, once you close the circle and move G closest to A, A is also closest to G. Those two will attack each other. The remaining worlds are either:
A closed system, which reduces the problem to n - 2.
or
Also attacking the warring pair, which inevitably leaves one world unscathed.
Aren’t we taking the long way around the rosebush here? Instead of the shortest route, let’s look at the longest route.
If all the systems are different distances apart, then there must be one that has the longest route to its nearest neighbor. Let’s designate it X, as Gukumatz has. It will attack that neighbor.
The neighbor attacked by X will necessarily have another neighbor that is closer than X; it will attack that neighbor rather than X.
All other intersystem distances are shorter than the X->anywhere route, so all other systems will attack someone other than X.
X will never be attacked. In fact, even if you vary the number of systems, X will only be attacked in a scenario with only two systems.
Is there a hole in that reasoning?
Side question: We’ve established that at least one system will remain unscathed in this scenario. What’s the maximum number of systems that could remain unscathed?
I think it would be possible to arrange the systems such that only two are attacked. Take one system at the center of the cluster and arrange the others at cardinal positions around it (think north, south, east, west, up, down). Now each relationship between three systems can be described as a right triangle. The distance between any two of the cardinal systems would be the hypotenuse of that particular triangle, and thus greater than the distance of either from the central system. All six cardinal systems would attack the central system, which would in turn attack the nearest cardinal system, leaving five systems unscathed.
Yes. Imagine a one-dimensional Cartesian universe, with the stars at positions 1, 2, 4, 8, 16, 100 and 132 from the origin. Then there are two with the longest route to the nearest neighbour, i.e., 100 and 132, and they attack each other. The star that is unattacked is 16. I think I covered this possibility in my original argument.
Starting with seven stars (as in the original problem) suppose five of them (A, B, C, D, E) are clustered together, and the other two (F, G) are distant, but in roughly the same direction. The distance between F and G is greater than any neighbors within the cluster, but they attack each other. One of the other five is left unscathed.
Got it. Thanks, Giles, Robot Arm. I was looking for a way around the reduction process, but you’re right–it applies just as much working from the opposite direction. You can split off as many pairs as you want, but you’ll eventually wind up with a set of 3 systems, one of which won’t get attacked.
Not quite. It’s possible that some distant pair will attack each other (as a counter argument to your previous post), but it’s not guaranteed that there will be such a pair. You’re only certain to reduce the problem starting with the closest neighbors.
This is the mistake. As pointed out, there could be two systems that share the longest route to the nearest neighbor.
Yes, and you can do even slightly better. (To keep the question interesting, we’ll have to specify somehow that we’re only looking at one cluster, of course. Not sure how to do that rigorously without thinking more about it) In 2-D, you can arrange five systems around the central one and have them all closest to the central one (with six systems on the periphery, they’re all exactly the same distance). Going to 3-D, at a minimum you could add two more (straight up and straight down), so we know that at least six unscathed is possible in 3-D. I suspect more are possible, but don’t know the exact solution.