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
    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
    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