This entry was posted
on Saturday, November 24th, 2007 at 7:19 pm and is filed under Math, Riddles.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
Look at the sum of the lengths of the segments connecting the pairs. If a pairing is invalid, find two such pairs with intersecting segments. You can transpose those pairs, so that at least those two are now fixed. Note that, because no three are on the same line and the segments intersect, you have replaced the two diagonals of a convex quadrilateral with two of its sides; by Triangle Inequality, you have thus strictly decreased the sum of lengths of all the segments.
There is only a finite number of pairings (100!), and thus there is a pairing with minimal sum of lengths: It must then be a valid pairing, by the above reasoning.
I think that qualifies as elegant, although it was not the solution I came up with the first time I heard this riddle. My original solution, which I like better despite it being less elegant, involved induction on N, the number of points of each colour:
For N=0,1, the problem is trivial.
Assume that the claim is true for any N > k ≥ 0, and let us prove for N. First, find the convex hull of all 2N points, and take one of the points on its boundary, denote it B, and assume that it is red. Denote the adjacent vertices of the convex hull by A and C. Define an order on all of the points other than B by X > Y ↔ angle(ABX) > angle(ABY) (the angles satisfy 0 ≤ ABX ≤ ABC < 180°, as well as being all different from each other, due to properties of convex hull and the fact that no three points are on the same line).
We have ordered N such blue points and N-1 such red points, thus there exists a blue point D such that the amount of red points lesser than D equals the amount of blue points lesser than D (and obviously the same will then hold for the amounts greater than D). This is because the least blue point has AT LEAST as many red points lesser than it than blue points lesser than it (which amount to 0), while the greatest one has AT MOST as many red points lesser than it than blue points lesser than it (which amount to N-1). In addition, as we go over the blue points from least to greatest, the number of lesser blue points rises discretely, while the number of lesser red points is non-decreasing; thus, there must be such a point where those numbers are equal (this is the discrete equivalent of the stationary point theorem for non-decreasing functions).
Now let us look at what happens when we pair points B and D together: All of the points lesser than D are on one side of line BD, while all of the points greater than D are on the other, by the definition of the ordering. Therefore, on each side of BD there are as many red points as blue, and thus by the induction (woo!), we can find valid pairings for each side. We can then combine those pairings together, add the pair BD, and get a valid pairing for all of the points.
To answer the question of which solution is “better”, we might want to check the efficiency of the constructions.
In the first solution, we can construct a valid pairing by starting from a random pairing and improving it (by disentangling intersections) until it is valid. I believe that it is possible to do this with complexity O(N^2 + N*M), where N = number of pairs, and M = number of disentanglements performed, but as M could be very high, this might not be very efficient. There may be more efficient ways to implement this method, though.
In the second solution, the first step is to take an arbitrary point on the convex hull – we could just take the leftmost point, this will require O(N) time. We then sort the rest of the points by angle – we don’t really need another point for this, because all of the points are inside an angle of less than 180° – this will require O(N*log(N)) time. We then scan through the sorted array to find a point that split the sides equally – O(N) time. We then solve the problem for two smaller problems, K and L, with K+L=N-1. Overall we can easily see by induction that the total worst case complexity is not more than O(N^2*log(N)). We can also see that if we always find that K=0 and L=N-1, then we will indeed reach O(N^2*log(N)) complexity, so it is an exact bound. I doubt that the number of disentanglements performed in the first method is as small as N*log(N), for big values of N – in average case, perhaps (although still doubtful), but not in worst case.
I surmise that the second solution is more efficient for constructions; I would also add that were this problem needed to be solved by a human with a long ruler and pencil, and not by a computer, some of the steps in each method would be simpler and others more complex. However, in the second method, both finding a vertex of the convex hull and the sorting are almost immediate: The sorting can be completely skipped, and instead just scan the points clockwise with a ruler. This will make the complexity about O(N^2) instead. On the other hand, in the first method, intersections would be found more easily (we can say that if there is an intersection, it can be found in O(1)), which would make the complexity about O(N+M), even better. The value of M can also be decreased by trying to avoid intersections when possible while creating the starting pairing; however, there will be many line erasures and drawing involved, which would mean a significant coefficient to the complexity, as opposed to the second method, where you never erase the lines you draw.
Comparing complexities with other solutions could be interesting; unfortunately I don’t know any more.
I believe the complexity analysis of the second algorithm can be improved under the following modification:
at each step i will look for half a circle not containing all the points with center (0,0) (assume not part of our system) and radius “big”.
which has the same amount of blue and red points (exists by same rationing). thus i will split into the two convex domains. with preprocessing sorting by red points, and blue points by angle relative to (0,0) which is neglegent, it is similarly O(n^2) [ T(n) = T(k) + T(n-k) + O(n)]
The bottleneck is thus finding this half-circle. If I’m correct, this could be improved from linear to logarithmic. since at each step (except the first) we’re in a convex strip of less than PI degrees. Thus finding the difference between number of red, blue points in an intersection with a half-circle starting from an angle of one the points can be calculated using the array of angles. Thus the lion-in-the desert method proposed by Dan can be employed in O(lgn) time.
We get [neglecting preprocessing which is also O(nlgn)] T(n) = O(lgn) + T(n-k) + T(k), which amounts to O(n lgn)
This is optimal, because if the blue points are (0,1).. (0,n) and red are (1,y1).. (1,yn) it is equivalent to sorting.
November 25th, 2007 at 4:16 am
Look at the sum of the lengths of the segments connecting the pairs. If a pairing is invalid, find two such pairs with intersecting segments. You can transpose those pairs, so that at least those two are now fixed. Note that, because no three are on the same line and the segments intersect, you have replaced the two diagonals of a convex quadrilateral with two of its sides; by Triangle Inequality, you have thus strictly decreased the sum of lengths of all the segments.
There is only a finite number of pairings (100!), and thus there is a pairing with minimal sum of lengths: It must then be a valid pairing, by the above reasoning.
I think that qualifies as elegant, although it was not the solution I came up with the first time I heard this riddle. My original solution, which I like better despite it being less elegant, involved induction on N, the number of points of each colour:
For N=0,1, the problem is trivial.
Assume that the claim is true for any N > k ≥ 0, and let us prove for N. First, find the convex hull of all 2N points, and take one of the points on its boundary, denote it B, and assume that it is red. Denote the adjacent vertices of the convex hull by A and C. Define an order on all of the points other than B by X > Y ↔ angle(ABX) > angle(ABY) (the angles satisfy 0 ≤ ABX ≤ ABC < 180°, as well as being all different from each other, due to properties of convex hull and the fact that no three points are on the same line).
We have ordered N such blue points and N-1 such red points, thus there exists a blue point D such that the amount of red points lesser than D equals the amount of blue points lesser than D (and obviously the same will then hold for the amounts greater than D). This is because the least blue point has AT LEAST as many red points lesser than it than blue points lesser than it (which amount to 0), while the greatest one has AT MOST as many red points lesser than it than blue points lesser than it (which amount to N-1). In addition, as we go over the blue points from least to greatest, the number of lesser blue points rises discretely, while the number of lesser red points is non-decreasing; thus, there must be such a point where those numbers are equal (this is the discrete equivalent of the stationary point theorem for non-decreasing functions).
Now let us look at what happens when we pair points B and D together: All of the points lesser than D are on one side of line BD, while all of the points greater than D are on the other, by the definition of the ordering. Therefore, on each side of BD there are as many red points as blue, and thus by the induction (woo!), we can find valid pairings for each side. We can then combine those pairings together, add the pair BD, and get a valid pairing for all of the points.
To answer the question of which solution is “better”, we might want to check the efficiency of the constructions.
In the first solution, we can construct a valid pairing by starting from a random pairing and improving it (by disentangling intersections) until it is valid. I believe that it is possible to do this with complexity O(N^2 + N*M), where N = number of pairs, and M = number of disentanglements performed, but as M could be very high, this might not be very efficient. There may be more efficient ways to implement this method, though.
In the second solution, the first step is to take an arbitrary point on the convex hull – we could just take the leftmost point, this will require O(N) time. We then sort the rest of the points by angle – we don’t really need another point for this, because all of the points are inside an angle of less than 180° – this will require O(N*log(N)) time. We then scan through the sorted array to find a point that split the sides equally – O(N) time. We then solve the problem for two smaller problems, K and L, with K+L=N-1. Overall we can easily see by induction that the total worst case complexity is not more than O(N^2*log(N)). We can also see that if we always find that K=0 and L=N-1, then we will indeed reach O(N^2*log(N)) complexity, so it is an exact bound. I doubt that the number of disentanglements performed in the first method is as small as N*log(N), for big values of N – in average case, perhaps (although still doubtful), but not in worst case.
I surmise that the second solution is more efficient for constructions; I would also add that were this problem needed to be solved by a human with a long ruler and pencil, and not by a computer, some of the steps in each method would be simpler and others more complex. However, in the second method, both finding a vertex of the convex hull and the sorting are almost immediate: The sorting can be completely skipped, and instead just scan the points clockwise with a ruler. This will make the complexity about O(N^2) instead. On the other hand, in the first method, intersections would be found more easily (we can say that if there is an intersection, it can be found in O(1)), which would make the complexity about O(N+M), even better. The value of M can also be decreased by trying to avoid intersections when possible while creating the starting pairing; however, there will be many line erasures and drawing involved, which would mean a significant coefficient to the complexity, as opposed to the second method, where you never erase the lines you draw.
Comparing complexities with other solutions could be interesting; unfortunately I don’t know any more.
November 29th, 2007 at 3:44 am
I believe the complexity analysis of the second algorithm can be improved under the following modification:
at each step i will look for half a circle not containing all the points with center (0,0) (assume not part of our system) and radius “big”.
which has the same amount of blue and red points (exists by same rationing). thus i will split into the two convex domains. with preprocessing sorting by red points, and blue points by angle relative to (0,0) which is neglegent, it is similarly O(n^2) [ T(n) = T(k) + T(n-k) + O(n)]
The bottleneck is thus finding this half-circle. If I’m correct, this could be improved from linear to logarithmic. since at each step (except the first) we’re in a convex strip of less than PI degrees. Thus finding the difference between number of red, blue points in an intersection with a half-circle starting from an angle of one the points can be calculated using the array of angles. Thus the lion-in-the desert method proposed by Dan can be employed in O(lgn) time.
We get [neglecting preprocessing which is also O(nlgn)] T(n) = O(lgn) + T(n-k) + T(k), which amounts to O(n lgn)
This is optimal, because if the blue points are (0,1).. (0,n) and red are (1,y1).. (1,yn) it is equivalent to sorting.
November 29th, 2007 at 11:56 am
scratch the above, it’s no good