MathDB
Problems
Contests
National and Regional Contests
Iran Contests
Pre-Preparation Course Examination
2011 Pre-Preparation Course Examination
2011 Pre-Preparation Course Examination
Part of
Pre-Preparation Course Examination
Subcontests
(7)
6
1
Hide problems
2-dominating sets
We call a subset
S
S
S
of vertices of graph
G
G
G
,
2
2
2
-dominating, if and only if for every vertex
v
∉
S
,
v
∈
G
v\notin S,v\in G
v
∈
/
S
,
v
∈
G
,
v
v
v
has at least two neighbors in
S
S
S
. prove that every
r
r
r
-regular
(
r
≥
3
)
(r\ge3)
(
r
≥
3
)
graph has a
2
2
2
-dominating set with size at most
n
(
1
+
ln
(
r
)
)
r
\frac{n(1+\ln(r))}{r}
r
n
(
1
+
l
n
(
r
))
.(15 points) time of this exam was 3 hours
5
2
Hide problems
Cycles in graphs
a) Prove that if
G
G
G
is
2
2
2
-connected, then it has a cycle with the length at least
min
{
n
(
G
)
,
2
δ
(
G
)
}
\min\{n(G),2\delta(G)\}
min
{
n
(
G
)
,
2
δ
(
G
)}
. (10 points)b) Prove that every
2
k
2k
2
k
-regular graph with
4
k
+
1
4k+1
4
k
+
1
vertices has a hamiltonian cycle. (10 points)
two equivalent statements about prime numbers
suppose that
v
(
x
)
=
∑
p
≤
x
,
p
∈
P
l
o
g
(
p
)
v(x)=\sum_{p\le x,p\in \mathbb P}log(p)
v
(
x
)
=
∑
p
≤
x
,
p
∈
P
l
o
g
(
p
)
(here
P
\mathbb P
P
denotes the set of all positive prime numbers). prove that the two statements below are equivalent:a)
v
(
x
)
∼
x
v(x) \sim x
v
(
x
)
∼
x
when
x
⟶
∞
x \longrightarrow \infty
x
⟶
∞
b)
π
(
x
)
∼
x
l
n
(
x
)
\pi (x) \sim \frac{x}{ln(x)}
π
(
x
)
∼
l
n
(
x
)
x
when
x
⟶
∞
x \longrightarrow \infty
x
⟶
∞
. (here
π
(
x
)
\pi (x)
π
(
x
)
is number of the prime numbers less than or equal to
x
x
x
).
4
3
Hide problems
Without induced paw
A star
K
1
,
3
K_{1,3}
K
1
,
3
is called a paw. suppose that
G
G
G
is a graph without any induced paws. prove that
χ
(
G
)
≤
(
ω
(
G
)
)
2
\chi(G)\le(\omega(G))^2
χ
(
G
)
≤
(
ω
(
G
)
)
2
. (15 points)
calculating the sum
represent a way to calculate
∑
k
=
0
∞
(
−
1
)
k
(
2
k
+
1
)
3
=
1
−
1
3
3
+
1
5
3
−
1
7
3
+
.
.
.
\sum_{k=0}^{\infty}\frac{(-1)^k}{(2k+1)^3}=1-\frac{1}{3^3}+\frac{1}{5^3}-\frac{1}{7^3}+...
∑
k
=
0
∞
(
2
k
+
1
)
3
(
−
1
)
k
=
1
−
3
3
1
+
5
3
1
−
7
3
1
+
...
.
percolation
suppose that
0
≤
p
≤
1
0\le p \le 1
0
≤
p
≤
1
and we have a wooden square with side length
1
1
1
. in the first step we cut this square into
4
4
4
smaller squares with side length
1
2
\frac{1}{2}
2
1
and leave each square with probability
p
p
p
or take it with probability
1
−
p
1-p
1
−
p
. in the next step we cut every remaining square from the previous step to
4
4
4
smaller squares (as above) and take them with probability
1
−
p
1-p
1
−
p
. it's obvios that at the end what remains is a subset of the first square. a) show that there exists a number
0
<
p
0
<
1
0<p_0<1
0
<
p
0
<
1
such that for
p
>
p
0
p>p_0
p
>
p
0
the probability that the remainig set is not empty is positive and for
p
<
p
0
p<p_0
p
<
p
0
this probability is zero. b) show that for every
p
≠
1
p\neq 1
p
=
1
with probability
1
1
1
, the remainig set has size zero. c) for this statement that the right side of the square is connected to the left side of the square with a path, write anything that you can.
3
4
Show problems
2
4
Show problems
1
4
Show problems
7
1
Hide problems
every three longest paths have a common vertex
prove or disprove: in a connected graph
G
G
G
, every three longest paths have a vertex in common.