Suppose I have n integers μ i , i = { 1 , 2 , . . . , n }. Define μ ¯ = 1 n ∑ i = 1 n μ i . It is given that all the μ i 's are either +1 or −1. How can I show that ∑ i = 1 n ( μ i − μ ¯ ) 2 is maximized only when ⌊ n ⌋ 2 or ⌈ n ⌉ 2 are +1 and rest are −1's.I was thinking about proving this inductively, but I am not sure how.

Question

Suppose I have   n integers       μ    i  ,   i  =  {  1  ,  2  ,  .  .  .  ,  n  }. Define             μ      ¯        =      1    n        ∑          i      =      1              n            μ    i  . It is given that all the       μ    i  &#039;s are either +1 or −1. How can I show that       ∑          i      =      1              n        (      μ    i    −            μ      ¯            )    2   is maximized only when             ⌊      n      ⌋        2   or             ⌈      n      ⌉        2   are +1 and rest are −1&#039;s.I was thinking about proving this inductively, but I am not sure how.

Penelope Carson · Accepted Answer

Let   ϕ  (  μ  )  =      ∑    k    (      μ    k    −            μ      ¯            )    2    =      ∑    k        μ    k    2    −  (      ∑    k        μ    k        )    2  .Since       |        μ    k        |    =  1, we see that   ϕ  (  μ  )  =  n  −  (      ∑    k        μ    k        )    2  .Hence   ϕ will be maximised when   μ  ↦  (      ∑    k        μ    k        )    2   is minimised.As an aside, note that this is also the solution to the relaxation   max  {  ϕ  (  μ  )  ∣      μ    k    ∈  [  −  1  ,  1  ]  }, which is convex. It is straightforward to see that                     ∂        ϕ        (        μ        )                    ∂                  μ          k                      =  2  (      μ    k    −            μ      ¯        ) and                               ∂          2                ϕ        (        μ        )                    ∂                  μ          k          2                      =  2  (  1  −            1      n        ). In particular, we see that if       μ    k    ∈  (  −  1  ,  1  ) then there is some   t such that   μ  +  t      e    k   is feasible and   ϕ  (  μ  +  t      e    k    )  &amp;gt;  ϕ  (  μ  ). Hence at a maximum, we must have       |        μ    k        |    =  1.

Suppose I have n integers <msub> μ i </msub> , i =

Answered question

Answer & Explanation

New Questions in High school geometry