| Jan | Feb | Mar | Apr |
| Communicated by Dan Jurca |
Given 2n points in the plane with no three collinear, n colored blue and n colored red, prove that one can always connect the points in pairs by line segments having different colored endpoints and such that no two line segments cross each other.
| Solution by Dan Jurca |
The assertion is obviously true if n=1, hence follows by induction on n from the following
Proposition. If n is an integer, 2 £ n, and there exist 2n points in the plane with no three collinear, n colored blue and n colored red, then there exists a (straight) line \l in the plane and an integer m, 1 £ m < n, such that there are exactly m points colored blue and m points colored red on one side of \l, and n-m points colored blue and n-m points colored red on the other side of \l.
Proof.
The assertion is clearly true if n=2, so suppose 3 £ n. Let S be the set of 2n points, let D be a disk which includes S, let T be the set of all n(2n-1) lines determined by each pair of points in S, regardless of color, and let P be a point in the plane not in D and not on any line in T. (Such a P clearly exists since T is a finite set of lines.) Since no three points in S are collinear a line determined by P and a point in S contains no other point of S. Therefore a line through P rotated through 180° meets the points in S one at a time. So suppose k is a line through P such that the disk D is on one side of k, and let c=0. Without loss of generality suppose that as k is rotated through 180° the first point in S which is on k is a point colored blue. Then as k rotates through 180° add 1 to c each time a point colored blue is met, and subtract 1 from c each time a point colored red is met. (Thus, c is a ``counter''.) Clearly after k has rotated through 180° the value of c will be 0 again (since there are as many points colored blue as are colored red). If the last point met by k was colored blue, then c must have been -1 before k met this last point, hence must have been zero somewhere. Then l can be a line through P in the angle determined by k after c has assumed the value 0 for the first time (after being 1 earlier), and then either 1 again, or -1. A similar argument can be made if the first and last points met by k are colored red. If, however, the first and last points met by k are colored differently, then by considering the smaller set of points obtained by deleting these two points, and arguing as above, the proposition follows by induction on n.
| Better solution communicated (but not found) by Dan Jurca |
Suppose the points colored blue are labeled B1, B2, ¼, Bn and the points colored red are labeled R1, R2, ¼, Rn, let Sn
be the set of all permutations on the set {1, 2, ¼, n}, and let |PQ| be the length of the segment in the plane with endpoints P and Q.
Let j:Sn®R by
|
| Proposed by Dan Jurca |
A method often used to solve an equation, or, equivalently, to find a zero of a function f:R®R (i.e., a number z such that f(z)=0), is to compute the first few terms of the sequence (xn)n=0¥ where x0 is chosen near z and for 1 £ n the terms xn
are generated using Newton's method. That is
|
|
| Solution by the proposer |
|
|
Bojan Basic found an expression for a function f as required in 2 with coefficients satisfying a certain linear system, and proved that there exists a solution of the system.
Minhua Lin gave the following explicit formula for a function f satisfying the conditions in 2.
|