Deng Sir's Blog: 2011

Sunday, December 11, 2011

突然失望

當重新啟動這個blog的時候，發現自己常用的LaTex 支持卻突然不能繼續，換了這個域名卻不能隨心所欲，想blogger的開發人員反映了，如果能繼續支持，將繼續在此寫數學的心得，也希望明天開始，我能夠真的專注於中學的數學教學法。

在網頁上面看到如何在blogger上面插入Latex公式的方法：

To enable MathJax, just drop in

<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js">
MathJax.Hub.Config({
 extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js"],
 jax: ["input/TeX", "output/HTML-CSS"],
 tex2jax: {
     inlineMath: [ ['$','$'], ["\\(","\\)"] ],
     displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
 },
 "HTML-CSS": { availableFonts: ["TeX"] }
});
</script>

after the header (<head>) in the Blogger template (Design→Edit HTML→Edit Template).

Monday, November 28, 2011

The problem of the week of purdue university seems a little boring on last few problems. Here is another website from The Mathematics Department of the Hong Kong University of Science and Technology
http://www.math.ust.hk/excalibur/, which is more challenge.

Wednesday, November 9, 2011

Problem 11 fall 2011

The problem 11 of POW is quite interesting.
The system can be simplified.
Let $x_i$ represent the ith man, $d(x_i, x_j)$ is the distance between ith and jth man. Because all men shoot at the same time, so if $d(x_i, x_j)< \min \{ d(x_i,x_k), d(x_j,x_k)\}$, then $x_i, x_j$ die at the same time. So the each pair of $x_i, x_j$ which isolate far away from the others will be both dead at the same time, that means these kinds of pair men can be canceled from the whole. Beside these, there is another kind of situation. That is $d(x_i,x_{i+1})$<$d(x_{i+1},x_{i+2})$<$d(x_{i+2},x_{i+3})$ like a chain or like the domino. Here the first two men will shoot each other, only the last man will survive in a chain.
The question is, if there are two chain remain, what will happen? All last one of each chain will remain alive.
If n is odd number, simplified the whole, then get some chains. Then all the last of chain will remain alive. Since n is odd number, so there at least one chain in the whole (may be need detail discussion).
If n is even number, all men are paired isolated, then n men die without any survival.

Thursday, November 3, 2011

Problem 10 fall 2011

Problem 9 is a little hard for me to solve, because I did not touch the series problem for at least 4 years. So I do problem 10 first.

There are lots of examples can be list here like this one. Let $a=\sqrt{3}, b=\log_{\sqrt{3}}2$, then
$$a^b=\sqrt{3} ^\log_{\sqrt{3}}2$$ $$ =2 $$
And it is easy know that $\sqrt{3}$ is a irrational number. The following to prove $\log_{\sqrt{3}}2$ is also a irrational number.
If it is not, then $\log_{\sqrt{3}}2 = \frac{p}{q}$, where $(p,q)=1, p,q \in \mathbb{N}$.
Therefore $\sqrt{3}^{p/q}=2$, which can be write as $\sqrt{3}^p=2^q$. Square both side, we get $3^q=4^p$. Since $p,q$ are both nature number ($>0$), but R.H.S. is an odd number, L.H.S is an even number. Then the assumtion faile. Then $\log_{\sqrt{3}}2$ is an irrational number.

Friday, October 21, 2011

Problem 8 fall 2011

Show that, in every polygon with more than three edges, there must be two vertices A,B (not connected by any edge) such that the segment AB lies in the interior of the polygon and meets no edge of the plygon (except A and B).

The proof may be complex enough, but if we accept the triangulation polygon as a lemma or something, then the proof is done. Because select one triangle of the set of triangles, the triangle is inside the polygon, and its edges inside or belong to the polygon. Then there at least one side is not the edge of polygon, and this side of the triangle is what the proposition says. Read the wikipedia for the topic polygon triangulation to generate a proof.

Wednesday, October 12, 2011

Problem 6 fall 2011

I may find the proof to Problem 6 Fall 2011.

The proposition says: Given nine lattice points in space, show that there is an interior lattice point on at least one segment joining a pair of them.

This proof is quick easy. Since there nine lattice points, set one of them as the origin. The vectors of the other points are $ V:=(x_i, y_i, z_i), i=1,2,3, ..., 8 $ .Then there is an interior lattice point on at least on segment joining a pair of them means at least on of the co-ordinates of the eight points has $GCD(x_j, y_j, z_j) > 1, j\in {1,2,3, ..., 8}$.

Consider the co-ordinates of the vectors, E represent Even number, O represents Odd number, Then the eight co-ordinates are:
$(O,O,O), (E,O,O),(O,E,O),(O,O,E), (O,E,E),(E,O,E),(E,E,O),(E,E,E)$
If $(E,E,E)\in V$, which means the co-ordinates are Even number, then the $GCD =2$, so the proposition hold.
If $(E,E,E) \notin V$, the pigeonhole principle tells us that there two of the vector have same pattern. For example $v_1 $ and $v_2$ are $(O,E,O)$ type. new vector $v=v_1-v_2$ is $(E,E,E)$ type. $GCD$ of co-ordinates of $v$ equals to 2, then the proposition hold.

Yeah! Although the proof is not that prefect, it works.

Thursday, October 6, 2011

Problem 7 fall 2011

As I said problem 7 is much easier than problem 6. When I was on the bus, I made a mental draft procedure: the binomail theorom. Using the expansion of it.

The problem says: For every $n\geq2 $, $$\sum_{k=1}^n \dbinom{n}{k}k (-1)^k =0$$. where $\dbinom{n}{k}$ is the usual binomial coefficient.

pf:
Let $$ f(x)=(x-1)^n= \sum_{k=0}^n \dbinom{n}{k} x^k (-1)^{n-k}$$

then $$ \frac{d}{dx}f(x) = n(x-1)^{n-1} = \sum_{k=1}^n \dbinom{n}{k}kx^{k-1} (-1)^{n-k}$$.

It is know that $x=1$ is the $n-1$ degree root of $ \frac{d}{dx}f(x) = 0$.

consider n is even number, then $(-1)^{n-k}=(-1)^k$, for k not greater than n.

Then,$\frac{d}{dx}f(x) \Big|_{x=1}=\sum_{k=1}^n \dbinom{n}{k} k (-1)^k =0 $

If $n$ is odd number, then .
[Rewise Here]. When I was tutoring a student today, I found there is a problem in last term of the original expansion. $\dbinom{n}{n}kx^{k-}(-1)^{n-n-1}$. Maybe that will ok, but I multiple $1=(-1)^2$ to the $\frac{d}{dx}f(x)$.

Because $(-1)^2=1$
$$(-1)^2 \sum_{k=1}^n \dbinom{n}{k} k x^{k-1} (-1)^{n-k} = (-1)\sum_{k=1}^n \dbinom{n}{k} k x^{k-1}(-1)^{n-k+1}$$
Notice that $(-1)^{n-k+1}=(-1)^k $.
Then $ \frac{d}{dx}f(x) \Big|_{x=1} =(-1)\sum_{k=1}^n \dbinom{n}{k} k (-1)^k =0 $ That implies
$$\sum_{k=1}^n \dbinom{n}{k} k (-1)^{n-k} =0 $$ is hold for all the $n\geq2 $.

To complete the proof, there should add the condition n >=2 somewhere, which implies that 1 is the n-degree root of f(x), and (n-1)-degree root of f'(x)=0. Because n>=2, n-1>=1.

Maybe there is typing error. But the steps make sense. If so, the scale of the difficulty of the problem set it too large.

Wednesday, October 5, 2011

Problem 6 fall 2011

Strugle with the problem for many days, but can not find the correct solution. But I think it may use the pigeonhole principle to get the proof. Because there are nine points, and the number of combination of even and odd exactly is 2^3=8, that means 8 to 9 may fits the pigeonhole principle.

There are still something I can think about. The lattice point lies on the segment joining a pair of the other nine points. Set a point as the origin, then the other will be (a_i, b_i, c_i), i=1,2,3,...,8. Then the statement equivalent to there is at least one of the greate common divisor of the co-oridinates not equals to 1. But I do not know how to prove it.

I also illustrate a figure above, considering the pattern like the upper corner. I believe that if there any four points lie on a same plane, they have the same pattern, or otherwise there will be a transformation. And it is know that this kind of transformation can be separated into a scale multiple and a rotation, which is just matter the vector i, j, and k. The coordinates of the point remain unchange. Since there only 8 points, adding one more point will make the GCD of coordinates of its difference(vector) with the original 8 points greater than 1 (at least one vector). [hard to express my idea in english]

This method may solve the problem, but I was wondering am I think it too complex. One hand, because my boss gave me a lot of data to analysis, and the other hand I feel the books of number theory were a little hard to read, so I stop thinking this problem.

Maybe there is easier approach, but take long time to waite the announcement of the answer.

By the way Problem 7 is much easier than Problem 6.

Saturday, September 17, 2011

NAU POTW-2011.09.20

I have found another POTW website, which is called northern Arizona university.

http://www.cefns.nau.edu/Academic/Math/departmentActivities/POTW/

The problem says that:

A very tiny bug starts at the origin in the (x, y) plane. He walks to the right one unit and ends up at (1, 0). Then he makes a left turn and moves forward half a unit, reaching (1, 1/2). Then he turns left again and goes half again as far, reaching (3/4, 1/2). If he keeps doing this (turning left and going half again as far) again and again, what is his limiting position?

It maybe not easy to consider two dimension sequence, and also have the direction changing all the time. But the bug always turn left. That exactly the complex multiple ( multiple a number by i means turn the vector anti-clock wise in 90 degree.).

So the iterative function is z(n)=z(n-1)+(i/2)^(n-1). z(0)=0.
z(n)-z(n-1) =(i/2)^(n-1) ....(n)
z(n-1)-z(n-2)=(i/2)^(n-2)....(n-1)
...
z(1)-z(0)=(i/2)^0 ...(1)

Add all the n equations get z(n) - z(0) = [(i/2)^n-1]/(i/2-1) . So z(n) = [(i/2)^n-1]/(i/2-1)
z(n) -> 1/(1-i/2), when n-> Infinity.
In coordinates expression is {4/5, 2/5}.

I plot the graph with Mathematica

lis = {Re[#], Im[#]} & /@ Table[((I/2)^n - 1)/(I/2 - 1), {n, 0, 18}];
ListPlot[lis, Joined -> True, PlotRange -> {{-0.1, 1.1}, {-0.1, 0.6}}]

problem 3 fall 2011 of purdue POW

To solve problem 3, the pigeonhole principle should be knew first. The pigeonhole principle states that if n items put into m pigeonholes with n>m, then there is at least one pigeonhole must contain more than one item. In Chinese version is called 抽屜原理( drawer principle), which replace the pigeonholes with drawers. Beside this definition, there is another definition such n is greater than k times of m, then there is at least one pigeonhole must contain more than k items.

The problem 3 says: There are nine points in the interior of a cube of side 1. Show that at least two of the points are less than sqrt(3)/2. Can sqrt(3)/2 be replaced by a smaller number?

The idea of how to solve the problem is to set up the pigeonhole, then put the points in to the holes. Since the side of cube equals to 1, half of the side is 1/2. Then we can cut the cube into 8 small cube with side of 1/2. The diagonal of small cube is just sqrt(3). sqrt((1/2)^2+(1/2)^2+(1/2)^2)=sqrt(3)/2. The distance of any two points in the interior of the small cube is less than sqrt(3). Then we set up 8 pigeonholes. But there are 9 points, so at least one small cube contain more than two point. Then the problem is solved.

The further question is easy, but it is hard to explain with english.

容易知道sqrt(3)/2不可以被更小的數代替，其實最極端的放置方法是：將8個點放在大正方形的四個角，而第九個點就放在大正方形的中心位置，那麼他們的距離就剛好都是sqrt(3)/2。但是全部點都放在正方形內部（interior），所以如果sqrt(3)/2換成比sqrt(3)/2的數d，至少有一種方法可以使全部點兩兩之間的距離小於d。

Friday, September 16, 2011

fall 2010 problem 2

fall 2010 problem 2
Show that sin(x) >= x-(x^2)/pi. x belongs to [0,pi].
This problem seems very easy, but spend a lot of my time to finish it. But I post this solution due to the deadline.
let f(x)=sin(x)-x+(x^2)/pi, and going to prove f(x)>=0, which is a necessary and sufficient condition of statement.

[ English is not my first language, so it may hard to read my prove. Then you be better guess what I was going to say ]

pf:
let f(x)=sin(x)-x+(x^2)/pi. then let x=t+pi/2, t belongs to [-pi/2, pi/2].
g(t)=f(t+pi/2)=sin(t+pi/2)+((t+pi/2-pi/2)^2)/pi-pi/4.
so g(t) defines on (-pi/2, pi/2), which is a even function.
Simplify g(t)=cos(t)+((t+pi/2-pi/2)^2)/pi-pi/4.
Here going to prove g(t) >= 0 on [0,pi/2].
Consider g'(t)= -sin(t)+2*t/pi.

Jordan's inequality said sin(x)>= 2x/pi, for 0< x < pi/2.

g'(t) is strictly decreasing on the interval of (0,pi/2). Because g(t) -> 0 as t->pi/2. That means g(t)>=0 on the interval of (0,pi/2).
Since g(t) is a even function on (0,pi/2). So g(t)>=0 on (-pi/2,pi/2). Then f(x)>=0.
#

I also think about the f'(t)=cos(x)-1+2x/pi= -2(sin(x/2))^2+2x/pi. but it seems hard to separate the interval [0, pi] into [0,pi/2] and [pi/2, pi]. Then prove f'(x) is greater or equal to zero on [0,pi/2], and less or equal to zero on [pi/2,pi/2]. I think it is easy to follow. But that will look a little complicate to show. If there is somebody know how to, please tell me.

Wednesday, September 14, 2011

Purdue Problem of the week, Fall 2011 Problem 4

The problem 4 of 2011 fall is:

Show that if: u(x)= Sum { x^(3k)}/{(3k)!};

v(x)= Sum {x^(3k+1)}/{(3k+1)!};

w(x)=Sum {x^(3k+2)}/{(3k+2)!}; where k=0,1,2,3,...

then u^3+v^3+w^3-2uvw=1.

Let f(x) = u^3+v^3+w^3-2uvw, then consider f'(x).

f'(x)=3u'u^2+3v'v^2+3w'w^2-3u'vw-3uv'w-3uvw'.

It is easy to calculate u'=w, v'=u, w'=v. Therefore f'(x)=0, that means f(x) is constant.

Because f(0)=1, so f(x)=1 for all value of x.

Tuesday, September 13, 2011

Purdue的數學問題

Purdue大學的數學問題真的很有意思。這幾天也嘗試著去解一些。發現自己的水平確實比中學時有些退步，當然技術上有進步。不過我覺得它給出的解決方式有些問題（Fall 2011 problem1）。
http://www.math.purdue.edu/pow/
這個問題是：
Show that x^400+x^380+...+x^20+1 is divisible by x^20+x^19+...+x+1.

不過我想到的是，需要在複數域上面解決。因為只有在複數域上面才可以將多項式做完整的factorization，將多項式寫成product of lowest polynomials. 如果不是在複數域上面討論，它給出的解法就是不對的。
f(x)=x^400+x^380+...+x^20+1, g(x)=x^20+x^19+...+x+1.
f(x)=(x^420-1)/(x^20-1); g(x)=(x^21-1)/(x-1);
Consider f(x)=0, x_n=cos(2n*Pi/420)+i sin(2n*Pi/420), where n=0,1,2,...,419.
g(x')=0, x'_n=cos(2n*pi/21)+i sin(2n*Pi/21), where n=0,1,2,...,20.

since cos(2n*pi/21)+i sin(2n*Pi/21)= cos( 40n*Pi/420)+i sin(40n*Pi/420).

Therefore, g(x)|f(x).

因為，解題中沒有提到在複數域中解答，其實有些不好。