Monotonic bijection from naturals to pairs of natural numbers

October 23, 2014 Leave a comment

This is a cute problem I found this evening.

Suppose {\phi : \Bbb{N}^* \rightarrow \Bbb{N}^*\times \Bbb{N}^*} is a bijection such that if {\phi(k) = (i,j),\ \phi(k')=(i',j')} and {k \leq k'}, then {ij \leq i'j'}.

Prove that if {k = \phi(i,j)} then {k \geq ij}.

Proof: The trick is to divide the pairs of positive integers into families with the same product.

\displaystyle \begin{matrix} (1,1) & (1,2) & (1,3) & (1,4) & (1,5) & (1,6) & \cdots \\ & (2,1) & (3,1) & (2,2) & (5,1) & (2,3) & \cdots \\ & & &( 4,1) & & (3,2) & \cdots \\ & & & & & (6,1) & \cdots \end{matrix}

Note that the {M}-th column contains as many elements as the number of divisors of {M}. Now we just just use a simple observation. Let {\phi(k)=(i,j)} be on the {M}-th column (i.e. {ij = M}). If {n \geq 1} then {\phi(k+n)=(i',j')} cannot be on one of the first {M-1} columns. Indeed, the monotonicity property implies {M = ij \leq i'j'}. The fact that {\phi} is a bijection assures us that {\phi(1),...,\phi(k)} cover the first {M-1} columns. Moreover, one element from the {M}-th column is surely covered, namely {(i,j) = \phi(k)}. This means that

\displaystyle k \geq d(1)+...+d(M-1)+1 \geq M = ij,

where we have denoted by {d(n)} the number of positive divisors of {n}.

Solving Poisson’s equation on a general shape using finite differences

October 14, 2014 Leave a comment

One of the questions I received in the comments to my old post on solving Laplace equation (in fact this is Poisson’s equation) using finite differences was how to apply this procedure on arbitrary domains. It is not possible to use this method directly on general domains. The main problem is the fact that, unlike in the case of a square of rectangular domain, when we have a general shape, the boudary can have any orientation, not only the orientation of the coordinate axes. One way to avoid approach this problem would be using the Finite Element Method. Briefly, you discretize the boundary, you consider a triangulation of the domain with respect to this discretization, then you consider functions which are polynomial and have support in a few number of triangles. Thus the problem is reduced to a finite dimensional one, which can be written as a matrix problem. The implementation is not straightforward, since you need to conceive algorithms for doing the discretization and triangulation of your domain.

One other approach is to consider a rectangle {D} which contains the shape {\Omega} and add a penalization on the exterior of your domain {\Omega}. The problem to solve becomes something like:

\displaystyle (-\Delta +\mu I) u = 1 \text{ on }D

where {\mu} is defined by

\displaystyle \mu(x) = \begin{cases} 0 & x \in \Omega \\ + \infty & x \notin \Omega\end{cases}. \ \ \ \ \ (1)

Note that doing this we do not need to impose the boundary condition {u=0} on {\partial \Omega}. This is already imposed by {\mu}, and the fact that {u} is forced to be zero outside {\Omega}.

Read more…

Generalized version of Lebesgue dominated convergence theorem

October 10, 2014 Leave a comment

The following variant of the Lebesgue dominated convergence theorem may be useful in the case we can not dominate a sequence of functions by only one integrable function, but by a convergent sequence of integrable functions.

Let {(f_n)} be a sequence of measurable functions defined on a measurable set {\Omega} with real values, which converges pointwise almost everywhere to {f}. Suppose that there exists a sequence of positive, integrable functions {g_n} such that the two following conditions hold:

  • {|f_n(x)|\leq g_n(x)} for almost every {x \in \Omega};
  • There exists an integrable function {g} such that {(g_n) \rightarrow g} in {L^1(\Omega)}.


\displaystyle \lim_{n \rightarrow \infty} \int_\Omega f_n = \int_\Omega f

Read more…

Necessary condition for the uniform convergence of a certain series

October 8, 2014 Leave a comment

Let {a_n} be a decreasing sequence of positive numbers such that the series

\displaystyle \sum_{n = 1}^\infty a_n \sin(nx)

is uniformly convergent. Then {(a_n)} must satisfy {(na_n) \rightarrow 0}.

Note that this result implies that the series {\sum_{n=1}^\infty a_n \sin(nx)} is not uniformly convergent on {\Bbb{R}}. It is surprisngly similar to the following result:

Suppose that {(a_n)} is a decreasing sequence of positive real numbers such that the series {\sum_{n=1}^\infty a_n} is convergence. Then {(na_n) \rightarrow 0}. It is no surprise that the proofs of these two results are similar.

Read more…

Shrinkable polygons

October 7, 2014 Leave a comment

Here’s a nice problem inspired from a post on MathOverflow: link

We call a polygon shrinkable if any scaling of itself with a factor {0<\lambda<1} can be translated into itself. Characterize all shrinkable polygons.

It is easy to see that any star-convex polygon is shrinkable. Pick the point {x_0} in the definition of star-convex, and any contraction of the polygon by a homothety of center {x_0} lies inside the polygon.

Read more…

Qualitative study of a differential equation

September 26, 2014 Leave a comment

Consider the following Cauchy problem:

\displaystyle x'(t)=\sqrt{1+x(t)-x^4(t)},\ x(0)=0.

Prove that any solution {x} of the above problem cannot be bounded on {\Bbb{R}}.

Read more…

IMC 2014 Day 2 Problem 5

August 1, 2014 2 comments

For every positive integer {n}, denote by {D_n} the number of permutations {(x_1,...,x_n)} of {(1,2,...,n)} such that {x_j \neq j} for every {1 \leq j \leq n}. For {1 \leq k \leq \frac{n}{2}}, denote by {\Delta(n,k)} the number of permutations {(x_1,...,x_n)} of {(1,2,...,n)} such that {x_i = k+i} for every {1 \leq i \leq k} and {x_j \neq j} for every {1 \leq j \leq n}. Prove that

\displaystyle \Delta(n,k) = \sum_{i = 0}^{k-1} {k-1 \choose i} \frac{D_{(n+1)-(k+i)}}{n-(k+i)}.

IMC 2014 Day 2 Problem 5


Get every new post delivered to your Inbox.

Join 345 other followers

%d bloggers like this: