Problem

Source: III International Festival of Young Mathematicians Sozopol 2012, Theme for 10-12 grade

Tags: combinatorics, set theory



Let $A_n$ be the set of all sequences with length $n$ and members of the set $\{1,2…q\}$. We denote with $B_n$ a subset of $A_n$ with a minimal number of elements with the following property: For each sequence $a_1,a_2,...,a_n$ from $A_n$ there exist a sequence $b_1,b_2,...,b_n$ from $B_n$ such that $a_i\neq b_i$ for each $i=1,2,....,n$. Prove that, if $q>n$, then $|B_n |=n+1$.