MathDB
ASU 231 All Soviet Union MO 1976 sequence of universal numbers

Source:

July 6, 2019
combinatoricsSequence

Problem Statement

Given natural nn. We shall call "universal" such a sequence of natural number a1,a2,...,ak,k≥na_1, a_2, ... , a_k, k\ge n, if we can obtain every transposition of the first nn natural numbers (i.e such a sequence of nn numbers, that every one is encountered only once) by deleting some its members. (Examples: (1,2,3,1,2,1,31,2,3,1,2,1,3) is universal for n=3n=3, and (1,2,3,2,1,3,11,2,3,2,1,3,1) -- not, because you can't obtain (3,1,23,1,2) from it.) The goal is to estimate the length of the shortest universal sequence for given nn.
a) Give an example of the universal sequence of n2n2 members. b) Give an example of the universal sequence of (n2−n+1)(n^2 - n + 1) members.
c) Prove that every universal sequence contains not less than n(n+1)/2n(n + 1)/2 members
d) Prove that the shortest universal sequence for n=4n=4 contains 12 members
e) Find as short universal sequence, as you can. The Organising Committee knows the method for (n2−2n+4)(n^2 - 2n +4) members.
Back to ProblemsView on AoPS