MathDB

7 (C1)

Part of 2005 QEDMO 1st

Problems(1)

Differences in a subset give all possible differences

Source: QEDMO 2005

11/8/2005
Prove: From the set {1,2,...,n}\{1,2,...,n\}, one can choose a subset with at most 2⌊n⌋+12 \left\lfloor \sqrt n \right\rfloor +1 elements such that the set of the pairwise differences from this subset is {1,2,...,n−1}\{1,2,...,n-1\}. (⌊x⌋\left\lfloor x \right\rfloor means the greatest integer ≤x\leq x)
floor function