MathDB

13

Part of 1977 IMO Shortlist

Problems(1)

At most k^2/2^n sequences

Source:

9/20/2010
Let BB be a set of kk sequences each having nn terms equal to 11 or −1-1. The product of two such sequences (a1,a2,…,an)(a_1, a_2, \ldots , a_n) and (b1,b2,…,bn)(b_1, b_2, \ldots , b_n) is defined as (a1b1,a2b2,…,anbn)(a_1b_1, a_2b_2, \ldots , a_nb_n). Prove that there exists a sequence (c1,c2,…,cn)(c_1, c_2, \ldots , c_n) such that the intersection of BB and the set containing all sequences from BB multiplied by (c1,c2,…,cn)(c_1, c_2, \ldots , c_n) contains at most k22n\frac{k^2}{2^n} sequences.
abstract algebragroup theorycombinatoricsSequenceIMO Shortlist