Problem 1. Let be a subset of the closed unit sphere in such that a dense system of chords of the unit sphere is disjoint from . Prove that there exists a closed subset of the unit sphere such that a chord connecting any two points of is disjoint from .
Problem 2. Let be a van der Jorput series, that is, if the binary representation of the positive integer is , then . Let be the set of points on the plane of the form . Let be the graph with vertex set that is connecting any two points if and only if there is a rectangle which lies in a parallel position to the axes and . Prove tha tthe chromatic number of is finite.
Problem 3. Let be a finite set and be a binary relation on it such that for any , if , and then either or (or possibly both). Let be minimal such that for any there exists such that either or (or possibly both). Supposing that has at most elements that are pairwise not in relation , prove that has at most elements.
Problem 4. Let be a series of positive integers with and for any arbitrary prime number the set is a complete remainder system modulo . Prove that .
Problem 5. We denote for an integer . For which are there polynomials with real coefficients and degrees smaller than such that .
Problem 6. Let be a permutation group on the finite set . Consider such that and for any there is a unique such that . Prove that if the elements of are conjugate in then is -transitive on .
Problem 7. We call a bar of width on the surface of the unit sphere centered at the origin a spherical segment which has width and is symmetric with respect to the origin. Prove that there exists a constant such that for any positive integer the surface can be covered with bars of the same width so that any point is contained in no more than bars.
Problem 8. Prove that all continuous solutions of the functional equation
are constant functions.
Problem 9. For a function defined on let us denote the neignborhood of unit raduis of the set of roots of . Prove that for any compact set there exists a constant such that if is an arbitrary real harmonic function on which vanishes in a point of then
Problem 10. Let be a continuously differentiable, strictly convex function. Let be a complex Hilbert space and be bounded, self adjoint linear operators on . Prove that if then . (not sure if this is right, since I can’t imagine what means)
Problem 11. For , where is composed of a finite number of closed intervals, we start a two dimensional Brownian motion from the point terminating when we first hit . Let be the probability of this finish point being in . Prove that is increasing on the interval .
Many thanks to Eles Andras for the translation. Solutions should not be discussed until the end of the competition: November the 2nd 2015.
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 significant digits:
notice that using only the first significant digits we have made an error of . 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.
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
In 2002 the SIAM News magazine published a list of problems in numerical analysis. The answer to each of the problems should be given with an accuracy of at least digits. And so there came the Hundred-Dollar, Hundred-Digit Challenge. I present below my attempt to solving the 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
Let and suppose is a triangle such that there exists a point which satisfies , , . What is the relative position of with respect to the triangle such that
a) The area is maximized;
b) The perimeter is maximized.
This was inspired by this answer on Math Overflow.
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 points in about 5 seconds.
In general, curves of constant curvature in are not necessarily simple to describe. Here is a non trivial example. If instead of curves living in 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.