MathLinks Forum LaTeX Help AoPS Classes Books Classroom MathLinks Contest Math Resources

The time now is Tue Feb 09, 2010 5:48 pm
All times are UTC + 2		 View posts since last visit
View unanswered posts

Poll

Evaluate olympiad problems please

Excellent
42%
 42%  [ 3 ]
Good
28%
 28%  [ 2 ]
Some are good, some not
14%
 14%  [ 1 ]
Not so good
14%
 14%  [ 1 ]
Awful
0%
 0%  [ 0 ]

Total Votes : 7
 

13th International Scientific Olympiad in Mathematics
View previous topicView next topic
Home » Forum » College Playground » Contests & Research Topics for Undergrads » Other Undergrad Contests
 

Moderators: College Playground Moderators 
3 Posts • Page 1 of 1
Author Message
dmitin
Poincare Conjecture
Poincare Conjecture


Offline
Joined: 05 Feb 2005
Posts: 141
Location: Kyiv, Ukraine
Ukraine
To rate posts you must be logged in
#1
13th International Scientific Olympiad in Mathematics
Iran 2008 http://olympiad.sanjesh.org/en/index.asp
The 13th International Scientific Olympiad in Mathematics
for University Students
15-18 July 2008
Shahid Beheshti University, Tehran, I.R. Iran

First Day

I. Mathematical Analysis (2 hours)

1. (25 points) Suppose \mathfrak{X} is a compact metric space and T: \mathfrak{X}\to\mathfrak{X} be a continuous map. For each x\in\mathfrak{X} let \omega(x) be the set of all limit points of \{T^nx: n = 0,1,2,\ldots\}. Show that:
a. \omega(x) is a nonempty compact subset of \mathfrak{X}.
b. T(\omega(x)) = \omega(x).

2. (25 points) Let (c_n) be a sequence of strictly positive numbers such that \sum\limits_{n = 1}^{\infty}c_n = \infty.
a. Show that, there exists a sequence \{x_n: n\in\mathbb{N}\} which is dense in \mathbb{R} and every point of \mathbb{R} belongs to an infinite number of I_n = (x_n - c_n,x_n + c_n), for n\in\mathbb{N}.
b. Let f(x_n) = c_n and f(x) = 0, if x is distinct from all the x_n's, and \lim\limits_{n\to\infty}c_n = 0. Then f is differential at no point of \mathbb{R}.

3. (25 points) a. Let f be a piecewise continuously differentiable function on the interval [0,a] and f(0) = 0, then
\int_0^a\lvert f'(t)f(t)\rvert\,\mathrm{d}t\le\frac {a}{2}\int_0^a\lvert f'(t)\rvert^2\,\mathrm{d}t.
b. When does equality hold?

4. (25 points) Suppose f_n is a sequence of increasing functions on [0,1] (i.e., for all n, if x_1 < x_2 then f_n(x_1) < f_n(x_2)) which converges pointwise to a continuous function g(x). Prove that the convergence ia actually uniform on [0,1].

II. Numerical Analysis (2 hours)

1. (25 points) Let function f(x) be four times continuously differentiable and have a simple zero \xi. Successive approximations x_n, n = 1,2,\ldots to \xi are computed from
x_{n + 1} = \frac {1}{2}(x_{n + 1}' + x_{n + 1}''),
where x_{n + 1}' = x_n - \dfrac{f(x_n)}{f'(x_n)}, x_{n + 1}'' = x_n - \dfrac{g(x_n)}{g'(x_n)}, g(x) = \dfrac{f(x)}{f'(x)}.
Prove that if the sequence \{x_n\} converges to \xi, then the rate of convergence is cubic.

2. (25 points) Suppose that p(x) is the interpolating polynomial of degree less than or equal to n to (n + 1)-continuously differentiable function f(x) at distinct points x_i, 0\le i\le n. Prove that for any k, 0\le k\le n, there are points y_0,\ldots,y_{n - k} so that for any x there exists a corresponding \xi_x satisfying,
f^{(k)}(x) - p^{(k)}(x) = \frac {f^{(n + 1)}(\xi_x)}{(n - k + 1)!}\prod_{i = 0}^{n - k}(x - y_i),
where f^{(k)} and p^{(k)} denote the kth derivative of f and p respectively.

3. (25 points) Consider the following iteration formula for estimating A^{ - 1} of an n\times n symmetric positive definite matrix A,
X_{n + 1} = X_n + q(AX_n - I),\qquad(*)
where q is a constant and I is the n\times n identity matrix.
i) Under what conditions on q (in terms of the eigenvalues of A), the iteration formula (*) converges to A^{ - 1}?
ii) What should the value of q be so that the convergence is as fast as possible?

4. (25 points) Consider the following quadrature rule
\int_0^{3h}f(x)\,\mathrm{d}x\approx\alpha_1f(0) + \alpha_2f(2h) + \alpha_3f(3h).\qquad(**)
i) Find \alpha_1, \alpha_2 and \alpha_3 such that the rule has highest order (or degree) of precision.
ii) Write the composite rule of (**) for \displaystyle\int_a^bf(x)\,\mathrm{d}x with h = \dfrac{b - a}{3n}, x_i = a + ih, i = 0,1,\ldots,3n.
iii) Which one of the following integrals can be approximated by the composite rule of (**)?
a) \displaystyle\int_0^1\frac {\tan x}{\sqrt {1 - x}}\,\mathrm{d}x,
b) \displaystyle\int_{ - 1}^1\frac {\cos x}{\sqrt {1 - x^2}}\,\mathrm{d}x,
c) \displaystyle\int_0^1\frac {\cos x}{\sqrt {x}}\,\mathrm{d}x.

Second Day

III'. Algebra (2 hours)

1. (25 points) Prove that there is no ring epimorphism f: \mathcal{M}_2(\mathbb{R})\to\mathcal{M}_3(\mathbb{R}), where \mathbb{R} is the field of real numbers.

2. (25 points) Let R be an arbitrary ring and let Z(R) be the center of R. Prove that: If x^2\in Z(R) for all x\in R, then (xy)^2 = (yx)^2 for all x,y\in R.

3. (25 points) Let G be a finite group and for every subgroup H of G there is a homomorphism f: G\to H such that f(h) = h for all h\in H. Prove that G is isomorphic to a direct product of cyclic groups of prime order.

4. (25 points) Let G be a non-trivial group such that every normal subgroup of G is finitely generated. Prove that there is no non-trivial normal subgroup N of G such that G\cong\dfrac{G}{N}.

III''. Operations Research (2 hours)

1. (25 points) Consider the linear programming problem (P),
\min z = c^Tx
\text{s.\,t. } Ax = b\qquad\text{(P)}
\quad x\ge0.
a) Prove that a feasible point for (P) is optimal if and only if there exist v and w so that:
c - A^Tw - v = 0
v\ge0
v^Tx = 0.
b) Prove that if c\ge0, then the problem (P) can not be infinite.

2. (25 points) Prove that a network G = (V,A), with a finite number of vertices V and set of arcs A has infinite flow if and only if there exists a forward path from the source s to sink t with all its arcs having infinite capacity.

3. (25 points) Consider the following primal and dual problems
\min c^Tx,\quad\max b^Ty
x\in P\qquad(y,s)\in D
where P = \{x\mid Ax = b,\ x\ge0\}, D = \{y\mid A^Ty + s = c,\ s\ge0\}, A is a full rank m\times n (m < n) matrix, c,x,s\in\mathbb{R}^n and y,b\in\mathbb{R}^m. Prove:
i) If \exists\overline{x}\in P, \overline{x} > 0 and \exists(\overline{y},\overline{s})\in D, \overline{s} > 0 then both primal and dual problems have optimal solutions.
ii) Let P^{*} = \{x\in P, x is optimal\} and D^{*} = \{(y,s)\in D, (y,s) is optimal\}. Then P^{*} and D^{*} are bounded sets.

4. (25 points) Assume S is a compact convex subset of \mathbb{R}^n, and f: \mathbb{R}^n\to\mathbb{R} is a continuously differentiable convex function on S. Show that for any two optimal points y and z for the problem,
\min f(x)
\text{s.\,t. }x\in S,
we have,
\nabla f(y) = \nabla f(z).

IV. Linear Algebra (2 hours)

1. (33.3 points) Let T_1,T_2,\ldots,T_m be linear transformations of an n-dimensional vector space V. Suppose that:
(i) \dim\mathrm{Im}(T_i) = 1, for all i = 1,2,\ldots,m.
(ii) T_i^2\ne0 and T_iT_j = 0 for each i\ne j.
Prove that m\le n.

2. (33.3 points) Let A, B and C be n\times n matrices over a field such that AB + C = I_n. If there exists an n\times n matrix X such that A + CX is invertible, show that there exists an n\times n matrix Y such that B + YC is invertible.

3. (33.3 points) Let F be a field with at least three elements. If A\in\mathcal{M}_n(F), \mathrm{rank}(A) = n - 1, and moreover A has no zero row, then prove that there exists X\in F^n such that no entry of the vector AX is zero.
results_rename-to-djvu.pdf
Description  Results of the Olympiad (file extension should be renamed to djvu)
 pdf

 Download 
Filename  results_rename-to-djvu.pdf 
Filesize  44.24KB 
Downloaded  216 Time(s) 
problems.pdf
Description  Problems of the Olympiad (in pdf file)
 pdf

 Download 
Filename  problems.pdf 
Filesize  86.86KB 
Downloaded  253 Time(s) 
_________________
Cheating is dark side of teaching. Let's vote to vote or not to vote. Let's triple-check everything.
lib.mexmat.ru/forum = dxdy.ru

PostPosted: Tue Jul 22, 2008 8:29 pm
brunojoyal
P versus NP
P versus NP

Offline
Joined: 23 Mar 2009
Posts: 29
To rate posts you must be logged in
#2
IV. 1

Let R(T) = Im(T).

R(T_i^2) \subseteq R(T_i)

0<rank(T_i^2) \leq rank(T_i) = 1

Hence rank(T_i^2)=1, and R(T_i^2)=R(T_i). Hence T_i^2 : R(T_i) \rightarrow R(T_i) is bijective.

Moreover T_iT_j(V) = T_i(R(T_j)) = \{0\} for j \neq i. Hence R(T_j) \subseteq Kernel(T_i) for i \neq j.

Now suppose we take a nonzero vector in each of R(T_1), ..., R(T_m); say we get x_1, ..., x_m. Then if these vectors are linearly dependent, we can write

0 = \sum_{j=1}^ma_jx_j

where at least one of the a's is nonzero, say a_i. Then

x_i = \frac{-1}{a_i}\sum_{j=1, \: j \neq i}^ma_jx_j

T_i^2(x_i) = \frac{-1}{a_i}\sum_{j=1, \: j \neq i}^ma_jT_i^2(x_j)

But x_j \in R(T_j) \subseteq Kernel(T_i) for i \neq j, hence the right hand side is zero. But the left hand side is nonzero since x_i \neq 0 and T_i^2 : R(T_i) \rightarrow R(T_i) is bijective. Contradiction; hence \{x_1, ..., x_m\} are linearly independent, and m \leq n.

PostPosted: Fri Apr 03, 2009 6:33 pm
QuyBac
Riemann Hypothesis
Riemann Hypothesis


Offline
Joined: 01 Jul 2008
Posts: 450
Location: Viet Nam - France
Viet NamFrance
To rate posts you must be logged in
#3
II.3)We have \forall m \in \mathbb{N^{*}}
X_{m+1}=X_n+q(AX_n-I) then X_{m+1}-A^{-1}=(I+qA)(X_m-A^{-1})
By induction we have : X_m-A^{-1}=(I+qA)^{m-1}(X_1-A^{-1}),\forall k \geq 1
1)Put \lambda_1,\lambda_2,..,\lambda_n are positive eigenvalues of A and \lambda_s=Max_{1 \leq k \leq n}{\lambda_k} then conditions on q (in terms of the eigenvalues of A ), the iteration formula converges to A^{-1}
are |1+q\lambda_k|<1,\forall k\in \mathbb{N^{*}} or \frac{-2}{\lambda_k} <q<0,\forall k\in \mathbb{N^{*}} than if \frac{-2}{\lambda_s} <q<0 need find.
2)q=0 so that the convergence is as fast as possible.X_m=X_1

PostPosted: Sun Apr 05, 2009 3:06 am
Display posts from previous:   Sort by:   
3 Posts • Page 1 of 1
Home » Forum » College Playground » Contests & Research Topics for Undergrads » Other Undergrad Contests
 
View previous topicView next topic
Jump to:  


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum

Created and Maintained by Valentin Vornicu - (c) AoPS Inc. 2004-2008