MathDB

1

measurablility of level sets

f(x) = \sum_{n=0}^{\infty} 2^{-n} ||2^n x||

, where ||x|| is the distance between x and the closest integer to x. Are the level sets

\{ x \in [0,1] : f(x)=y \}

Lebesgue measurable for almost all

y \in f(R)

?

2

1

finite tree graph

Let T be a finite tree graph that has more than one vertex. Let s be the largest number of vertices of a subtree

X \subset T

for which every vertex of X has a neighbor other than X. Let t be the smallest positive integer for which each edge of T is contained in exactly t stars, and each vertex of T is contained in at most 2t - 1 stars. (That is, the stars can be represented by multiplicity.) Prove that s = t. Note: a star of T is a vertex with degree

\geq

3 , including its neighouring edges and vertices.

11

1

simple random walk

Let

\alpha

be an irrational number, and denote

F = \{ (x,y) \in R^2 : y \geq \alpha x \}

as a closed half-plane bounded by a line. Let

P(\alpha,n) = P(X_1,...,X_n \in F)

, where

X_n

is a simple, symmetric random walk that starts at the origin and moves with probability 1/4 in each direction. Prove that

P(\alpha,n)

does not depend on

\alpha

.

3

1

graph with same color edges

G is a complete geometric graph such that for any 4-coloring of its edges, we can find n edges which are pairwise disjoint and have the same color. Prove that the minimum number of vertices of G is 6n-4. a graph with 6n-4 vertices has 2n-1 pairwise disjoint edges with 1 of 2 colors. by PP, there exist n pairwise disjoint edges of the same color.

5

1

third order points in finite field

let

F_q

be a finite field with char ≠ 2, and let

V = F_q \times F_q

be the 2-dimensional vector space over

F_q

. Let L ⊂ V be a subset containing lines in all directions. The order of a point in V is the number of lines in L that pass through the point. Prove that L contains at least q lines having a third-order point.

10

1

half-space cuts

Let

K_1,...,K_d

be convex, compact sets in

R^d

with non-empty interior. Suppose they are strongly separated, which means for any choice of

x_1 \in K_1, x_2 \in K_2, ...

, their affine hull is a hyperplane in

R^d

. Also let

0< \alpha_i <1

. A half-space H is called an

\alpha

-cut if

vol(K_i \cap H) = \alpha_i\cdot vol(K_i)

for all i. How many

\alpha

-cuts are there?

9

1

self homeomorphism of circle

Does the circle T = R / Z have a self-homeomorphism

\phi

that is singular (that is, its derivative is almost everywhere 0), but the mapping

f:T \to T

,

f(x) = \phi^{-1} (2\phi(x))

is absolutely continuous?

7

1

periodic function decomposition

Suppose that the function

f: Z \to Z

can be written in the form

f = g_1+...+g_k

, where

g_1,. . . , g_k: Z \to R

are real-valued periodic functions, with period

a_1,...,a_k

. Does it follow that f can be written in the form

f = h_1 +. . + h_k

, where

h_1,. . . , h_k: Z \to Z

are periodic functions with integer values, also with period

a_1,...,a_k

?

6

1

GP free sets

Let G (n) = max | A(n) |, where A(n) ranges over all subsets of {1,2,...,n} and contains no three-member geometric series, ie, there is no

x, y, z \in A

such that x < y < z and xz = y^2. Prove that

\lim_{n \to \infty} \frac{G (n)}{n}

exists.

4

1

partially ordered, connected set

let P be a finite set with at least 2 elements. P is a partially ordered and connected set.

p:P^3 \to P

is a 3-variable, monotone function which satisfies p(x,x,y)=y. Prove that there exists a non-empty subset

I \subset P

such that

\forall x \in P

\forall y \in I

, we have

p(x, y, y) \in I

.
[P is connected means that if each element is replaced by vertices and there is an edge between 2 vertices iff the 2 elements can be compared, then the graph is connected. p is monotone means that if

x_1\leq y_1 , x_2\leq y_2 , x_3\leq y_3

, then

p(x_1,x_2,x_3)\leq p(y_1,y_2,y_3)

.]

1

topology

Prove that if X is a compact

T_2

space, and X has density d(X), then

X^3

contains a discrete subspace of cardinality

d(X)

. note:

d(X)

is the smallest cardinality of a dense subspace of X.

2006 Miklós Schweitzer

Subcontests

measurablility of level sets

finite tree graph

simple random walk

graph with same color edges

third order points in finite field

half-space cuts

self homeomorphism of circle

periodic function decomposition

GP free sets

partially ordered, connected set

topology

2006 Mikl&oacute;s Schweitzer

Subcontests

measurablility of level sets

finite tree graph

simple random walk

graph with same color edges

third order points in finite field

half-space cuts

self homeomorphism of circle

periodic function decomposition

GP free sets

partially ordered, connected set

topology

2006 Miklós Schweitzer