Заполнение бункеров парами шаров

Контейнер называется полным, если он содержит не менее шаров. Наша цель - заполнить как можно больше ящиков.$k$

В простейшем сценарии нам дано шаров, и мы можем расположить их произвольно. В этом случае, очевидно, лучшее, что мы можем сделать, - это произвольно выбрать мусорных ведер и положить шаров в каждый из них.$n$$\lfloor n/k \rfloor$$k$

Меня интересует следующий сценарий: нам дано пар шаров. Мы должны поместить два шара каждой пары в два разных контейнера. Затем противник приходит и удаляет один шар из каждой пары. Что мы можем сделать, чтобы получить максимально возможное количество полных корзин после удаления?$n$

Простая стратегия такова: выбрать пар бинов. Заполните каждую пару шарами (каждый бин содержит шара, по одному шару от каждой пары). Затем, независимо от того, что удаляет наш противник, в каждой паре бинов есть хотя бы один полный бин.$\lfloor n/(2k-1) \rfloor$$2k-1$$2k-1$

Есть ли у нас стратегия, которая позволяет получить большее количество полных корзин (больше, чем )?$\lfloor n/(2k-1) \rfloor$

TL; DR - нет, нет лучшей стратегии, чем простая стратегия. Вот основная идея доказательства. Когда шаров не хватает, будет «дорожка шаров» от корзины с полками до корзины с не более чем шарами. Противник может передать мяч из этого полного бина в этот менее полный бункер по этому пути, что можно делать несколько раз, пока число полных бинов не уменьшится.k - 2 $k$$k-2$$k$

---

Переформулировка в теории графов

Предположим, нам дан простой конечный граф с функцией . Мы говорим, что в ребре есть шаров . Пусть будет (конечное ребро) множество . Если удовлетворяет для каждого ребра , мы говорим, что это -distributing. Любая -распределительная функция индуцирует функцию, которую мы используем одним и тем же символом, , , Мы говорим, чтоw : E → Z ≥ 0 w ( e ) e E 2 { ( e , v ) | e ∈ E , v ∈ e } d : E 2 → Z ≥ 0 w ( e ) = d ( e , v 1 ) + d ( e , $G(V,E)$$w: E\to\Bbb Z_{\ge 0}$$w(e)$$e$$E_2$$\{(e,v)| e\in E, v\in e\}$$d:E_2\to\Bbb Z_{\ge 0}$e = { v 1 , v 2 } d w w d d : V → Z ≥ 0 d ( v ) = ∑ v ∈ e d ( e , v ) d ( v ) v k ∈ Z > 0 F k ( г ) = # { v ∈ V | д $w(e)=d(e,v_1) + d(e,v_2)$$e=\{v_1,v_2\}$$d$$w$$w$$d$$d:V\to\Bbb Z_{\ge 0}$$d(v) =\sum_{v\in e}d(e,v)$$d(v)$ шары находятся в . Учитывая , пусть , число -полных вершин на .$v$$k\in\Bbb Z_{\gt0}$k $F_k(d)=\#\{v\in V|d(v)\ge k\}$$k$$d$

(Теорема Эрла-Апаса). Для любого простого конечного графа и имеем$G(V,E)$$w:E\to\Bbb Z_{\ge0}$$\sum_{e\in E}w(e)\geq (2k-1) \min_{w\text{-distributing }d}F_k(d)$

Представьте, что каждая вершина является мусорным ведром. Для каждого ребра , шариковой пары помещают в и , каждый из которых получать шаров. Среди этих шаровых пар противник может забрать шаров из и шаров из . Конечный результат такой же, как если бы, учитывая изначально все пустые ячейки, для каждого ребра , в него помещаются шарики , а затем и шары распределены по и$e=\{v_1,v_2\}$$w(e)$$v_1$$v_2$$w(e)$$w(e)$$d(e,v_2)$$v_1$$d(e,v_1)$$v_2$$e=\{v_1, v_2\}$$w(e)$$d(e,v_1)$$d(e,v_2)$$v_1$$v_2$соответственно противником. Следовательно, теорема Эрла-Апаса говорит о том, что для обеспечения k-полных корзин после удаления умного противника необходимо по крайней мере пар шаров. $t$$(2k-1)t$Другими словами, оптимальной стратегией, позволяющей иметь максимально возможное количество оставшихся бинов, является действительно «простая стратегия», которая многократно заполняет другую пару бинов шариковыми парами, пока у нас не будет достаточно шаров для повторения.$2k-1$

---

Доказательство теоремы

Для противоречия, пусть и - контрпример, число вершин которого наименьшее среди всех контрпримеров. То есть, есть -distributing таким образом, что минимален среди всех из -distributing функции . Кроме того, $G(V,E)$$w$$w$$m$$F_k(m)$$F_k(d)$$w$$d$

$$\sum_{e\in E}w(e)\lt (2k-1)F_k(m)$$

Пусть . Пусть . Так что .$V_s=\{v\in V | m(v)\le k-2\}$$V_\ell=\{v\in V|m(v)\geq k\}$$F_k(m)=\#V_\ell$

Утвердите одно: . $V_s\neq\emptyset$
Доказательство претензии один. Предположим, что в противном случае пуст. Давайте также повторно использовать как функцию из в такую ​​что для любого . $V_s$

$$\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$$ $w$$V$$\Bbb Z_{\ge 0}$$w(v)=\sum_{v\in e}w(e)$$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}$$ Так что должна быть вершина такая, что .$b$$w(b)\ge 2k-1$

Рассмотрим индуцированные установки и , где , - индуцированный граф и где . Для любой -распределяющей функции мы можем расширить ее до -распределительной функции где совпадает с на а для каждого ребра смежного с . Обратите внимание, что так как$G'(V', E')$$w'$$V'=V\setminus\{b\}$$G'(V', E')$$G[V']$$w'=w|_{E'}$$w'$$d'$$w$$d_{d'}$$d_{d'}$$d'$$E'$$d_{d'}(e, b)=w(e)$$e$$b$$F_k(d_{d'})= F_k(d') + 1$$d_{d'}(b)=\sum_{b\in e}d_{d'}(e,b) = \sum_{b\in e}w(e)=w(b)\ge 2k-1\ge k$ . Тогда Таким образом, и представляет собой контрпример, число вершин меньше , чем число вершин в . Это не может быть верным по нашему предположению о и . Так что утверждение одно доказано.

$$\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}$$ $G'(V', E')$$w'$$G$$G(V,E)$$w$

---

Для любой вершины определите достижимый из вершины если существует путь , такой, что . Пусть .$v$$v$ $d$$u$$u_0= u, u_1, u_2, \cdots, u_m, u_{m+1}=v$$m\ge0$$d(\{u_i, u_{i+1}\}, u_i)>0$$V_r=V_\ell\cup \{v\in V|\exists u\in V_\ell \text{ and } v\text{ is } m\text{-reachable from } u \}$

Претензии два:$V_r = V$
Доказательство п два: пусть . Для любой вершины и , поскольку мы не можем достичь из , если - ребро, то Рассмотрим индуцированная установка и , где , - индуцированный граф и где . Для любой -распределительной функции ,$V_r\neq V$$v\in V_r$$u\notin V_r$$u$$v$$\{v, u\}$$w(\{v, u\}, v) = 0.$$G'(V', E')$$w'$$v'=V_r$$G'(V', E')$$G[V']$$w'=w|_{E'}$$w'$$d'$$w$$d_{d'}$где такой же, как на и такой же, как на других ребрах. Обратите внимание, что поскольку все вершины с не менее чем шарами находятся в . Тогда Итак, и$d_{d'}$$d'$$E'$$m$$F_k(d_{d'})= F_k(d')$$k$$V_\ell\subset V_r$

$$\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}$$ $G'(V', E')$$w'$$G$, Это не может быть правдой из нашего предположения о и . Итак, утверждение два доказано.$G(V,E)$$w$

---

Теперь докажем теорему.

Поскольку и , существует путь , с , и . Построим новую -распределительную функцию из так, чтобы $V_r=V$$V_s\neq\emptyset$$u_0= u, u_1, u_2, \cdots, u_m, u_{m+1}=v$$m\ge0$$m(u)\gt k$$m(v)\leq k-2$$d(\{u_i, u_{i+1}\}, u_i)>0$$w$$r(m)$$m$

$$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$ и согласованы по всем вершинам, кроме и , и . Мы можем применить эту процедуру к чтобы получить . Повторяя это время для некоторого достаточно большого , мы получим функцию распределения с . Тем не менее, мы предположили , что является минимальным среди из -distributing функции$r(m)$$v$$u$$m(v)\lt r(m)(v)\le k-1$$r(m)(u)\lt m(u)$$r(m)$$r^2(m)$$i$$i$$w$$r^i(m)$$F_k(r^i(m))=0$$F_k(m)>0$$F(d)$$w$$d$, Это противоречие показывает, что мы доказали теорему Эрла-Апаса.