## Private and Public

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

### Private and Public

This one was a pretty fun one. Let's say you have n perfectly spherical planets, all with the same radius, floating around in the universe. Let's call a point on a planet private, if it cannot be seen from any other planet in the universe. If a point can be seen from another planet, it is public. What is the total private area given you have n planets. (Note: the answer is pretty obvious with some investigation, but proving its true is more difficult)

Kurushimi

Posts: 842
Joined: Thu Oct 02, 2008 12:06 am UTC

### Re: Private and Public

Hmm... not a full solution, but two simple pieces of it:
Spoiler:
First, we don't have to worry about one planet being hidden behind another... if a point A on one planet could normally see a point B on another planet, but can't because there's a third planet in the way... then there are points on that third planet that can see points A and B (specifically, the intersections of the line from A to B with the third planet's surface). It can be similarly extended if there are multiple planets blocking A and B. So A and B are still public. So all you need is that each planet can see exactly half of each other planet, and take the union.

Second, if there is a constant answer (which the question implies), that answer is: the same area as the surface area of one planet. Imagine the planets all in a row, in a straight line... the ones in the middle are entirely public, and the ones at each end are half public and half private. However, that doesn't prove that a constant answer exists.
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6959
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Private and Public

Great puzzle. I have a rather clunky solution.

Spoiler:
Firstly, I'll mostly just use geometric language, so I'll talk about spheres instead of planets, and use points, lines and planes to talk about what's going on.

Note that a point on a sphere is private iff the plane tangent to that point is such that all parts of all the spheres are to one side of that plane. In a two planet system, the set of points which are private, or public, on one of the planets is a hemisphere, and the line dividing the two halves I will call a terminator. My revised definition of what is public and private might lead to some disagreement regarding the disposition of points on the terminators, but I could care less as these have no area.

Moreover, we can see that the private area on some sphere will be the intersection of n-1 hemispheres of that sphere, a sort of spherical polygon. The proposition that I put is that these polygons can be reassembled into a whole sphere, so that the private area on all spheres combined is the area of one of the spheres.

To see this, fix a plane, P_0, and form the set \{P_t : t\in R\} of all planes parallel to it such that |x-y| = \min \{d(x,y):\ x\in P_x, y\in P_y\} ie, I've indexed all the planes parallel to P_0, in a nice way. There exists some smallest interval [a,b] such that all parts of the spheres are all to only one side of P_a, and all to the other side of P_b. Note that P_a must intersect at least one sphere, or else a smaller interval does the job, and it can only touch any sphere at at most one point, or else that sphere has parts that are not on the correct side of the plane.

If P_a intersects the spheres at precisely one point, then that point is indisputably private. On the other hand, if it touches more than one sphere, then these points are on terminators, and I again mention that they have a total area of 0, and so are inconsequential.

Moreover,P_0 was chosen arbitrarily, so for most directions that a plane can be oriented, there is a point within a private spherical polygon that has a tangent plane that is parallel to that plane.

I've been rather sloppy here, in that I haven't mentioned that we can do the same thing for P_b, and so we actually get two points whose tangents are parallel, and we get full coverage of the the sphere... Kinda clunky but I think I get there in the end. I had another idea, about scaling the centres of the spheres so that they approached a point, without scaling the radii, but that was clunkier still.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5392
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Private and Public

I believe I have an elegant solution, with only a modicum of handwaving.

Spoiler:
As phlip notes, the very fact that the question is being posed means there is a constant answer (which from the n=1 case must be the surface area of a single sphere). Since I like induction, I want to show that removing an arbitrary planet (call it A) will not change the total private area. I can do this by showing that the total area of A that is private is the same as the total area on other planets that only A can see.

The key is to consider tangent planes. A point on A is private iff the tangent plane at that point has nothing on one side of it. A point on a planet B can be seen only by A iff the tangent plane at that point has only (part of) A on one side. So we can map the area of B that only A can see into the private area of A by simple translation. Similarly, if we take a private point on A and drag its tangent plane along its perpendicular, we will eventually hit a planet at a point only A can see - it might hit more than one at once, but luckily this will happen only for a set of points of measure zero. So "translate and glue together" is a bijection between (the interiors of) the parts of other planets that only A can see, and (all but a set of points of measure zero of) the private area of A. So we're done by induction.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.
Token

Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

### Re: Private and Public

I got a simple solution that's similar to Token's.
Spoiler:
Define the tangent direction of a point on a planet's surface be the direction from it's planet's center to it. Such a point is visible only from points that lie further in space along its tangent direction than it. So, a point is private exactly if it is the furthest point in its tangent direction, and therefore there is exactly one private point of every tangent direction, except in the case of "ties", which are measure-zero by handwaving. So, the private regions (tee hee) of all the planets, partition the tangent directions minus a measure-zero set, and therefore can be translated to form a sphere minus a measure-zero set. So, their total area is that of a sphere.

Interestingly, this proof carries through if the planets are identical, identically-oriented strictly convex potatoes.
Last edited by aleph_one on Thu Dec 02, 2010 12:06 am UTC, edited 3 times in total.
aleph_one

Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

### Re: Private and Public

I really like aleph_one's solution. It's pretty much exactly the one that was given in the video I got this problem off of.
Also, like how the proof is actually more general than simple spheres. Didn't realize that.

Kurushimi

Posts: 842
Joined: Thu Oct 02, 2008 12:06 am UTC

### Re: Private and Public

What video did you find this problem from? I'd be curious to hear others, as this was quite a nice one.

EDIT: I figured out how to make my proof rigorous:
Spoiler:
To proof the fact that the ties (point on boundaries of private regions) are measure zero, not that the directions in which there's a tie are a subset of the union of the tied directions of each pair of planets, which form a circle on the sphere. Since there are finitely many pairs and each circle is measure zero, the tied direction are measure zero as well.
aleph_one

Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA