That “Japan” location threw me off. Howdy.
refined answer
[details=Spoiler]*For any N set, there will always be 2 units that have an identical smallest distance, thus facing each other.
are you looking for a formal mathematical proof using induction? i’m too lazy to come up with it 
hence teh fail at interviews :sad:
edit: ah screw it i’ll take a stab at it and edit in my solution later
I’m not sure what you mean exactly by “each pair’s smallest separation is to each other”, but remember that every distance between pairs of marines is unique. So in your diagram, the distance between 1-2 is different from that between 3-4, and different from 3-2, etc…
I’ll try to show with an example. Here, we have A watching B, B watching A, and C watching B. But no one is watching C!
A.....B.......................C
Here’s an example where A and B watch each other, and C and D watch each other
A...B.................C....D
Now in the real problem, the soldiers don’t have to be in a line. They can be anywhere. In fact, they can even be in space… so each soldier could be stationed on a planet, and told to watch the nearest planet.
You have to show that if the number of soliders is odd, then NO MATTER HOW THEY ARE ARRANGED, there will always be one that is not watched. Hope that’s more clear 
Formal mathematical proof yes. Whether your use induction or not is up to you. :lovin:
Ok Im gonna go with what I originally posted. Whats important to note here is that the distance between each soldier is unique.
So lets take the shortest distance between two soldiers. These two soldiers will form a unique pair that will watch each other. If they watched anyone else, that would be a direct violation of their orders, since they are closest to each other. Now take the second shortest distance between the remaining soldiers. These two soldiers will also form a unique pair, under the same logic. With an even number of soldiers, we can thus see how there is a unique pair of soldiers that watches each other. Since there are an even number of soldiers, we can pair them up easily
But now lets try to add an odd soldier, call him y, and assume that everyone can still watch each other. If we place the odd soldier too far away, no one watches him. we could place him next to a soldier, call him x, such that x and y form the pair that watch each other. however, we have displaced x’s original partner, call him z. At this point, z can either be too far away to be watched, or he is within distance to another soldier, and can form up a pair with him. However, this will displace yet another soldier. New pairs will be formed, but there will always be an odd one out.
I think this is where the induction comes in, to prove that this displacement always leaves someone out. will think more on this.
1/2/3/4 are the distances, '’ are the soldiers. That was the quickest most logical shorthand I could come up with. It of course encompasses 3 dimensionality, as any metric established can be flipped to 2d easily since it’s all lines. So your in-a-line examples could be written more tersely with:
12
and
132
I was just expanding that to the next level:
1
3 2
4
, since it’s not the identification of any soldier blob that’s important, but the distance. Plus who deploys soliders in a line, anyways? That only happens if you’re French. 
Probably the shortest proof possible is: “alcohol.” Or “blinking”.
EDIT: The counter to the last of course being “robots”. Which of course means that Zass here is trying to seed the ground for takeover by our new robot overlords. :sad:
As for the pool problem, i initially thought double the depth, but after the clarification, i don’t quite agree that rotate 45 degrees and expand is the best answer. i agree that it leads to the answer, but its not based as much in reality given that it is a pool and it would be a little difficult to rotate =] given the pool:
1____A____2
|~|
|~3~|
|
take the equilateral triangle formed by points 1-2-3, reflect over side A, dig, fill with water, repeat for each side of the pool.
Here’s the answer to the soldier problem. Again, not something I’d ask in an interview (too hard), but I think it’s a fun problem.
answer
The key to solving this problem is realizing two things. First I’ll describe the two things to realize, and then show how they combine to solve the problem.
There will always be a pair of soldiers who are looking at each other. The 2 soldiers with the smallest distance must be looking at each other, because it’s the smallest distance.
If there’s more than one person looking at any given solider, then there is an unwatched soldier. This is true by the pigeonhole principle. If two people are watching one soldier, then there is at least one unwatched soldier.
With these two observations, we can solve the problem. We will proceed by contradiction. Let’s assume that there are N soldiers, where N is odd, and there are no unwatched soliders. By observation 2), this means that there is one and only one solider watching any given soldier.
Now by observation 1), there is a pair of soliders looking at each other THAT NO ONE ELSE IS LOOKING AT (by observation 2). We can “remove” both of these soliders from the field, because no one else is looking at them, and they aren’t looking at anyone else. They have no bearing on the other soldier’s behavior.
Notice that we now have the same problem, except with N-2 soliders. We can proceed in this way with a field of N-4, N-6, etc… But because N is odd, we will be eventually left with one soldier, all alone. He cannot be watched. This is a contradiction of our assumption, that all soldiers are watched. Thus our assumption was false.
QED.
Zass, although I see how your line of reasoning leads to the answer, there are a couple of problems with your assumptions. Keep in mind I, for one, was not smart enough to figure out this problem mathematically and I had to look up the answer. But, after thinking about this problem for a while (probably way too long than is reasonable =]), there were a couple of things I realized.
Remember, we are trying to solve the problem for only an odd number of soldiers. Your first assumption is correct, there will always be at least one pair of soldiers looking at each other. However, your second assumption, while correct, is not limited to only an odd number of soldiers. Let me draw up an example using Preppy’s notation. For simplicity sake, lets represent soldiers with letters and distances with numbers:
A 2 B 3 C 4 D
Both soldiers A and C are watching B. However, notice that the unwatched soldier is not C, but D (who is watching soldier C). While your theory about having an unwatched soldier is correct, this setup presents two problems to your second assumption.
For one, there are an even number of soldiers. This means that the assumption you used, while correct, can’t be used to solve the problem because it can be a potential solution to both an odd and even number of soldiers, depending on the setup.
Secondly, it also shows that the assumption later in your solution about all the soldiers in an even number problem being paired up is also incorrect. We cannot remove all the “paired” soldiers from the problem simply because they are looking at each other. As the example shows, they may not necessarily be.
That’s not to say there isn’t a solution to the problem. There is, and it’s one I can’t take credit for figuring out. Google it if you’re interested. I’m not trying to insult your intelligence or anything, but I just thought that given the way you laid out the problem that the logic used to find the solution shouldn’t have any exceptions.
In your example, there are an even number of soldiers, yes. My second observation is true for both odd and even numbers of soldiers. To restate it:
2) If there’s more than one person looking at any given solider, then there is an unwatched soldier. This is true by the pigeonhole principle. If two people are watching one soldier, then there is at least one unwatched soldier.
So this observation is true for any number of soldiers.
Remember, I’m starting with the assumption that Let’s assume that there are N soldiers, where N is odd, and there are no unwatched soliders
Note the clause and there are no unwatched soliders. Because there are no unwatched soliders, then there cannot be any solider that is being watched by two or more people.
So what I’m essentially doing, is saying that either we can remove the “paired” soliders, OR there will be a soldier that is watched by several people. If we remove the “paired” soliders, then we end up with 1 solider by himself, since N is odd. And if we have a soldier that is watched by several people, then there must be an unwatched solider. Either way, there will always be an unwatched solider!
You’re not insulting my intelligence at all :). Thanks for your response! I enjoy these kinds of puzzles. I’d love to hear an alternative solution. Also, please let me know if what I wrote above didn’t convince you that the logic was sound, and I’ll try my best to be more clear.
Julien
You have 9 oranges and 4 paper bags.
You must put at least 1 orange in each bag and each bag must have an odd number of oranges in it.
How would you do this?
Do you HAVE to use all 9 oranges? Can I double bag? I hate it when I go to a shitty supermarket and they fail to double bag.
Demonstrated skills and experience are key. Does your resume clearly communicate that? What projects do you have that would show that? Are they clearly explained? If you were someone else, would you understand what your resume is supposed to telling/selling to you?
cut an orange in half, and then put 5 in one bag, 1 in another, and 1.5 in the other 2…i’m assuming 1.5 is an odd number.
My answer…
Given those rules, I would just put one orange in one bag, two oranges and the first bag in the second bag, and so on.