MathDB
Problems
Contests
Undergraduate contests
Miklós Schweitzer
1992 Miklós Schweitzer
1992 Miklós Schweitzer
Part of
Miklós Schweitzer
Subcontests
(9)
8
1
Hide problems
set of filters compatible with topology
Let
F
F
F
be a set of filters on X so that if
σ
,
τ
∈
F
\sigma, \tau \in F
σ
,
τ
∈
F
,
∀
S
∈
σ
\forall S \in\sigma
∀
S
∈
σ
,
∀
T
∈
τ
\forall T\in\tau
∀
T
∈
τ
, we have
S
∩
T
≠
∅
S \cap T\neq\emptyset
S
∩
T
=
∅
, then
σ
∩
τ
∈
F
\sigma \cap \tau \in F
σ
∩
τ
∈
F
. We say that
F
F
F
is compatible with a topology on X when
x
∈
X
x \in X
x
∈
X
is a contact point of
A
⊂
X
A\subset X
A
⊂
X
, if and only if , there is
σ
∈
F
\sigma \in F
σ
∈
F
such that
x
∈
S
x \in S
x
∈
S
and
S
∩
A
≠
∅
S \cap A \neq\emptyset
S
∩
A
=
∅
for all
S
∈
σ
S \in\sigma
S
∈
σ
.When is there an
F
F
F
compatible with the topology on X in which finite subsets of X and X are closed ?contact point is also known as adherent point.
3
1
Hide problems
congruence distributive algebra
Call a (non-trivial) lattice class a pseudo-variety if it is closed under taking a homomorphic image, a direct product, and a convex subset. Prove that the smallest distributive pseudo-variety cannot be defined by a first-order set of formulas.
9
1
Hide problems
convex hull
Let K be a bounded, d-dimensional convex polyhedron that is not simplex and P is a point on K. Show that if vertices
P
1
,
.
.
.
,
P
k
P_1 , ..., P_k
P
1
,
...
,
P
k
are not all on the same face of K, then one of them can be omitted so that the convex hull of the remaining vertices of K still contains P.caratheodory's theorem might be useful.
10
1
Hide problems
perfect matching in square
We place n points in the unit square independently, according to a uniform distribution. These points are the vertices of a graph
G
n
G_n
G
n
. Two points are connected by an edge if the slope of the segment connecting them is nonnegative. Denote by
M
n
M_n
M
n
the event that the graph
G
n
G_n
G
n
has a 1-factor. Prove that
lim
n
→
∞
P
(
M
2
n
)
=
1
\lim_{n \to \infty} P(M_ {2n}) = 1
lim
n
→
∞
P
(
M
2
n
)
=
1
.
7
1
Hide problems
topology
Prove that in a topological space X , if all discrete subspaces have compact closure , then X is compact.
6
1
Hide problems
analysis
Let
E
⊂
[
0
,
1
]
E \subset [0,1]
E
⊂
[
0
,
1
]
be a Lebesgue measurable set having Lebesgue measure
∣
E
∣
<
1
2
| E |<\frac{1}{2}
∣
E
∣
<
2
1
. Let
h
(
s
)
=
∫
E
‾
d
t
(
s
−
t
)
2
h (s) = \int _ {\overline {E}} \frac{dt}{{(s-t)}^2}
h
(
s
)
=
∫
E
(
s
−
t
)
2
d
t
where
E
‾
=
[
0
,
1
]
\
E
\overline {E} = [0,1] \backslash E
E
=
[
0
,
1
]
\
E
. Prove that there is one
t
∈
E
‾
t \in \overline {E}
t
∈
E
for which
∫
E
d
s
h
(
s
)
(
s
−
t
)
2
≤
c
∣
E
∣
2
\int_E \frac {ds} {h (s) {(s-t)} ^ 2} \leq c {| E |} ^ 2
∫
E
h
(
s
)
(
s
−
t
)
2
d
s
≤
c
∣
E
∣
2
with some absolute constant c .
5
1
Hide problems
square number
Prove that if the
a
i
a_i
a
i
's are different natural numbers, then
∑
j
=
1
n
a
j
2
∏
k
≠
j
a
j
+
a
k
a
j
−
a
k
\sum_ {j = 1}^n a_j ^ 2 \prod_{k \neq j} \frac{a_j + a_k}{a_j-a_k}
∑
j
=
1
n
a
j
2
∏
k
=
j
a
j
−
a
k
a
j
+
a
k
is a square number.
4
1
Hide problems
graph inequality
show there exist positive constants
c
1
c_1
c
1
and
c
2
c_2
c
2
such that for any
n
≥
3
n\geq 3
n
≥
3
, whenever
T
1
T_1
T
1
and
T
2
T_2
T
2
are two trees on the set of vertices
X
=
{
1
,
2
,
.
.
.
,
n
}
X = \{1, 2, ..., n\}
X
=
{
1
,
2
,
...
,
n
}
, there exists a function
f
:
X
→
{
−
1
,
+
1
}
f : X \to \{-1, +1\}
f
:
X
→
{
−
1
,
+
1
}
for which
∣
∑
x
∈
P
f
(
x
)
∣
<
c
1
log
n
\bigg | \sum_ {x \in P} f (x) \bigg | <c_1 \log n
x
∈
P
∑
f
(
x
)
<
c
1
lo
g
n
for any path P that is a subgraph of
T
1
T_1
T
1
or
T
2
T_2
T
2
, but with an upper bound
c
2
log
n
/
log
log
n
c_2 \log n / \log \log n
c
2
lo
g
n
/
lo
g
lo
g
n
the statement is no longer true.
2
1
Hide problems
sum indivisible by prime
Let p be a prime and
a
1
,
a
2
,
.
.
.
,
a
k
a_1 , a_2 , ..., a_k
a
1
,
a
2
,
...
,
a
k
pairwise incongruent modulo p . Prove that
[
k
−
1
]
[\sqrt {k-1}]
[
k
−
1
]
of the elements can be selected from
a
i
a_i
a
i
's such that adding any numbers different from the selected ones will never give a number divisible by p .