Chinese TST 2008 P4
Source:
April 3, 2008
inductioncombinatorics proposedcombinatorics
Problem Statement
Prove that for arbitary positive integer , there exists a permutation of the subsets that contain at least two elements of the set G_{n} \equal{} \{1,2,3,\cdots,n\}: P_{1},P_{2},\cdots,P_{2^n \minus{} n \minus{} 1} such that |P_{i}\cap P_{i \plus{} 1}| \equal{} 2,i \equal{} 1,2,\cdots,2^n \minus{} n \minus{} 2.