All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Minimal cardinality (Posted on 2016-03-16)
Let S be a set of n distinct real numbers.
Let AS be the set of numbers that occur as averages
of two distinct elements of S.

For a given n >= 2, what is the smallest possible number
of distinct elements in As?

 See The Solution Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution | Comment 2 of 3 |
S consists of real numbers, so its members can be ordered.  Let k_1, k_2, k_3, ... k_n be the members of S sorted in ascending order.  k_1 is the smallest member and k_n is the largest member.

Let A_k1 be the subset of A_s consisting of all n-1 averages using k_1.  Similarly let A_kn be the subset of A_s consisting of all n-1 averages using k_n.  These two subsets have one member in common: (k_1+k_n)/2.  All the other members of A_k1 are smaller than this value and all the other members of A_kn are larger than this value.

The union of A_k1 and A_kn has (n-1)+(n-1)-1 = 2n-3 members.  The union also must be a subset of A_s.  Therefore A_s must have at least 2n-3 members.

As Charlie noted in his solution, if S is an arithmetic sequence of n terms then A_s has 2n-3 members.  This shows the theoretical minimum size of A_s, as determined above, can be achieved for some set S.  The smallest possible number of distinct members if A_s is 2n-3.

 Posted by Brian Smith on 2016-03-16 10:34:44

 Search: Search body:
Forums (0)