MathDB
Problems
Contests
National and Regional Contests
Iran Contests
Pre-Preparation Course Examination
2004 Pre-Preparation Course Examination
2004 Pre-Preparation Course Examination
Part of
Pre-Preparation Course Examination
Subcontests
(7)
7
1
Hide problems
Colorful subtrees
Let
G
=
(
V
,
E
)
G=(V,E)
G
=
(
V
,
E
)
be a simple graph.a) Let
A
,
B
A,B
A
,
B
be a subsets of
E
E
E
, and spanning subgraphs of
G
G
G
with edges
A
,
B
,
A
∪
B
A,B,A\cup B
A
,
B
,
A
∪
B
and
A
∩
B
A\cap B
A
∩
B
have
a
,
b
,
c
a,b,c
a
,
b
,
c
and
d
d
d
connected components respectively. Prove that
a
+
b
≤
c
+
d
a+b\leq c+d
a
+
b
≤
c
+
d
.We say that subsets
A
1
,
A
2
,
…
,
A
m
A_1,A_2,\dots,A_m
A
1
,
A
2
,
…
,
A
m
of
E
E
E
have
(
R
)
(R)
(
R
)
property if and only if for each
I
⊂
{
1
,
2
,
…
,
m
}
I\subset\{1,2,\dots,m\}
I
⊂
{
1
,
2
,
…
,
m
}
the spanning subgraph of
G
G
G
with edges
∪
i
∈
I
A
i
\cup_{i\in I}A_i
∪
i
∈
I
A
i
has at most
n
−
∣
I
∣
n-|I|
n
−
∣
I
∣
connected components. b) Prove that when
A
1
,
…
,
A
m
,
B
A_1,\dots,A_m,B
A
1
,
…
,
A
m
,
B
have
(
R
)
(R)
(
R
)
property, and
∣
B
∣
≥
2
|B|\geq2
∣
B
∣
≥
2
, there exists an
x
∈
B
x\in B
x
∈
B
such that
A
1
,
A
2
,
…
,
A
m
,
B
\
{
x
}
A_1,A_2,\dots,A_m,B\backslash\{x\}
A
1
,
A
2
,
…
,
A
m
,
B
\
{
x
}
also have property
(
R
)
(R)
(
R
)
.Suppose that edges of
G
G
G
are colored arbitrarily. A spanning subtree in
G
G
G
is called colorful if and only if it does not have any two edges with the same color. c) Prove that
G
G
G
has a colorful subtree if and only if for each partition of
V
V
V
to
k
k
k
non-empty subsets such as
V
1
,
…
,
V
k
V_1,\dots,V_k
V
1
,
…
,
V
k
, there are at least k\minus{}1 edges with distinct colors that each of these edges has its two ends in two different
V
i
V_i
V
i
s. d) Assume that edges of
K
n
K_n
K
n
has been colored such that each color is repeated
[
n
2
]
\left[\frac n2\right]
[
2
n
]
times. Prove that there exists a colorful subtree. e) Prove that in part d) if
n
≥
5
n\geq5
n
≥
5
there is a colorful subtree that is non-isomorphic to
K
1
,
n
−
1
K_{1,n-1}
K
1
,
n
−
1
. f) Prove that in part e) there are at least two non-intersecting colorful subtrees.
6
1
Hide problems
Hales–Jewett theorem
Let
l
,
d
,
k
l,d,k
l
,
d
,
k
be natural numbers. We want to prove that for large numbers
n
n
n
, for each
k
k
k
-coloring of the
n
n
n
-dimensional cube with side length
l
l
l
, there is a
d
d
d
-dimensional subspace that all of its vertices have the same color. Let
H
(
l
,
d
,
k
)
H(l,d,k)
H
(
l
,
d
,
k
)
be the least number such that for
n
≥
H
(
l
,
d
,
k
)
n\geq H(l,d,k)
n
≥
H
(
l
,
d
,
k
)
the previus statement holds. a) Prove that: H(l,d \plus{} 1,k)\leq H(l,1,k) \plus{} H(l,d,k^l)^{H(l,1,k)} b) Prove that H(l \plus{} 1,1,k \plus{} 1)\leq H(l,1 \plus{} H(l \plus{} 1,1,k),k \plus{} 1) c) Prove the statement of problem. d) Prove Van der Waerden's Theorem.
5
1
Hide problems
Distinct subsets with at most n/2 elements
Let A\equal{}\{A_1,\dots,A_m\} be a family distinct subsets of
{
1
,
2
,
…
,
n
}
\{1,2,\dots,n\}
{
1
,
2
,
…
,
n
}
with at most
n
2
\frac n2
2
n
elements. Assume that
A
i
⊄
A
j
A_i\not\subset A_j
A
i
⊂
A
j
and
A
i
∩
A
j
≠
∅
A_i\cap A_j\neq\emptyset
A
i
∩
A
j
=
∅
for each
i
,
j
i,j
i
,
j
. Prove that: \sum_{i\equal{}1}^m\frac1{\binom{n\minus{}1}{|A_i|\minus{}1}}\leq1
4
1
Hide problems
Independent sets
Let
G
G
G
be a simple graph. Suppose that size of largest independent set in
G
G
G
is
α
\alpha
α
. Prove that: a) Vertices of
G
G
G
can be partitioned to at most
α
\alpha
α
paths. b) Suppose that a vertex and an edge are also cycles. Prove that vertices of
G
G
G
can be partitioned to at most
α
\alpha
α
cycles.
3
1
Hide problems
Graph and degrees
For a subset
S
S
S
of vertices of graph
G
G
G
, let
Λ
(
S
)
\Lambda(S)
Λ
(
S
)
be the subset of all edges of
G
G
G
such that at least one of their ends is in
S
S
S
. Suppose that
G
G
G
is a graph with
m
m
m
edges. Let
d
∗
:
V
(
G
)
⟶
N
∪
{
0
}
d^*: V(G)\longrightarrow\mathbb N\cup\{0\}
d
∗
:
V
(
G
)
⟶
N
∪
{
0
}
be a function such that a) \sum_{u}d^*(u)\equal{}m. b) For each subset
S
S
S
of
V
(
G
)
V(G)
V
(
G
)
:
∑
u
∈
S
d
∗
(
u
)
≤
∣
Λ
(
S
)
∣
\sum_{u\in S}d^*(u)\leq|\Lambda(S)|
u
∈
S
∑
d
∗
(
u
)
≤
∣Λ
(
S
)
∣
Prove that we can give directions to edges of
G
G
G
such that for each edge
e
e
e
, d^\plus{}(e)\equal{}d^*(e).
2
1
Hide problems
Hexagons
Let
H
(
n
)
H(n)
H
(
n
)
be the number of simply connected subsets with
n
n
n
hexagons in an infinite hexagonal network. Also let
P
(
n
)
P(n)
P
(
n
)
be the number of paths starting from a fixed vertex (that do not connect itself) with lentgh
n
n
n
in this hexagonal network. a) Prove that the limits \alpha: \equal{}\lim_{n\rightarrow\infty}H(n)^{\frac1n}, \beta: \equal{}\lim_{n\rightarrow\infty}P(n)^{\frac1n}exist. b) Prove the following inequalities:
2
≤
β
≤
2
\sqrt2\leq\beta\leq2
2
≤
β
≤
2
α
≤
12.5
\alpha\leq 12.5
α
≤
12.5
α
≥
3.5
\alpha\geq3.5
α
≥
3.5
α
≤
β
4
\alpha\leq\beta^4
α
≤
β
4
1
1
Hide problems
Circular Flow
A network is a simple directed graph such that each edge
e
e
e
has two intger lower and upper capacities
0
≤
c
l
(
e
)
≤
c
u
(
e
)
0\leq c_l(e)\leq c_u(e)
0
≤
c
l
(
e
)
≤
c
u
(
e
)
. A circular flow on this graph is a function such that: 1) For each edge
e
e
e
,
c
l
(
e
)
≤
f
(
e
)
≤
c
u
(
e
)
c_l(e)\leq f(e)\leq c_u(e)
c
l
(
e
)
≤
f
(
e
)
≤
c
u
(
e
)
. 2) For each vertex
v
v
v
: \sum_{e\in v^\plus{}}f(e)\equal{}\sum_{e\in v^\minus{}}f(e) a) Prove that this graph has a circular flow, if and only if for each partition
X
,
Y
X,Y
X
,
Y
of vertices of the network we have: \sum_{\begin{array}{c}{e\equal{}xy}\\{x\in X,y\in Y}\end{array}} c_l(e)\leq \sum_{\begin{array}{c}{e\equal{}yx}\\{y\in Y,x\in X}\end{array}} c_l(e) b) Suppose that
f
f
f
is a circular flow in this network. Prove that there exists a circular flow
g
g
g
in this network such that g(e)\equal{}\lfloor f(e)\rfloor or g(e)\equal{}\lceil f(e)\rceil for each edge
e
e
e
.