MathDB
Problems
Contests
National and Regional Contests
Iran Contests
Iran MO (3rd Round)
2014 Iran MO (3rd Round)
2014 Iran MO (3rd Round)
Part of
Iran MO (3rd Round)
Subcontests
(8)
7
1
Hide problems
Repairing a Machine
We have a machine that has an input and an output. The input is a letter from the finite set
I
I
I
and the output is a lamp that at each moment has one of the colors of the set
C
=
{
c
1
,
…
,
c
p
}
C=\{c_1,\dots,c_p\}
C
=
{
c
1
,
…
,
c
p
}
. At each moment the machine has an inner state that is one of the
n
n
n
members of finite set
S
S
S
. The function
o
:
S
→
C
o: S \rightarrow C
o
:
S
→
C
is a surjective function defining that at each state, what color must the lamp be, and the function
t
:
S
×
I
→
S
t:S \times I \rightarrow S
t
:
S
×
I
→
S
is a function defining how does giving each input at each state changes the state. We only shall see the lamp and we have no direct information from the state of the car at current moment. In other words a machine is
M
=
(
S
,
I
,
C
,
o
,
t
)
M=(S,I,C,o,t)
M
=
(
S
,
I
,
C
,
o
,
t
)
such that
S
,
I
,
C
S,I,C
S
,
I
,
C
are finite,
t
:
S
×
I
→
S
t:S \times I \rightarrow S
t
:
S
×
I
→
S
, and
o
:
S
→
C
o:S \rightarrow C
o
:
S
→
C
is surjective. It is guaranteed that for each two different inner states, there's a sequence of inputs such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state. (a) The machine
M
M
M
has
n
n
n
different inner states. Prove that for each two different inner states, there's a sequence of inputs of length no more than
n
−
p
n-p
n
−
p
such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state. (b) Prove that for a machine
M
M
M
with
n
n
n
different inner states, there exists an algorithm with no more than
n
2
n^2
n
2
inputs that starting at any unknown inner state, at the end of the algorithm the state of the machine at that moment is known. Can you prove the above claim for
n
2
2
\frac{n^2}{2}
2
n
2
?
6
2
Hide problems
Prove that there are 100 natural number
Prove that there are 100 natural number
a
1
<
a
2
<
.
.
.
<
a
99
<
a
100
a_1 < a_2 < ... < a_{99} < a_{100}
a
1
<
a
2
<
...
<
a
99
<
a
100
(
a
i
<
1
0
6
a_i < 10^6
a
i
<
1
0
6
) such that A , A+A , 2A , A+2A , 2A + 2A are five sets apart ?
A
=
{
a
1
,
a
2
,
.
.
.
,
a
99
,
a
100
}
A = \{a_1 , a_2 ,... , a_{99} ,a_{100}\}
A
=
{
a
1
,
a
2
,
...
,
a
99
,
a
100
}
2
A
=
{
2
a
i
∣
1
≤
i
≤
100
}
2A = \{2a_i \vert 1\leq i\leq 100\}
2
A
=
{
2
a
i
∣1
≤
i
≤
100
}
A
+
A
=
{
a
i
+
a
j
∣
1
≤
i
<
j
≤
100
}
A+A = \{a_i + a_j \vert 1\leq i<j\leq 100\}
A
+
A
=
{
a
i
+
a
j
∣1
≤
i
<
j
≤
100
}
A
+
2
A
=
{
a
i
+
2
a
j
∣
1
≤
i
,
j
≤
100
}
A + 2A = \{a_i + 2a_j \vert 1\leq i,j\leq 100\}
A
+
2
A
=
{
a
i
+
2
a
j
∣1
≤
i
,
j
≤
100
}
2
A
+
2
A
=
{
2
a
i
+
2
a
j
∣
1
≤
i
<
j
≤
100
}
2A + 2A = \{2a_i + 2a_j \vert 1\leq i<j\leq 100\}
2
A
+
2
A
=
{
2
a
i
+
2
a
j
∣1
≤
i
<
j
≤
100
}
(20 ponits )
Polynomial of a Function
P
P
P
is a monic polynomial of odd degree greater than one such that there exists a function
f
:
R
→
N
f : \mathbb{R} \rightarrow \mathbb{N}
f
:
R
→
N
such that for each
x
∈
R
x \in \mathbb{R}
x
∈
R
,
f
(
P
(
x
)
)
=
P
(
f
(
x
)
)
f(P(x))=P(f(x))
f
(
P
(
x
))
=
P
(
f
(
x
))
(a) Prove that there are a finite number of natural numbers in range of
f
f
f
. (b) Prove that if
f
f
f
is not constant then the equation
P
(
x
)
−
x
=
0
P(x)-x=0
P
(
x
)
−
x
=
0
has at least two real solutions. (c) For each natural
n
>
1
n>1
n
>
1
prove that there exists a function
f
:
R
→
N
f : \mathbb{R} \rightarrow \mathbb{N}
f
:
R
→
N
and a monic polynomial of odd degree greater than one
P
P
P
such that for each
x
∈
R
x \in \mathbb{R}
x
∈
R
,
f
(
P
(
x
)
)
=
P
(
f
(
x
)
)
f(P(x))=P(f(x))
f
(
P
(
x
))
=
P
(
f
(
x
))
and range of
f
f
f
contains exactly
n
n
n
different numbers.Time allowed for this problem was 105 minutes.
1
5
Show problems
8
1
Hide problems
Recursive Polynomial
The polynomials
k
n
(
x
1
,
…
,
x
n
)
k_n(x_1, \ldots, x_n)
k
n
(
x
1
,
…
,
x
n
)
, where
n
n
n
is a non-negative integer, satisfy the following conditions
k
0
=
1
k_0=1
k
0
=
1
k
1
(
x
1
)
=
x
1
k_1(x_1)=x_1
k
1
(
x
1
)
=
x
1
k
n
(
x
1
,
…
,
x
n
)
=
x
n
k
n
−
1
(
x
1
,
…
,
x
n
−
1
)
+
(
x
n
2
+
x
n
−
1
2
)
k
n
−
2
(
x
1
,
…
,
x
n
−
2
)
k_n(x_1, \ldots, x_n) = x_nk_{n-1}(x_1, \ldots , x_{n-1}) + (x_n^2+x_{n-1}^2)k_{n-2}(x_1,\ldots,x_{n-2})
k
n
(
x
1
,
…
,
x
n
)
=
x
n
k
n
−
1
(
x
1
,
…
,
x
n
−
1
)
+
(
x
n
2
+
x
n
−
1
2
)
k
n
−
2
(
x
1
,
…
,
x
n
−
2
)
Prove that for each non-negative
n
n
n
we have
k
n
(
x
1
,
…
,
x
n
)
=
k
n
(
x
n
,
…
,
x
1
)
k_n(x_1,\ldots,x_n)=k_n(x_n,\ldots,x_1)
k
n
(
x
1
,
…
,
x
n
)
=
k
n
(
x
n
,
…
,
x
1
)
.
3
5
Show problems
5
5
Show problems
2
5
Show problems
4
5
Show problems