Problem for 2008 January

Problem for 2008 February

Problem for 2008 March

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.

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.

Suppose the points colored blue are labeled B₁, B₂, ¼, B_n and the points colored red are labeled R₁, R₂, ¼, R_n, let S_n 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:S_n®R by

j(p)= n å i=1  |BiRp(i)|.

Since S_n is a finite set the function j attains a minimum value, say at p₀ Î S_n. Now if the segment B_iR_p0(i) intersects the segment B_jR_p0(j), then (by the triangle inequality) a value less than j(p₀) is attained by j(p₁), where 1 £ k £ n, k ¹ i, k ¹ j Þ p₁(k)=p₀(k), p₁(i)=p₀(j), and p₁(j)=p₀(i). This contradiction shows that no two of the segments B₁R_p0(1), B₂R_p0(2), ¼,\B_nR_p0(n) intersect.

Problem for 2008 April

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 (x_n)_n=0^¥ where x₀ is chosen near z and for 1 £ n the terms x_n are generated using Newton's method. That is

1 £ n Þ xn=xn-1-  f(xn-1) f¢(xn-1) .

If f is nice enough and x₀ is sufficiently close to z the sequence so generated converges to z, and often converges (in an appropriate sense) rapidly.

1.

Consider f:R®R by f(x)=(4x⁵-19x⁴+26x³-7x²-4x+4)/4, and observe that f(2)=0. Show that with x₀=0 the sequence of Newton's method iterates as described above is (0,1,0,1,0,1,¼), hence does not converge.

2.

Generalize this as follows. Suppose n is an integer and 2 £ n. Then there exists a function f:R®R such that f(n)=0 but if we set x₀=0, then the sequence of Newton's method iterates as described above is

(0,1,2,¼,n-1,0,1,2,¼,n-1,0,1,2,¼,n-1,¼,¼);

i.e., x_i=i mod n.

1.

We find

1 £ iÞ xi =xi-1-  f(xi-1) f¢(xi-1) =xi-1-  4xi-15-19xi-14+26xi-13-7xi-12-4xi-1+4 20xi-14-76xi-13+78xi-12-14xi-1-4 =  16xi-15-57xi-14+52xi-13-7xi-12-4 20xi-14-76xi-13+78xi-12-14xi-1-4 ,

so that if x_i-1=0, then x_i=1, and if x_i-1=1, then x_i=0.

2.

There exists a unique polynomial p(x) of degree £ 2n+1 (a Hermite interpolating polynomial ) with the following properties.

a.

p(0)=p(1)=p(2)=¼ = p(n-2)=1;

b.

p¢(0)=p¢(1)=p¢(2)=¼ = p¢(n-2)=-1;

c.

p(n-1)=1, and p¢(n-1)=1/(n-1);

d.

p(n)=0, and p¢(n)=0.

This polynomial has the properties required in 2.

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.

f(x)= ì ï ï ï í ï ï ï î e-x if x Î (-¥,n-2) (x+3-n)(x+1-n)2e-(n-2)+ (3x-2nx+2n2-4n+2)(x+2-n)2(n-1) if x Î [n-2,n-1) (2xn-x-2n2+4n-2)(x-n)2(n-1) if x Î [n-1,¥)

Problem for 2008 May

According to the Hungarian Problem Book II the following problem appeared in the 1913 Eötvös mathematics competition.

Prove that for every integer n > 2

(1·2·3¼n)2 > nn.

Solution by Dan Jurca

1 < i < n Þ

i < n   so (i-1)i < (i-1)n   so i2-i < in-n   so n < in-i2+i =i(n-i+1)   so  n n+1-i < i.

Therefore 2 < n Þ

nn n! = n Õ i=1   n i = n-1 Õ i=1   n i = n Õ i=2   n n+1-i < n Õ i=2  i = n Õ i=1  i =n!,   whence nn < (n!)2,

as desired.

Problem for 2008 June

Proposed by Dan Jurca

Recall that the vector ``cross product'' a×b in R³ is not associative. For example

i×(i×j) =i×k=-j,   but (i×i)×j =0×j=0.

So for vectors a and b in R³ let

V1(a,b) ={x Î R3 | x×(a×b)=(x×a)×b} V2(a,b) ={x Î R3 | a×(x×b)=(a×x)×b} V3(a,b) ={x Î R3 | a×(b×x)=(a×b)×x}.

1.

Prove that a,b Î R³ Þ V_i(a,b) is a subspace of R³, i=1,2,3.

2.

Prove that a,b Î R³ Þ V₁(a,b)=V₃(b,a).

3.

Prove that a Î R³ Þ V₂(a,a)=R³.

4.

What are the subspaces V_i(a,0), i=1,2,3?

5.

If a ¹ 0, what is the subspace V₃(a,a)?

6.

What is the subspace V₃(i,j)?

7.

What is the subspace V₃(j,i)?

8.

What is the subspace V₃(i+j,i)?

9.

Show that a,b Î R³ Þ V_i(a,b) ¹ {0}, i=1,2,3.

1.

Obviously 0, the zero vector, is in each V_i(a,b), so each is a nonempty subset of R³. If x Î V₁(a,b) and y Î V₁(a,b), then

(x+y)×(a×b) =(x×(a×b))+(y×(a×b)) =((x×a)×b)+((y×a)×b) =((x×a)+(y×a))×b =((x+y)×a)×b,

so that x+y Î V₁(a,b). If k Î R and x Î V₁(a,b), then

(kx)×(a×b) =k×(x×(a×b)) =k((x×a)×b) =(k(x×a))×b =((kx)×a)×b,

so that kx Î V₁(a,b). Hence V₁(a,b) is a subspace of R³; and similarly V₂(a,b) and V₃(a,b) are subspaces of R³.

2.

If x Î V₁(a,b), then x×(a×b)=(x×a)×b; hence

b×(a×x) =-b×(x×a) =(x×a)×b =x×(a×b) =-(a×b)×x =(b×a)×x,

so that x Î V₃(b,a), and V₁(a,b) Ì V₃(b,a). Similarly V₃(b,a) Ì V₁(a,b), whence V₁(a,b)=V₃(b,a).

3.

x Î R³ Þ a×(x×a)=-(x×a)×a=(a×x)×a, so that x Î V₂(a,a); hence R³ Ì V₂(a,a), so V₂(a,a)=R³.

4.

Since x Î R³ Þ x×(a×0)=x×0=0=(x×a)×0, x Î V₁(a,0), and V₁(a,0)=R³. Similarly V₂(a,0)=R³ and V₃(a,0)=R³.

5.

x Î V₃(a,a) Þ a×(a×x)=(a×a)×x=0×x=0; it follows that (a·x)a-(a·a)x=0, so that (since a ¹ 0) x=(a·x)a/(a·a); i.e., x=ka for some k Î R. Conversely, if x=ka, then a×(a×x)=a×(a×ka)=0=0×x=(a×a)×x, and x Î V₃(a,a). Hence a ¹ 0 Þ V₃(a,a)=Ra.

6.

Suppose x=x₁i+x₂j+x₃k and x Î V₃(i,j). Then i×(j×(x₁i+x₂j+x₃k))=(i×j)×(x₁i+x₂j+x₃k). Therefore i×(-x₁k+x₃i)=k×(x₁i+x₂j+x₃k), so x₁j=x₁j-x₂i. Therefore x₂=0 and x=x₁i+x₃k. Conversely, i×(j×(x₁i+x₃k))=i×(-x₁k+x₃i)=x₁j=x₁(k×i)+0=k×(x₁i+x₃k)=(i×j)×(x₁i+x₃k), so x₁i+x₃k Î V₃(i,j). Therefore V₃(i,j)=RiÅRk.

7.

If x=x₁i+x₂j+x₃k Î V₃(j,i), then j×(i×(x₁i+x₂j+x₃k))=j×(x₂k-x₃j)=x₂i=(j×i)×(x₁i+x₂j+x₃k)=-k×(x₁i+x₂j+x₃k)=-x₁j+x₂i, so that x₁=0 and x=x₂j+x₃k. Conversely, if x=x₂j+x₃k, then j×(i×x)=j×(i×(x₂j+x₃k)=j×(x₂k-x₃j)=x₂i=-k×(x₂j+x₃k)=(j×i)×(x₂j+x₃k), so x Î V₃(j,i). Hence V₃(j,i)=RjÅRk.

8.

If x=x₁i+x₂j+x₃k and x Î V₃(i+j,i), then we find (i+j)×(i×(x₁i+x₂j+x₃k))=(i+j)×(x₂k-x₃j)=-x₂j-x₃k+x₂i=x₂i-x₂j-x₃k; and ((i+j)×i)×(x₁i+x₂j+x₃k)=-k×(x₁i+x₂j+x₃k)=-x₁j+x₂i=x₂i-x₁j. Therefore x₁=x₂ and x₃=0, so that x=k(i+j) for some k Î R. Conversely, (i+j)×(i×k(i+j))=k(i+j)×k=k(-j+i)=-k(j-i)=-kk×(i+j)=((i+j)×i)×k(i+j), so k(i+j) Î V₃(i+j,i). Thus V₃(i+j,i)=R(i+j).

9.

Suppose a=a₁i+a₂j+a₃k and b=b₁i+b₂j+b₃k. Then by a straightforward computation we find that x Î V₁(a,b) if and only if M₁x=0, x Î V₂(a,b) if and only if M₂x=0, and x Î V₃(a,b) if and only if M₃x=0 where M₁, M₂, and M₃ are the following matrices.

M1= é ê ê ê ê ê ë a2b2+a3b3 -a2b1 -a3b1 -a1b2 a1b1+a3b3 -a3b2 -a1b3 -a2b3 a1b1+a2b2 ù ú ú ú ú ú û

M2= é ê ê ê ê ê ë 0 a1b2-a2b1 a1b3-a3b1 -a1b2+a2b1 0 a2b3-a3b2 -a1b3+a3b1 -a2b3+a3b2 0 ù ú ú ú ú ú û

M3= é ê ê ê ê ê ë a2b2+a3b3 -a1b2 -a1b3 -a2b1 a1b1+a3b3 -a2b3 -a3b1 -a3b2 a1b1+a2b2 ù ú ú ú ú ú û

By another straightforward computation one finds that each of M₁, M₂, and M₃ is a singular matrix; hence for each a and b there exists a nonzero vector in each of V₁(a,b), V₂(a,b), and V₃(a,b).