MathDB
Problems
Contests
National and Regional Contests
Russia Contests
All-Russian Olympiad
1976 All Soviet Union Mathematical Olympiad
231
231
Part of
1976 All Soviet Union Mathematical Olympiad
Problems
(1)
ASU 231 All Soviet Union MO 1976 sequence of universal numbers
Source:
7/6/2019
Given natural
n
n
n
. We shall call "universal" such a sequence of natural number
a
1
,
a
2
,
.
.
.
,
a
k
,
k
≥
n
a_1, a_2, ... , a_k, k\ge n
a
1
,
a
2
,
...
,
a
k
,
k
≥
n
, if we can obtain every transposition of the first
n
n
n
natural numbers (i.e such a sequence of
n
n
n
numbers, that every one is encountered only once) by deleting some its members. (Examples: (
1
,
2
,
3
,
1
,
2
,
1
,
3
1,2,3,1,2,1,3
1
,
2
,
3
,
1
,
2
,
1
,
3
) is universal for
n
=
3
n=3
n
=
3
, and (
1
,
2
,
3
,
2
,
1
,
3
,
1
1,2,3,2,1,3,1
1
,
2
,
3
,
2
,
1
,
3
,
1
) -- not, because you can't obtain (
3
,
1
,
2
3,1,2
3
,
1
,
2
) from it.) The goal is to estimate the length of the shortest universal sequence for given
n
n
n
. a) Give an example of the universal sequence of
n
2
n2
n
2
members. b) Give an example of the universal sequence of
(
n
2
−
n
+
1
)
(n^2 - n + 1)
(
n
2
−
n
+
1
)
members. c) Prove that every universal sequence contains not less than
n
(
n
+
1
)
/
2
n(n + 1)/2
n
(
n
+
1
)
/2
members d) Prove that the shortest universal sequence for
n
=
4
n=4
n
=
4
contains 12 members e) Find as short universal sequence, as you can. The Organising Committee knows the method for
(
n
2
−
2
n
+
4
)
(n^2 - 2n +4)
(
n
2
−
2
n
+
4
)
members.
combinatorics
Sequence