Eyes Above The Waves

Seems like a few people got close to the answer for the first problem. You formulate the condition for q being on the circle as a quadratic equation in t, and then apply the quadratic formula to solve for t. However, I can't give full credit to anyone because all the answers were incomplete; many ended containing a "plus or minus the square root ..." but a complete answer must describe which solution to pick. It's pretty easy to figure that out though.

My answer is

t = (ax + by - √(r²(x² + y²) - (ay - bx)²))/(a² + b² - r²)

where p = (a,b) and q = (x,y). The answer from Wolfram Alpha via Neil Rashbrooke is the same except it chooses the positive root; I think that's wrong, because it will give you a negative t (the denominator is negative).

The second problem is harder. Even though it's intuitively "obvious" that a solution is always possible, I found it quite difficult to prove, and apparently so did my readers. I think Joshua Cranmer got close but I don't fully understand his answer and he didn't get a complete algorithm for finding the order.

I start by observing that if you can find one rectangle to move safely then the solution to the whole problem follows by induction, since one moved rectangle can never overlap other moved rectangles, since they didn't overlap to start with. So the problem is reduced to finding one rectangle to move safely from the set of rectangles.

I also observe that without loss of generality you can reduce the problem to the case where the components of v are non-negative, i.e., we are moving the rectangles down and to the right by some amount, possibly zero.

Let's say rectangles R and S overlap horizontally if their projections onto the x-axis intersect. Similarly, they overlap vertically if their projections onto the y-axis intersect. Because our rectangles are non-overlapping, if R and S are different and overlap horizontally they cannot overlap vertically, and either R is entirely above S (every point in R is above (or on) the top edge of S) or R is entirely below S (every point in R is below (or on) the bottom edge of S).

Consider the subset of rectangles R such that R has no rectangle entirely below it that it overlaps horizontally. These rectangles do not overlap each other horizontally. Choose the "rightmost" rectangle from this set, let's call it M. I claim no other rectangle intersects M + v. This solves the problem.

The proof is still subtle. We have to show that our subset is non-empty, i.e., that at least one rectangle has no rectangles below it that it overlaps horizontally. This is easy though, since rectangle with the lowest bottom-edge certainly has no rectangles below it. So such an M exists.

Of course the hard part is to show that no other rectangle intersects M + v. We can show that in fact no rectangles are below M's top edge and to the right of M's left edge (other than M itself). Let's call this set S. I'll show S is empty, by assuming S is nonempty and working to a contradiction.

Clearly there can be no rectangles below M's top edge that overlap M horizontally, or they would have to be below M and we wouldn't have put M in that subset. So every rectangle in S would have to be entirely to the right of M. So choose out S one rectangle that has the lowest bottom edge rectangles in S. Let's call it P. I will show that P has no rectangles entirely below it that it overlaps horizontally, so it should have been part of the initial subset, which contradicts our choice of M as the rightmost rectangle in that subset, thus showing that no such P exists and S is empty.

Clearly no rectangle in S is below P and overlaps P horizontally. What about the rectangles not in S? Suppose a rectangle Q is not in S, is entirely below P and overlaps P horizontally. The left edge of Q must be at or to the left of the left edge of M, otherwise Q would be in S. The right edge of Q must be to the right of the right edge of M, since Q overlaps P horizontally. So Q also overlaps M horizontally. The bottom edge of Q is below the bottom edge of P which is below the top edge of M, so Q must be entirely below M --- but this is impossible, since we chose M to have no rectangle overlapping horizontally below it.

Phew! That's not easy for something so "obvious".

This solution should make for a reasonably efficient algorithm.

1. Sort the rectangles by right edge.
   
2. Set R to the rightmost rectangle.
   
3. If R has any rectangles overlapping horizontally below it, set R to the one of those rectangles with the rightmost right edge and go to step 3.
   
4. Move R.
   
5. Remove R from our list.
   
6. If there are more rectangles in the list, go to step 2.
   

Update Actually I'm pretty sure you can do a direct proof of correctness of the above algorithm. At the beginning of step 3 you have the invariant that there are no rectangles to the right of the right edge of R and below the top edge of R. Using that invariant, I think you can construct a much simpler proof than the one I gave here.

Also, as at least one commenter observed, you can improve this algorithm by not throwing away all your work every time you go to step 2. That adds complexity though...

Update Fixed a typo in the answer to the first problem, pointed out by Boris.