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

Home > Numbers
Minimal cardinality (Posted on 2016-03-16) Difficulty: 3 of 5
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 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
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information