Found problems: 141
2022 Miklós Schweitzer, 5
Is it possible to select a non-degenerate segment from each line of the plane such that any two selected segments are disjoint?
1986 Miklós Schweitzer, 10
Let $X_1, X_2$ be independent, identically distributed random variables such that $X_i\geq 0$ for all $i$. Let $\mathrm EX_i=m$, $\mathrm{Var} (X_i)=\sigma ^2<\infty$. Show that, for all $0<\alpha\leq 1$
$$\lim_{n\to\infty} n\,\mathrm{Var} \left( \left[ \frac{X_1+\ldots +X_n}{n}\right] ^\alpha\right)=\frac{\alpha ^ 2 \sigma ^ 2}{m^{2(1-\alpha)}}$$
[Gy. Michaletzki]
2003 Miklós Schweitzer, 2
Let $p$ be a prime and let $M$ be an $n\times m$ matrix with integer entries such that $Mv\not\equiv 0\pmod{p}$ for any column vector $v\neq 0$ whose entries are $0$ are $1$. Show that there exists a row vector $x$ with integer entries such that no entry of $xM$ is $0\pmod{p}$.
(translated by L. Erdős)
2010 Miklós Schweitzer, 3
Let $ A_i,i=1,2,\dots,t$ be distinct subsets of the base set $\{1,2,\dots,n\}$ complying to the following condition
$$ \displaystyle A_ {i} \cap A_ {k} \subseteq A_ {j}$$for any $1 \leq i <j <k \leq t.$ Find the maximum value of $t.$
Thanks @dgrozev
2008 Miklós Schweitzer, 3
A bipartite graph on the sets $\{ x_1,\ldots, x_n \}$ and $\{ y_1,\ldots, y_n\}$ of vertices (that is the edges are of the form $x_iy_j$) is called tame if it has no $x_iy_jx_ky_l$ path ($i,j,k,l\in\{ 1,\ldots, n\}$) where $j<l$ and $i+j>k+l$. Calculate the infimum of those real numbers $\alpha$ for which there exists a constant $c=c(\alpha)>0$ such that for all tame graphs $e\le cn^{\alpha}$, where $e$ is the number of edges and $n$ is half of the number of vertices.
(translated by Miklós Maróti)
2002 Miklós Schweitzer, 6
Let $K\subseteq \mathbb{R}$ be compact. Prove that the following two statements are equivalent to each other.
(a) For each point $x$ of $K$ we can assign an uncountable set $F_x\subseteq \mathbb{R}$ such that
$$\mathrm{dist}(F_x, F_y)\ge |x-y|$$
holds for all $x,y\in K$;
(b) $K$ is of measure zero.
2008 Miklós Schweitzer, 2
Let $t\ge 3$ be an integer, and for $1\le i <j\le t$ let $A_{ij}=A_{ji}$ be an arbitrary subset of an $n$-element set $X$. Prove that there exist $1\le i < j\le t$ for which
$$\left| \left( X\,\backslash\, A_{ij}\right) \cup \bigcup_{k\neq i,j}\left( A_{ik}\cap A_{jk}\right) \right| \ge \frac{t-2}{2t-2}n$$
(translated by Miklós Maróti)
2004 Miklós Schweitzer, 1
The Lindelöf number $L(X)$ of a topological space $X$ is the least infinite cardinal $\lambda$ with the property that every open covering of $X$ has a subcovering of cardinality at most $\lambda$. Prove that if evert non-countably infinite subset of a first countable space $X$ has a point of condensation, then $L(X)=\sup L(A)$, where $A$ runs over the separable closed subspaces of $X$.
(A point of condensation of a subset $H\subseteq X$ is a point $x\in X$ such that any neighbourhood of $x$ intersects $H$ in a non-countably infinite set.)
1985 Miklós Schweitzer, 12
Let $(\Omega, \mathcal A, P)$ be a probability space, and let $(X_n, \mathcal F_n)$ be an adapted sequence in $(\Omega, \mathcal A, P)$ (that is, for the $\sigma$-algebras $\mathcal F_n$, we have $\mathcal F_1\subseteq \mathcal F_2\subseteq \dots \subseteq \mathcal A$, and for all $n$, $X_n$ is an $\mathcal F_n$-measurable and integrable random variable). Assume that
$$\mathrm E (X_{n+1} \mid \mathcal F_n )=\frac12 X_n+\frac12 X_{n-1}\,\,\,\,\, (n=2, 3, \ldots )$$
Prove that $\mathrm{sup}_n \mathrm{E}|X_n|<\infty$ implies that $X_n$ converges with probability one as $n\to\infty$. [I. Fazekas]
2002 Miklós Schweitzer, 8
Prove that there exists an absolute constant $c$ such that any set $H$ of $n$ points of the plane in general position can be coloured with $c\log n$ colours in such a way that any disk of the plane containing at least one point of $H$ intersects some colour class of $H$ in exactly one point.
2000 Miklós Schweitzer, 6
Suppose the real line is decomposed into two uncountable Borel sets. Prove that a suitable translated copy of the first set intersects the second in an uncountable set.
2016 Miklós Schweitzer, 10
Let $X$ and $Y$ be independent, identically distributed random points on the unit sphere in $\mathbb{R}^3$. For which distribution of $X$ will the expectation of the (Euclidean) distance of $X$ and $Y$ be maximal?
1985 Miklós Schweitzer, 9
Let $D=\{ z\in \mathbb C\colon |z|<1\}$ and $D=\{ w\in \mathbb C \colon |w|=1\}$. Prove that if for a function $f\colon D\times B\rightarrow\mathbb C$ the equality
$$f\left( \frac{az+b}{\overline{b}z+\overline{a}}, \frac{aw+b}{\overline{b}w+\overline a} \right)=f(z,w)+f\left(\frac{b}{\overline a}, \frac{aw+b}{\overline b w+\overline a} \right)$$
holds for all $z\in D, w\in B$ and $a, b\in \mathbb C,|a|^2=|b|^2+1$, then there is a function $L\colon (0, \infty )\rightarrow \mathbb C$ satisfying
$$L(pq)=L(p)+L(q)\,\,\,\text{for all}\,\,\, p,q > 0$$
such that $f$ can be represented as
$$f(z,w)=L\left( \frac{1-|z|^2}{|w-z|^2}\right)\,\,\,\text{for all}\,\,\, z\in D, w\in B$$.
[Gy. Maksa]
2006 Miklós Schweitzer, 2
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.
2000 Miklós Schweitzer, 1
Prove that there exists a function $f\colon [\omega_1]^2 \rightarrow \omega _1$ such that
(i) $f(\alpha, \beta)< \mathrm{min}(\alpha, \beta)$ whenever $\mathrm{min}(\alpha,\beta)>0$; and
(ii) if $\alpha_0<\alpha_1<\ldots<\alpha_i<\ldots<\omega_1$ then $\sup\left\{ a_i \colon i<\omega \right\} =\sup \left\{ f(\alpha_i, \alpha_j)\colon i,j<\omega\right\}$.
Russian TST 2017, P3
Prove that for any polynomial $P$ with real coefficients, and for any positive integer $n$, there exists a polynomial $Q$ with real coefficients such that $P(x)^2 +Q(x)^2$ is divisible by $(1+x^2)^n$.
2008 Miklós Schweitzer, 1
Let $H \subset P(X)$ be a system of subsets of $X$ and $\kappa > 0$ be a cardinal number such that every $x \in X$ is contained in less than $\kappa$ members of $H$. Prove that there exists an $f \colon X \rightarrow \kappa$ coloring, such that every nonempty $A \in H$ has a “unique” point, that is, an element $x \in A$ such that $f(x) \neq f(y)$ for all $x \neq y \in A$.
(translated by Miklós Maróti)
2000 Miklós Schweitzer, 10
Joe generates 4 independent random numbers in $(0,1)$ according to the uniform distribution. He shows one the numbers to Bill, who has to guess whether the number shown is one of the extremal numbers (that is, the smallest or the greatest) of the four numbers or not. Can Joe have a deterministic strategy such that no matter what Bill's method is, the probability of the right guess of Bill is at most $\frac12$?
1986 Miklós Schweitzer, 5
Prove that existence of a constant $c$ with the following property: for every composite integer $n$, there exists a group whose order is divisible by $n$ and is less than $n^c$, and that contains no element of order $n$. [P. P. Palfy]
2007 Miklós Schweitzer, 6
For which subsets $A\subset \mathbb R$ is it true that whenever $0\leq x_0 < x_1 < \cdots < x_n\leq 1$, $n=1,2, \ldots$, then there exist $y_j\in A$ numbers, such that $y_{j+1}-y_j>x_{j+1}-x_j$ for all $0\leq j < n$.
(translated by Miklós Maróti)
2002 Miklós Schweitzer, 10
Let $X_1, X_2, \ldots$ be independent random variables of the same distribution such that their joint distribution is discrete and is concentrated on infinitely many different values. Let $a_n$ denote the probability that $X_1,\ldots, X_{n+1}$ are all different on the condition that $X_1,\ldots, X_n$ are all different ($n\ge 1$). Show that
(a) $a_n$ is strictly decreasing and tends to $0$ as $n\to \infty$; and
(b) for any sequence $1\le f(1)\le f(2) < \ldots$ of positive integers the joint distribution of $X_1, X_2, \ldots$ can be chosen such that
$$\limsup_{n\to\infty}\frac{a_{f(n)}}{a_n}=1$$
holds.
2016 Miklós Schweitzer, 4
Prove that there exists a sequence $a(1),a(2),\dots,a(n),\dots$ of real numbers such that
\[
a(n+m)\le a(n)+a(m)+\frac{n+m}{\log (n+m)}
\]
for all integers $m,n\ge 1$, and such that the set $\{a(n)/n:n\ge 1\}$ is everywhere dense on the real line.
[i]Remark.[/i] A theorem of de Bruijn and Erdős states that if the inequality above holds with $f(n + m)$ in place of the last term on the right-hand side, where $f(n)\ge 0$ is nondecreasing and $\sum_{n=2}^\infty f(n)/n^2<\infty$, then $a(n)/n$ converges or tends to $(-\infty)$.
1985 Miklós Schweitzer, 7
Let $p_1$ and $p_2$ be positive real numbers. Prove that there exist functions $f_i\colon \mathbb R \rightarrow \mathbb R$ such that the smallest positive period of $f_i$ is $p_i\, (i=1, 2)$, and $f_1-f_2$ is also periodic. [J. Riman]
2007 Miklós Schweitzer, 10
Let $\zeta_1, \zeta_2,\ldots$ be identically distributed, independent real-valued random variables with expected value $0$. Suppose that the $\Lambda (\lambda) := \log \mathbb E \exp (\lambda \zeta_i)$ logarithmic moment-generating function always exists for $\lambda\in\mathbb R$ ($\mathbb E$ is the expected value). Furthermore, let $G\colon\mathbb R \rightarrow \mathbb R$ be a function such that $G(x)\leq \min (|x|, x^2)$. Prove that for small $\gamma >0$ the following sequence is bounded:
$$\left\{ \mathbb E \exp \left( \gamma l G \left( \frac 1l (\zeta_1+\ldots + \zeta_l)\right)\right)\right\}^{\infty}_{l=1}$$
(translated by j___d)
2016 Miklós Schweitzer, 3
Prove that for any polynomial $P$ with real coefficients, and for any positive integer $n$, there exists a polynomial $Q$ with real coefficients such that $P(x)^2 +Q(x)^2$ is divisible by $(1+x^2)^n$.