Sylvester’s Problem, Gallai’s Solution

(Để tạm đây)

Source: http://www.cut-the-knot.org/proofs/SylvesterGallai.shtml

The Sylvester Problem has been posed by James Joseph Sylvester in 1893 in Educational Times:

Let n given points have the property that the line joining any two of them passes through a third point of the set. Must the n points all lie on one line?

T. Gallai’s proof has been outlined by P. Erdös in his submission of the problem to The American Mathematical Monthly in 1943.

Solution

Given the set Π of noncollinear points, consider the set of lines Σ that pass through at least two points of Π. Such lines are said to be connecting. Among the connecting lines, those that pass through exactly two points of Π are called ordinary.

Choose any point p1Π. If p1 lies on an ordinary line we are done, so we may assume that p1 lies on no ordinary line. Project p1 to infinity and consider the set of connecting lines containing p1. These lines are all parallel to each other, and each contains p1 and at least two other points of Π. Any connecting line not through p1 forms an angle with the parallel lines; let s be a connecting line (not through p1) which forms the smallest such angle:

Gallai's proof of Sylvester's problem, part 1

Then s must be ordinary! For suppose s were to contain three (or more) points of Π, say, p2, p3, p4 named so that p3 is between p2 and p4:

Gallai's proof of Sylvester's problem, part 2

The connecting line through p3 and p1 (being not ordinary) would contain a third point of Π, say p5, and now either the line p2p5 or the line p4p5 would form a smaller angle with the parallel lines than does s.

References

  1. P. Borwein, W. O. J. Moser, A survey of Sylvester’s problem and its generalizations, Aequationes Mathematicae 40 (1990) 111 – 135
  2. P. Erdös, R. Steinberg, Problem 4065 [1943, 65], The American Mathematical Monthly, Vol. 51, No. 3 (Mar., 1944), pp. 169-171
  3. J. J. Sylvester, Educational Times, Mathematical Question 11851, vol. 59 (1893), p. 98

Chứng minh rằng: $latex (4m)!$ chia hết cho $latex 24^m$.

Chứng minh rằng:  (4m)! chia hết cho 24^m.

Lời giải.

Ta chứng minh bằng quy nạp.

Với m=14! =24 chia hết cho 24, nên khẳng định đúng.

Giả sử khẳng định đúng với m=k, k\ge 1, tức là (4k)! chia hết cho 24^k.

Ta cần chứng minh (4(k+1))! chia hết cho 24^{k+1}.

Thật vậy, do (4(k+1))! =(4k)!.(4k+1).(4k+2).(4k+3).(4k+4) nên theo giả thiết quy nạp ta cần chứng minh

(4k+1).(4k+2).(4k+3).(4k+4) chia hết cho 24.

Đây là tích của 4 số tự nhiên liên tiếp nên luôn chia hết cho 4! =24.

Cách khác:

Xét tập A={1,2,3,....,4m}

Số các số chia hết cho 4 trong Am(1)

Số các số chia hết cho 2 trong A2m

\Rightarrow Số các số chia hết cho 2 mà không chia hết cho 4 trong A là: 2m-m=m (2)

Từ (1),(2) suy ra (4m)! chia hết cho 4^m.2^m (a)

Số các số chia hết cho 3 trong A là: [\frac{4m}{3}]\geq m \Rightarrow (4m)! chia hết cho 3^m (b)

Kết hợp a,b ta có đpcm.

Theo: http://math.vn

Problem of division boy and girl set

TST Lam Dong 2010

Make n boys and n girls a line. Divide the line by two parts such that number of boys and number of girls are equivalent. Let A be number of cases which cannot divide, let B be number of cases which can divide by one way. Prove that B = 2A.

Solution. One way division the line is choosing k boys and k girls. The line has two part, left part and right part. And two ways division are equivalent if their left part has same of number boys and girls.

With the only way division, (suppose k boys and k girls in left part), we change a boy in left part with a girl in right part then we attain a impossible way. And we change a girl in left part with a boy in right part then we attain a impossible way too.

So we have correspondence of one-one: the one way division and two impossible way division, this implies B = 2A. QEA