Miklos Schweitzer 2015 Problems

October 31, 2015 Leave a comment

Problem 1. Let {K} be a subset of the closed unit sphere in { \Bbb{R}^3} such that a dense system of chords of the unit sphere is disjoint from {K}. Prove that there exists a closed subset {H} of the unit sphere such that a chord connecting any two points of {H} is disjoint from {K}.

Problem 2. Let {\{x_n\}} be a van der Jorput series, that is, if the binary representation of the positive integer is {n = \sum_i a_i2^i}, then {x_n = \sum_i a_i2^{-i-1}}. Let {V} be the set of points on the plane of the form {(n,x_n)}. Let {G} be the graph with vertex set {V} that is connecting any two points {(p,q)} if and only if there is a rectangle {R} which lies in a parallel position to the axes and {R\cap V = \{p,q\}}. Prove tha tthe chromatic number of {G} is finite.

Problem 3. Let {A} be a finite set and {\rightarrow} be a binary relation on it such that for any {a,b,c \in A}, if {a\neq b}, {a \rightarrow c} and {b \rightarrow c} then either {a \rightarrow b} or {b \rightarrow a} (or possibly both). Let {B \subset A} be minimal such that for any {a \in A \setminus B} there exists {b \in B} such that either {a \rightarrow b} or {b \rightarrow a} (or possibly both). Supposing that {A} has at most {k} elements that are pairwise not in relation {\rightarrow}, prove that {B} has at most {k} elements.

Problem 4. Let {a_n} be a series of positive integers with {a_1 = 1} and for any arbitrary prime number {p} the set {\{a_1,a_2,...,a_p\}} is a complete remainder system modulo {p}. Prove that {\lim_{n\rightarrow \infty} a_n/n = 1}.

Problem 5. We denote {f(x) = x^n+x^{n-1}+...+x+1} for an integer {n \geq 1}. For which {n} are there polynomials {g,h} with real coefficients and degrees smaller than {n} such that {f(x) = g(h(x))}.

Problem 6. Let {G} be a permutation group on the finite set {\Omega}. Consider {S \subset G} such that {1 \in S} and for any {x,y \in \Omega} there is a unique {\sigma \in S} such that {\sigma(x)=y}. Prove that if the elements of {S \setminus \{1\}} are conjugate in {G} then {G} is {2}-transitive on {\Omega}.

Problem 7. We call a bar of width {w} on the surface of the unit sphere {\Bbb{S}^2} centered at the origin a spherical segment which has width {w} and is symmetric with respect to the origin. Prove that there exists a constant {c>0} such that for any positive integer {n} the surface {\Bbb{S}^2} can be covered with {n} bars of the same width so that any point is contained in no more than {c\sqrt{n}} bars.

Problem 8. Prove that all continuous solutions of the functional equation

\displaystyle (f(x)-f(y))\left( f\left(\frac{x+y}{2}\right) -f(\sqrt{xy})\right) \equiv 0,\ x,y \in (0,\infty)

are constant functions.

Problem 9. For a function {u} defined on {G \subset \Bbb{C}} let us denote {Z(u)} the neignborhood of unit raduis of the set of roots of {u}. Prove that for any compact set {K \subset G} there exists a constant {C} such that if {u} is an arbitrary real harmonic function on {G} which vanishes in a point of {K} then

\displaystyle \sup_{z \in K} |u(z)| \leq C \sup_{Z(u)\cap G}|u(z)|.

Problem 10. Let {f: \Bbb{R} \rightarrow \Bbb{R}} be a continuously differentiable, strictly convex function. Let {H} be a complex Hilbert space and {A,B} be bounded, self adjoint linear operators on {H}. Prove that if {f(A)-f(B) = f'(B)(A-B)} then {A=B}. (not sure if this is right, since I can’t imagine what {f(A)} means)

Problem 11. For {[0,1] \subset E \subset [0,\infty)}, where {E} is composed of a finite number of closed intervals, we start a two dimensional Brownian motion from the point {x<0} terminating when we first hit {E}. Let {p(x)} be the probability of this finish point being in {[0,1]}. Prove that {p(x)} is increasing on the interval {[-1,0)}.

Many thanks to Eles Andras for the translation. Solutions should not be discussed until the end of the competition: November the 2nd 2015.

Source: http://www.bolyai.hu/schweitzer_feladatsor_2015.pdf

Categories: Uncategorized

Even small errors can be fatal

October 14, 2015 Leave a comment

Machines and computers represent numbers as sequences of zeros and ones called bits. The reason for doing this is the simplicity of constructing circuits dealing with two states. This fact coupled with limited memory capacities means that from the start we cannot represent all numbers in machine code. It is true that we can get as close as we want to any number with great memory cost when precision is important, but in fact we always use a fixed precision. In applications this precision is fixed to a number of bits (16, 32, 64) which correspond to significant digits in computations. Doing math operations to numbers represented on bits may lead to loss of information. Consider the following addition using {15} significant digits:

\displaystyle 5.00000000000002+6.00000000000003 = 11.0000000000000,

notice that using only the first {15} significant digits we have made an error of {5\times 10^{-14}}. This may seem small, but if we do not pay attention and we let errors of this kind accumulate we may have a final error which is unacceptable. This is what happened in the case of the Patriot missile case which I’ll discuss briefly below.

Read more…

SIAM 100-digit challenge no 1 – Matlab and Pari GP

October 14, 2015 Leave a comment

Continuing the SIAM 100-digit challenge presentation I show below how to solve the first problem of the series. A great bibliography for the series is the book entitled The SIAM 100-digit Challenge. A study in high-accuracy numerical computing by Folkmar Bornemann, Dirk Laurie, Stan Wagon, Jorg Waldvogel. The first problem in the series deals with the numerical integration of a highly oscillating function. As stated, the purpose is to obtain at least ten significant digits in the numerical computation.

Problem 1. Compute the limit

\displaystyle \lim_{\varepsilon \rightarrow 0} \int_\varepsilon^1 x^{-1}\cos(x^{-1}\log(x))dx.

Read more…

Categories: Uncategorized

SIAM 100 digit challenge no 4 – Matlab solution

October 11, 2015 Leave a comment

In 2002 the SIAM News magazine published a list of {10} problems in numerical analysis. The answer to each of the problems should be given with an accuracy of at least {10} digits. And so there came the Hundred-Dollar, Hundred-Digit Challenge. I present below my attempt to solving the {4}th problem in this series, as it deals to finding the global minimum of a highly oscillating function. I confess that my approach is rather simplistic, but solves the problem. First let’s state the problem below:

Problem 4. What is the global minimum of the function

\displaystyle e^{\sin(50x)}+\sin(60e^y)+\sin(70\sin x)+\sin(\sin(80y))-\sin(10(x+y))+\frac{1}{4}(x^2+y^2).

Read more…

Optimal triangles with vertices on fixed circles

October 5, 2015 Leave a comment

Let {x,y,z>0} and suppose {ABC} is a triangle such that there exists a point {O} which satisfies {OA=x}, {OB = y}, {OC = z}. What is the relative position of {O} with respect to the triangle {ABC} such that

a) The area is maximized;

b) The perimeter is maximized.

This was inspired by this answer on Math Overflow.

Read more…

Voronoi diagrams on the sphere

October 3, 2015 Leave a comment

Lately I wanted to be able to compute the Voronoi diagram of a family of points on the unit sphere in an efficient way. I started by looking all over the place for implemented results and I found a few: a Python implementation, a Matlab implementation or an online interactive Java implementation. Each of these have their inconveniences: I’m not familiar with Python or Java and the Matlab code is not vectorized, which means it is really slow. So the challenge was on. Luckily, the idea for a fast, efficient algorithm was found here. I present below the main idea, along with some justifications. For the sake of simplicity, suppose we work on the unit sphere.

In order to compute the Voronoi diagram of a set of points on the sphere we need to

  • compute the convex hull of this set of points;
  • the normals to each of the faces give the Voronoi points;
  • the face connectivities provide the connectivities between Voronoi points.

Now, each of these steps has well optimized algorithms which are implemented in numerical software like Matlab. Just to give you an idea, it is possible to compute the Voronoi diagram of a set of {100000} points in about 5 seconds.

Read more…

Categories: Uncategorized

Curve of constant curvature on a sphere

September 29, 2015 Leave a comment

In general, curves of constant curvature in {\Bbb{R}^3} are not necessarily simple to describe. Here is a non trivial example. If instead of curves living in {\Bbb{R}^3} we consider only curves lying on the unit sphere, the situation changes.

Problem. If a smooth, three dimensional curve has constant curvature and is contained in the unit sphere, then it is a piece of a circle.

Read more…


Get every new post delivered to your Inbox.

Join 391 other followers

%d bloggers like this: