12
$\begingroup$

A bin is called full if it contains at least $k$ balls. Our goal is to make as many bins as possible full.

In the simplest scenario, we are given $n$ balls and may arrange them arbitrarily. In that case, obviously the best we can do is pick $\lfloor n/k \rfloor$ bins arbitrarily and put $k$ balls in each one of them.

I am interested in the following scenario: we are given $n$ pairs of balls. We have to put the two balls of each pair in two different bins. Then, an adversary comes and removes one ball from each pair. What can we do to have the maximum possible number of full bins after the removal?

A simple strategy is: pick $\lfloor n/(2k-1) \rfloor$ pairs of bins. Fill each bin-pair with $2k-1$ ball-pairs (each bin contains $2k-1$ balls, one ball from each pair). Then, regardless of what our adversary removes, we have in each bin-pair at least one full bin.

Do we have a strategy that achieves a larger number of full bins (more than $\lfloor n/(2k-1) \rfloor$)?

$\endgroup$
  • 1
    $\begingroup$ I don't believe so $\endgroup$ – Zach Saucier Apr 5 '16 at 17:39
  • $\begingroup$ $n$ is given and $k$ is given? $k$ depends on $n$? $\endgroup$ – Evil Apr 5 '16 at 23:13
  • $\begingroup$ @EvilJS $n$ and $k$ are given, and are independent. $\endgroup$ – Erel Segal-Halevi Apr 7 '16 at 9:00
  • $\begingroup$ Does the player place all of his $n$ pairs of balls and then the adversary picks $n$ balls?, or does the player place a pair of balls and then the adversary chooses one from that pair and then the player puts the next pair and the adversary picks one and so on until there are no more pairs of balls to place? $\endgroup$ – rotia Apr 10 '16 at 22:20
  • $\begingroup$ @rotia The player places all of his n pairs of balls, and then the adversary picks n balls. $\endgroup$ – Erel Segal-Halevi Apr 11 '16 at 10:36
2
$\begingroup$

TL;DR -- No, there is no better strategy than the simple strategy. Here is the main idea of the proof. When there are not enough balls, there will be a "ball path" from a $k$-full bin to a bin with at most $k-2$ balls. The adversary can pass a ball from that full bin to that less full bin along that path, which can be done repeatedly until the number of $k$-full bins is reduced.


Reformulation in Graph theory

Suppose we are given a simple finite graph $G(V,E)$ with a function $w: E\to\Bbb Z_{\ge 0}$. We say there are $w(e)$ balls in edge $e$. Let $E_2$ be the (end-marked edge) set $\{(e,v)| e\in E, v\in e\}$. If $d:E_2\to\Bbb Z_{\ge 0}$ satisfies $w(e)=d(e,v_1) + d(e,v_2)$ for every edge $e=\{v_1,v_2\}$, we say that $d$ is $w$-distributing. Any $w$-distributing function $d$ induces a function, which we use the same symbol, $d:V\to\Bbb Z_{\ge 0}$, $d(v) =\sum_{v\in e}d(e,v)$. We say that $d(v)$ balls are in $v$. Given $k\in\Bbb Z_{\gt0}$, let $F_k(d)=\#\{v\in V|d(v)\ge k\}$, the number of $k$-full vertices by $d$.

(Erel-Apass Theorem) For any simple finite graph $G(V,E)$ and $w:E\to\Bbb Z_{\ge0}$, we have $\sum_{e\in E}w(e)\geq (2k-1) \min_{w\text{-distributing }d}F_k(d)$

Imagine each vertex is a bin. For each edge $e=\{v_1,v_2\}$, $w(e)$ ball-pairs are put into $v_1$ and $v_2$, each of which getting $w(e)$ balls. Among these $w(e)$ ball-pairs, the adversary may take away $d(e,v_2)$ balls from $v_1$ and $d(e,v_1)$ balls from $v_2$. The end result is the same as if, given all empty bins initially, for each edge $e=\{v_1, v_2\}$, $w(e)$ balls are put into it and, then, $d(e,v_1)$ and $d(e,v_2)$ balls are distributed to $v_1$ and $v_2$ respectively by the adversary. Hence, Erel-Apass theorem says that in order to ensure $t$ k-full bins after a smart adversary's removal, at least $(2k-1)t$ pairs of balls are needed. In another word, an optimal strategy to have the maximum possible number of full bins left is indeed the "simple strategy", which repeatedly fills a different pair of bins with $2k-1$ ball-pairs until we do not have enough balls to repeat.


Proof of the theorem

For the sake of contradiction, let $G(V,E)$ and $w$ be a counterexample whose number of vertices is the smallest among all counterexamples. That is, there is $w$-distributing $m$ such that $F_k(m)$ is minimal among all $F_k(d)$ of $w$-distributing function $d$. Furthermore, $$\sum_{e\in E}w(e)\lt (2k-1)F_k(m)$$

Let $V_s=\{v\in V | m(v)\le k-2\}$. Let $V_\ell=\{v\in V|m(v)\geq k\}$. So $F_k(m)=\#V_\ell$.

Claim one: $V_s\neq\emptyset$.
Proof of claim one. Suppose otherwise that $V_s$ is empty. $$ \sum_{v\in V}m(v)= (k-1)\#V +\sum_{v\in V}(m(v)-(k-1)) \ge (k-1)\#V + \#V_\ell \gt (k-1)\#V$$ Let us also reuse $w$ as a function from $V$ to $\Bbb Z_{\ge 0}$ such that $w(v)=\sum_{v\in e}w(e)$ for any $v\in V$. $$\begin{align} \sum_{v\in V}w(v) &=\sum_{v\in V}\sum_{v\in e }w(e) =\sum_{e\in E }\sum_{v\in e}w(e) =\sum_{e\in E}2w(e) =2\sum_{e\in E}w(e)\\ &=2\sum_{e\in E }\sum_{v\in e}m(e,v) =2\sum_{v\in V}\sum_{v\in e }m(e,v) =2\sum_{v\in V}m(v)\\ &\gt 2(k-1)\#V \end{align}$$ So there must be a vertex $b$ such that $w(b)\ge 2k-1$.

Consider the induced setup $G'(V', E')$ and $w'$, where $V'=V\setminus\{b\}$, $G'(V', E')$ is the induced graph $G[V']$ and where $w'=w|_{E'}$. For any $w'$-distributing function $d'$, we can extend it to a $w$-distributing function $d_{d'}$ where $d_{d'}$ is the same as $d'$ on $E'$ while $d_{d'}(e, b)=w(e)$ for every edge $e$ adjacent to $b$. Note that $F_k(d_{d'})= F_k(d') + 1$ since $d_{d'}(b)=\sum_{b\in e}d_{d'}(e,b) = \sum_{b\in e}w(e)=w(b)\ge 2k-1\ge k$. Then $$\begin{align}\sum_{e\in E'}w'(e)&\le\sum_{e\in E}w(e) - w(b)\\ &\lt (2k-1)F_k(m) -(2k-1)\\ &=(2k-1) \left(\min_{w\text{-distributing }d}F_k(d) -1\right)\\ &\le (2k-1) \left(\min_{w'\text{-distributing }d'}F_k(d_{d'})-1\right)\\ &\le (2k-1) \min_{w'\text{-distributing }d'}F_k(d') \end{align}$$ So, $G'(V', E')$ and $w'$ is a counterexample whose number of vertices is smaller than the number of vertices in $G$. That cannot true by our assumption about $G(V,E)$ and $w$. So claim one is proved.


For any vertex $v$, define $v$ $d$-reachable from vertex $u$ if there is a path $u_0= u, u_1, u_2, \cdots, u_m, u_{m+1}=v$, $m\ge0$ such that $d(\{u_i, u_{i+1}\}, u_i)>0$. Let $V_r=V_\ell\cup \{v\in V|\exists u\in V_\ell \text{ and } v\text{ is } m\text{-reachable from } u \}$.

Claim two: $V_r = V$
Proof of claim two: Suppose $V_r\neq V$. For any vertex $v\in V_r$ and $u\notin V_r$, since we cannot reach $u$ from $v$, if $\{v, u\}$ is an edge, then $w(\{v, u\}, v) = 0.$ Consider the induced setup $G'(V', E')$ and $w'$, where $v'=V_r$, $G'(V', E')$ is the induced graph $G[V']$ and where $w'=w|_{E'}$. For any $w'$-distributing function $d'$, we can extend it to a $w$-distributing function $d_{d'}$ where $d_{d'}$ is the same as $d'$ on $E'$ and the same as $m$ on other edges. Note that $F_k(d_{d'})= F_k(d')$ since all vertices with no less than $k$ balls inside are in $V_\ell\subset V_r$. Then $$\begin{align}\sum_{e\in E'}w'(e)&\le\sum_{e\in E}w(e)\\ &\lt (2k-1)F_k(m)\\ &=(2k-1) \min_{w\text{-distributing }d}F_k(d)\\ &\le (2k-1) \min_{w'\text{-distributing }d'}F_k(d_{d'})\\ &\le (2k-1) \min_{w'\text{-distributing }d'}F_k(d') \end{align}$$ So, $G'(V', E')$ and $w'$ would be a counterexample whose number of vertices is smaller than the number of vertices in $G$. That cannot be true by our assumption about $G(V,E)$ and $w$. So claim two is proved.


Now let us prove the theorem.

Since $V_r=V$ and $V_s\neq\emptyset$, there is a path $u_0= u, u_1, u_2, \cdots, u_m, u_{m+1}=v$, $m\ge0$ with $m(u)\gt k$, $m(v)\leq k-2$ and $d(\{u_i, u_{i+1}\}, u_i)>0$. Let us construct a new $w$-distributing function $r(m)$ from $m$ so that $$r(m)(e, u)= \begin{cases} m(\{u_i, u_{i+1}\}, u_i) -1 & \text{ if } (e,u)=(\{u_i, u_{i+1}\},u_i)\text { for some } 0\le i\le m\\ m(\{u_i, u_{i+1}\}, u_{i+1}) +1 & \text{ if } (e,u)=(\{u_i, u_{i+1}\},u_{i+1})\text { for some } 0\le i\le m\\ m(e,u) &\text{ otherwise } \end{cases}$$

$m$ and $r(m)$ agrees on all vertices except $v$ and $u$, $m(v)\lt r(m)(v)\le k-1$ and $r(m)(u)\lt m(u)$. We can apply this procedure on $r(m)$ to get $r^2(m)$. Repeating this $i$ time for some large enough $i$, we will obtain a $w$-distributing function $r^i(m)$ with $F_k(r^i(m))=0$. However, we have assumed that $F_k(m)>0$ is the minimum among $F(d)$ of $w$-distributing function $d$. This contradiction shows that we have proved the Erel-Apass theorem.

$\endgroup$
  • $\begingroup$ I read the proof, it looks good. In fact, if I understand correctly, it is even more general since it allows for an arbitrary graph - my question is a special case where G is the complete graph. Is this correct? Another question: where exactly does the proof use the fact that m is such that Fk(m) is minimal? I see that it is used only at the last paragraph - are the previous claims in the proof true without this fact? $\endgroup$ – Erel Segal-Halevi Oct 31 '18 at 8:03
  • $\begingroup$ Yes, the theorem is correct for any graph since it says "for any (simple finite) graph G(V,E)". The minimality of $F_k(m)$ is necessary for each claim. If you search for "counterexample", you will find where the minimality is used. $\endgroup$ – John L. Nov 5 '18 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.