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.
Friday, October 21, 2011
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.
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.
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.
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.
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.
Subscribe to:
Posts (Atom)