MathDB
Problems
Contests
National and Regional Contests
Iran Contests
Pre-Preparation Course Examination
2008 Pre-Preparation Course Examination
2008 Pre-Preparation Course Examination
Part of
Pre-Preparation Course Examination
Subcontests
(5)
5
1
Hide problems
Cycles and Permutations
A permutation
π
\pi
π
is selected randomly through all
n
n
n
-permutations. a) if C_a(\pi)\equal{}\mbox{the number of cycles of length }a\mbox{ in }\pi then prove that E(C_a(\pi))\equal{}\frac1a b) Prove that if
{
a
1
,
a
2
,
…
,
a
k
}
⊂
{
1
,
2
,
…
,
n
}
\{a_1,a_2,\dots,a_k\}\subset\{1,2,\dots,n\}
{
a
1
,
a
2
,
…
,
a
k
}
⊂
{
1
,
2
,
…
,
n
}
the probability that
π
\pi
π
does not have any cycle with lengths
a
1
,
…
,
a
k
a_1,\dots,a_k
a
1
,
…
,
a
k
is at most \frac1{\sum_{i\equal{}1}^ka_i}
4
1
Hide problems
Sarah and Darah play a game
Sarah and Darah play the following game. Sarah puts
n
n
n
coins numbered with
1
,
…
,
n
1,\dots,n
1
,
…
,
n
on a table (Each coin is in HEAD or TAIL position.) At each step Darah gives a coin to Sarah and she (Sarah) let him (Dara) to change the position of all coins with number multiple of a desired number
k
k
k
. At the end, all of the coins that are in TAIL position will be given to Sarah and all of the coins with HEAD position will be given to Darah. Prove that Sarah can put the coins in a position at the beginning of the game such that she gains at least
Ω
(
n
)
\Omega(n)
Ω
(
n
)
coins. [hide="Hint:"]Chernov inequality!
3
1
Hide problems
Pointed distributed over a sphere
Prove that we can put
Ω
(
1
ϵ
)
\Omega(\frac1{\epsilon})
Ω
(
ϵ
1
)
points on surface of a sphere with radius 1 such that distance of each of these points and the plane passing through center and two of other points is at least
ϵ
\epsilon
ϵ
.
2
1
Hide problems
Random points on a circle
Seven points are selected randomly from
S
1
⊂
C
S^1\subset\mathbb C
S
1
⊂
C
. What is the probability that origin is not contained in convex hull of these points?
1
1
Hide problems
Ramsey numbers
R
k
(
m
,
n
)
R_k(m,n)
R
k
(
m
,
n
)
is the least number such that for each coloring of
k
k
k
-subsets of
{
1
,
2
,
…
,
R
k
(
m
,
n
)
}
\{1,2,\dots,R_k(m,n)\}
{
1
,
2
,
…
,
R
k
(
m
,
n
)}
with blue and red colors, there is a subset with
m
m
m
elements such that all of its k-subsets are red or there is a subset with
n
n
n
elements such that all of its
k
k
k
-subsets are blue. a) If we give a direction randomly to all edges of a graph
K
n
K_n
K
n
then what is the probability that the resultant graph does not have directed triangles? b) Prove that there exists a
c
c
c
such that
R
3
(
4
,
n
)
≥
2
c
n
R_3(4,n)\geq2^{cn}
R
3
(
4
,
n
)
≥
2
c
n
.