0
$\begingroup$

In order to solve one of my probability HW questions I got that I need to find

$$\max_{\Large{B=A\uplus\{1\}\atop A\subseteq\{2,\dots,6\}}}\sum_{i\in B}\frac{i}{|B|}$$

Where the union is disjoint union.

I have made the observation that for some choise of $j\geq 1$ elements from $2,...6$ for $A$ the maximum will occur when choosing the elements $6,...6-j+1$.

So I can go over each $1\leq j \leq 5$ and take $j=0$ and set $A=B={1}$ and check those $6$ cases and see where I get the maximum.

Is there a way to calculate the maximum without brute-force of trying all $j=0,...,5$ ?

  • 0
    The expression $$\max_{\Large{B=A\uplus\{1\}\atop A\subseteq\{2,\dots,6\}}}\sum_{i\in B}\frac{i}{|B|}$$ can be written more simply as $$\max_{1\in B\subseteq\{1,\dots,6\}}\sum_{i\in B}\frac1{|B|}\;.$$2012-12-02
  • 0
    @BrianM.Scott - can you please explain ? it seems that the expressions are not the same since they sum different things on the same set of indexes2012-12-02
  • 0
    If $1\in B\subseteq\{1,\dots,6\}$, then $B=(B\setminus\{1\})\uplus\{1\}$, where $B\setminus\{1\}\subseteq\{2,\dots,6\}$. Conversely, if $B=A\uplus\{1\}$, where $A\subseteq\{2,\dots,6\}$, then $1\in B\subseteq\{1,\dots,6\}$.2012-12-02
  • 0
    @BrianM.Scott - I agree, but in both expressions it seems that $B$ is any set contained in $1,...6$ with the condition that $1\in B$ but we sum different elements on the same elements of $B$ as the index set...maybe it should be $i$ and not $1$ in the second expression or did you meant is to be $1$ ?)2012-12-02
  • 0
    I don’t understand: the two expressions take the maximum over exactly the same set of sums.2012-12-02
  • 0
    @BrianM.Scott - the first expression looks like $6/3 + 5/3 + 4/3$ where the second expression looks like $1/3 + 1/3 + 1/3$.2012-12-02
  • 0
    Oh! Yes, that was a typo: the numerator should be $i$. Sorry: I knew so clearly what it was supposed to be that I didn’t see what I’d actually typed.2012-12-02
  • 0
    @BrianM.Scott - its ok :) but how does this help finding the maximum ? there is the conflict that when you sum more elements each element in the sum is smaller, so its not clear when to stop taking elements for $A$ and so I don't see any other way then brute-force of going over all choises for $|B|$2012-12-02
  • 0
    I don't like my way since if you change $6$ to, say, $100$ it would take me hours to do homework. oh wait, it takes hours anyways :P2012-12-02

1 Answers 1

2

More generally, consider $$\max_{1\in B\subseteq[n]}\frac1{|B|}\sum B\;,$$ where $[n]=\{1,\dots,n\}$. Fix $k\in[n]$ and let $\mathscr{B}_k=\{B\subseteq[n]:1\in B\text{ and }|B|=k\}$. Then clearly

$$\begin{align*} \max_{B\in\mathscr{B}_k}\frac1k\sum B&=\frac1k\left(1+\sum_{i=n-k+2}^ni\right)\\ &=\frac1k\left(1+\frac12\Big((n-k+2)+n\Big)(k-1)\right)\\ &=\frac1k\left(1+\frac{(2n-k+2)(k-1)}2\right)\\ &=\frac{2nk-2n-k^2+3k}{2k}\\ &=n+\frac32-\left(\frac{n}k+\frac{k}2\right) \end{align*}$$

so your problem reduces to finding

$$\max_{k\in[n]}\left(n+\frac32-\left(\frac{n}k+\frac{k}2\right)\right)$$

or, equivalently,

$$\min_{k\in[n]}\left(\frac{n}k+\frac{k}2\right)\;.$$

By elementary calculus the function $f(x)=\dfrac{n}x+\dfrac{x}2$ assumes its minimum at $x=\sqrt{2n}$, so the desired value of $k$ must be either $\left\lfloor\sqrt{2n}\right\rfloor$ or $\left\lceil\sqrt{2n}\right\rceil$. In the case $n=6$ these are $k=3$ and $k=4$, both of which work.

In general these two values will be the same if $2n$ is a square. Otherwise,

$$\begin{align*} &\left(\frac{n}{\left\lfloor\sqrt{2n}\right\rfloor}+\frac{\left\lfloor\sqrt{2n}\right\rfloor}2\right)-\left(\frac{n}{\left\lceil\sqrt{2n}\right\rceil}+\frac{\left\lceil\sqrt{2n}\right\rceil}2\right)\\ &\qquad=n\left(\frac1{\left\lfloor\sqrt{2n}\right\rfloor}-\frac1{\left\lceil\sqrt{2n}\right\rceil}\right)+\frac12\left(\left\lfloor\sqrt{2n}\right\rfloor-\left\lceil\sqrt{2n}\right\rceil\right)\\ &\qquad=\frac{n}{\left\lfloor\sqrt{2n}\right\rfloor\cdot\left\lceil\sqrt{2n}\right\rceil}-\frac12\\\\ &\qquad\begin{cases} <0,&\text{if }\left\lfloor\sqrt{2n}\right\rfloor\cdot\left\lceil\sqrt{2n}\right\rceil>2n\\ =0,&\text{if }\left\lfloor\sqrt{2n}\right\rfloor\cdot\left\lceil\sqrt{2n}\right\rceil=2n\\ >0,&\text{if }\left\lfloor\sqrt{2n}\right\rfloor\cdot\left\lceil\sqrt{2n}\right\rceil<2n\;. \end{cases} \end{align*}$$

The desired value of $k$ is therefore

$$\begin{cases} \left\lfloor\sqrt{2n}\right\rfloor,&\text{if }\left\lfloor\sqrt{2n}\right\rfloor\cdot\left\lceil\sqrt{2n}\right\rceil>2n\\\\ \left\lfloor\sqrt{2n}\right\rfloor=\left\lceil\sqrt{2n}\right\rceil,&\text{if }\left\lfloor\sqrt{2n}\right\rfloor\cdot\left\lceil\sqrt{2n}\right\rceil=2n\\\\ \left\lceil\sqrt{2n}\right\rceil,&\text{if }\left\lfloor\sqrt{2n}\right\rfloor\cdot\left\lceil\sqrt{2n}\right\rceil<2n\;. \end{cases}$$

  • 0
    In our setteing $n=6$ ? because then you have it that we should take an emptyset for $A$ and then the result is $1\neq n=6$2012-12-02
  • 0
    Direct calculation gave me $A={6,5}$ and $A={6,5,4}$ gave the max ($=4$), if I understand correctly you have a different answer ?2012-12-02
  • 0
    @Belgi: You’re right: when I added that last bit, I somehow managed to forget that $1$ had to be in $B$. I’ll have to go back and reconsider it.2012-12-02
  • 0
    Thanks, the approach is clear though :)2012-12-02
  • 0
    @Belgi: Thanks. I figured that the idea would probably be enough for you, but I still intend to clean it up $-$ partly because now **I’m** curious!2012-12-02
  • 0
    I'm curious too! My intuition is that the general answer will be to take $n,n-1,...n/2$ (and $1$)2012-12-02