Conference rusure::math

>      n
>    Sigma x  = 3						(I)
>    i=1    i
>
>      n    2
>    Sigma x  = n-4						(III)
>    i=1    i
>
>    Since the Right-Hand Side (RHS) of (I) is non-zero, then the LHS of
>    (III) must be positive, therefore n must be more than 4.
>
>    Do you see any errors? Any suggestions on how to proceed?

Set three of the x  to 1, and four more to 0?
		  i

It's probably not the smallest solution, though it may be the shortest. :-)

Dan

    Given that sum x[i] is three, what is the smallest that sum x[i]^2
    could be?  I suspect the minimum is obtained when each x[i] equals 3/n,
    producing a sum of squares of n*(3/n)^2 = 9/n.  I won't prove that but
    expect it could be done by showing any set of n numbers summing to
    three could be improved by moving two of the numbers closer to 3/n.
    
    Next, we need the minimum value of sum x[i]^2 to equal or exceed n-4. 
    9/n is less than n-4 for n = 1, 2, 3, 4, and 5, so 6 is the best
    potential case.  We know there is a solution of 7 numbers from note .1,
    so now we have to determine whether there is a solution of 6.
    
    Let's suppose there's solution [ 3/6, 3/6, 3/6, 3/6, a, 1-a ].  The
    total is 3.  The sum of the squares is 4*(.25)+a^2+(1-a)^2, and we know
    this must equal n-4, which is 2.  This reduces to a^2-a = 0, or a = 0
    or 1.  Either choice makes the result [ 1/2, 1/2, 1/2, 1/2, 0, 1 ],
    which, when joined with -2 and -1, has mean 0 and (sample) variance 1.
    
    
    				-- edp

The only other solution I can find in integers is 
	[-2,-1, 1,2,0,0,0,0,0,0,0], 
which is longer. However,
	[-2,-1, x,x,x,x,x, 3-5*x] 
has mean 0 and variance 1 for x ~= .3709005551, and is of length 8.

    For n=5, we have:
    
    	x[5] = 3 - x[1] - x[2] - x[3] - x[4]
    
    	x[1]� + x[2]� + x[3]� + x[4]� + (3 - x[1] - x[2] - x[3] - x[4])� = 1
    
    In this second equation, we have a problem minimizing the sum of those
    squares.  Assuming x = x[1] = x[2] = ... = x[4] is necessary to minimize
    the sum of the squares, we get 20�x� - 24�x + 8, which is minimized
    when x = 3/5, but the sum is still 9/5; alas, this is still greater than 1.
    
    For n=6, we have:
    
    	x[6] = 3 - x[1] - x[2] - x[3] - x[4] - x[5]
    
    	x[1]� + x[2]� + x[3]� + x[4]� + x[5]�
    			+ (3 - x[1] - x[2] - x[3] - x[4] - x[5])� = 2
    
    Similarly, we have 5�x� + (3-5�x)� - 2 = 0 whence x = (15�sqrt(15))/30,
    x[1] = x[2] = x[3] = x[4] = x[5] = x, and x[6] = 3 - 5�x.
    
    Alternatively, for n = 6, we could simply assume there are two kinds
    of values, x = x[1] = x[2] = x[3], and y = y[1] = y[2] = y[3], and solve:
    
    	3�x + 3�y = 3,  and  3�x� + 3�y� = 2.
    
    Solving, we get {x,y} = { � + sqrt(3)/6, � - sqrt(3)/6 }.

    Great stuff. Only one nit: in .2, I'm sure EDP meant "greater" instead
    of "less" in "9/n is less than n-4 for n = 1, 2, 3, 4, and 5, so ..."
    
    I enjoyed reading your solutions. Thanks.
    
    Dwayne
    

.2> Given that sum x[i] is three, what is the smallest that sum x[i]^2
.2> could be?  I suspect the minimum is obtained when each x[i] equals 3/n,

		    n		     n
Problem:  Minimize sum x[i]�, given sum x[i] = M.
		   i=1		    i=1

Solution: x[i] = M/n for i=1..n.

Proof (by contradiction):  Assume a set z[i] minimizes sum z[i]�, but
	not all z[i] = M/n.  Then some z[j] is < M/n (otherwise, all are
	>= M/n, and necessarily = M/n).  Similarly, some z[k] is > M/n.
	Let y[j] = z[j] + d, y[k] = z[k] - d, and for other i, y[i] = z[i].
	For certain (positive) d, we assert that sum y[i]� < sum z[i]�.

	Choose 0 < d < z[k]-z[j].  Then

	sum z[i]� - sum y[i]�
		= z[j]� - (z[j]+d)� + z[k]� - (z[k]-d)�
		= -2�d�z[j] - d� + 2�d�z[k] - d�
		= 2�d�( z[k] - z[j] - d )
		> 0	(since d > 0 and z[k] - z[j] - d > 0)

	Thus, the z[i] do not minimize sum z[i]�, since sum y[i]� is smaller.
	So the premise is false, and so x[i] = M/n minimizes sum x[i]�.

Alternate solution:

	Solve the sum for x[n], and substitute this into the sum of squares:

		   n-1
	x[n] = M - sum x[i]
		   i=1

	     n		n-1		 n-1
	f = sum x[i]� = sum x[i]� + (M - sum x[i])�
	    i=1		i=1		 i=1

	We want to choose x[1]..x[n-1] to minimize f.  So we take a
	partial derivative with respect to x[j] (where 1 <= j < n), set
	this to zero, and solve for x[j].

	 df			n-1
	----- = 2�x[j] + 2�(M - sum x[i])�(-1) = 0, so that
	dx[j]			i=1
		    n-1
	x[j] = (M - sum x[i])		(yes, x[j] appears on both sides)
		    i=1

	This holds for any/all j < n, and also for x[n]!  Thus, the x[i] are
	all equal; and so all x[i] = M/n.

.3> The only other solution I can find in integers is 
.3>	[-2,-1, 1,2,0,0,0,0,0,0,0], 

Ignoring the -2 and -1, which are given, suppose the solution has a[0] zeroes,
1 occurs a[1] times, ..., i occurs a[i] times.  We have:

	sum a[i] = n

	sum a[i]�i = 3

	sum a[i]�i� = (n-4)

Assuming we aren't interested in solutions containing numbers with absolute
value >= 4 (since this would make n at least 12 -- twelve numbers in the
solution), we can solve the above:

	n    =  6�a[3] + 2�a[2] + 2�a[-1] + 6�a[-2] + 12�a[-3] + 7

	a[0] =  8�a[3] + 3�a[2] +           3�a[-2] +  8�a[-3] + 4

	a[1] = -3�a[3] - 2�a[2] +   a[-1] + 2�a[-2] +  3�a[-3] + 3

Here, a[3], a[2], a[-1], a[-2], and a[-3] are free variables which we want
to be integers >= 0.

From the first of these three equations, we see that to minimize n (to 7),
all the free variables must be zero.  And so we get a[0] = 4 and a[1] = 3.

So the shortest integral solution is:

	[-2,-1, 0,0,0,0,1,1,1]

    The formula for the variance of a set of n numbers with known mean, �
    is:

		     n		 2
		   Sigma (x  - �) 
		    i=1    i
	    VAR = -----------------		(I)
			 n

    rather than the formula used which is appropriate when the mean, M is
    estimated from the sample:

		     n		 2
		   Sigma (x  - M) 
		    i=1    i
	    VAR = -----------------		(II)
			n-1

    What does using I instead of II do to the solution?

				    Topher

    Right, Topher. The puzzle was meant to use �, not M.
    
    Applying the techniques in the previous replies, I find the minimum
    size to be five elements. Two solutions I find are:
    
    { 1/2, 1/2, 1/2, 1/2, 1 }
    
    and
    
    { 1/5, 7/10, 7/10, 7/10, 7/10 }
    
    Dwayne
    

And in integers:

	sum a[i] = n
	sum a[i]�i = 3
	sum a[i]�i� = n-3	(previously this was n-4)

	n    =  6�a[3] + 2�a[2] + 2�a[-1] + 6�a[-2] + 12�a[-3] + 6
	a[0] =  8�a[3] + 3�a[2] +           3�a[-2] +  8�a[-3] + 3
	a[1] = -3�a[3] - 2�a[2] +   a[-1] + 2�a[-2] +  3�a[-3] + 3

Setting the free variables a[3], a[2], a[-1], a[-2], and a[-3] to zero
minimizes n, and gives a[0] = a[1] = 3.  So the shortest integral solution is:

	[-2,-1, 0,0,0,1,1,1]

(Way to go, Topher!
	When you aren't satisfied with the answer, rewrite the problem!)