Napełnianie pojemników parami kulek

Kosz jest nazywany pełnym, jeśli zawiera co najmniej kulek. Naszym celem jest, aby jak najwięcej pojemników było pełnych. $k$

W najprostszym scenariuszu otrzymujemy piłek i możemy je dowolnie rozmieścić. W takim przypadku, oczywiście najlepsze, co możemy zrobić, to wybrać kosze i umieścić dowolnie kulki w każdej z nich. $n$ $\lfloor n/k \rfloor$ $k$

Interesuje mnie następujący scenariusz: otrzymujemy par piłek. Musimy umieścić dwie kule każdej pary w dwóch różnych pojemnikach. Następnie przychodzi przeciwnik i usuwa jedną piłkę z każdej pary. Co możemy zrobić, aby mieć maksymalną możliwą liczbę pełnych pojemników po usunięciu? $n$

Prostą strategią jest: wybór par pojemników. Wypełnij każdą parę pojemników parami kulek (każdy pojemnik zawiera kulek , jedna piłka z każdej pary). Następnie, niezależnie od tego, co usuwa nasz przeciwnik, w każdej parze bin mamy co najmniej jeden pełny bin. $\lfloor n/(2k-1) \rfloor$ $2k-1$ $2k-1$

Czy mamy strategię, która pozwala osiągnąć większą liczbę pełnych pojemników (więcej niż )? $\lfloor n/(2k-1) \rfloor$

combinatorics balls-and-bins

— Erel Segal-Halevi
źródło

Nie wierzę tak

— Zach Saucier

n

$n$ podano a podano ? zależy od ?

k

$k$

k

$k$

n

$n$

— Zły

@EvilJS i są podane i są niezależne.

n

$n$

k

$k$

— Erel Segal-Halevi

Czy gracz umieszcza wszystkie swoje par piłek, a następnie przeciwnik wybiera piłek? Czy też gracz umieszcza parę piłek, a następnie przeciwnik wybiera jedną z tej pary, a następnie gracz kładzie następną parę i przeciwnik wybiera i tak dalej, dopóki nie będzie już więcej par piłek do umieszczenia?

n

$n$

n

$n$

— rotia 10.04.16

@rotia Gracz umieszcza wszystkie swoje n par piłek, a następnie przeciwnik wybiera n piłek.

— Erel Segal-Halevi

TL; DR - Nie, nie ma lepszej strategii niż prosta strategia. Oto główna idea dowodu. Kiedy nie ma wystarczającej liczby piłek, powstanie „ścieżka piłki” od kosza pełnego do kosza zawierającego co najwyżej kulek. Przeciwnik może podać piłkę z tego pełnego pojemnika do tego mniej pełnego pojemnika wzdłuż tej ścieżki, co można powtarzać do momentu zmniejszenia liczby pełnych pojemników. $k$ $k-2$ $k$

Reformulacja w teorii grafów

Załóżmy, że otrzymaliśmy prosty skończony wykres z funkcją . Mówimy, że w krawędzi znajdują się piłki . Niech będzie (krawędzią zaznaczoną na końcu) zestaw . Jeśli spełnia dla każdej krawędzi , mówimy, że jest -dystrybucja. Każda dystrybuująca funkcja indukuje funkcję, której używamy tego samego symbolu, , . Mówimy tak $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}$ $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)$ piłki są w . Biorąc pod uwagę , niech , liczba pełnych wierzchołków o . $v$ $k\in\Bbb Z_{\gt0}$ $F_k(d)=\#\{v\in V|d(v)\ge k\}$ $k$ $d$

(Twierdzenie Erel-Apassa) Dla każdego prostego grafu skończonego i mamy $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)$

Wyobraź sobie, że każdy wierzchołek to kosz. Dla każdej krawędzi , pary są umieszczane w i , z których każda otrzymuje piłki . Spośród tych par piłek przeciwnik może zabrać piłki z i z . Końcowy wynik jest taki sam, jak w przypadku, biorąc pod uwagę wszystkie puste pojemniki początkowo, na każdej krawędzi , kulki umieszcza się w niej, a następnie, i piłki są dystrybuowane do i $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$ odpowiednio przez przeciwnika. Stąd twierdzenie Erel-Apass mówi, że aby zapewnić k-pełne kosze po usunięciu inteligentnego przeciwnika, potrzebne są co najmniej par kulek. $t$ $(2k-1)t$ Innymi słowy, optymalną strategią pozwalającą na pozostawienie maksymalnej możliwej liczby pełnych pojemników jest w rzeczywistości „prosta strategia”, która wielokrotnie wypełnia inną parę pojemników parami kulek dopóki nie będziemy mieć wystarczającej liczby powtórzeń. $2k-1$

Dowód twierdzenia

Dla sprzeczności niech i będą kontrprzykładem, którego liczba wierzchołków jest najmniejsza spośród wszystkich kontrprzykładów. Oznacza to, że -dystrybucja taka, że jest minimalne wśród wszystkich funkcji -dystrybucji . Ponadto $G(V,E)$ $w$ $w$ $m$ $F_k(m)$ $F_k(d)$ $w$ $d$

\sum_{e \in E} w (e) < (2 k - 1) F_{k} (m)

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

Niech . Niech . Więc . $V_s=\{v\in V | m(v)\le k-2\}$ $V_\ell=\{v\in V|m(v)\geq k\}$ $F_k(m)=\#V_\ell$

Zgłoś jedno: . $V_s\neq\emptyset$
Dowód roszczenia pierwszego. Załóżmy inaczej, że jest puste. Użyjmy również jako funkcji od do tak że dla każdej . $V_s$

\sum_{v \in V} m (v) = (k - 1) # V + \sum_{v \in V} (m (v) - (k - 1)) \geq (k - 1) # V + # V_{ℓ} > (k - 1) # V

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

$w$

V

$V$

Z_{\geq 0}

$\Bbb Z_{\ge 0}$

w (v) = \sum_{v \in e} w (e)

$w(v)=\sum_{v\in e}w(e)$

v \in V

$v\in V$

\begin{aligned} \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} 2 w (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) \\ > 2 (k - 1) # V \end{aligned}

$\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}$ Więc musi istnieć wierzchołek taki, że .

b

$b$

w (b) \geq 2 k - 1

$w(b)\ge 2k-1$

Rozważ indukowaną konfigurację i , gdzie , jest indukowanym wykresem i gdzie . Dla każdego -distributing funkcji , można rozszerzyć go na -distributing funkcji gdzie jest taki sam jak na , a dla każdej krawędzi sąsiadującej z . Zauważ, że od tego czasu $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$ . Następnie SO, i jest kontrprzykładem których liczba wierzchołków jest mniejsza niż liczba wierzchołków . Nie może to być prawdą przy założeniu, że i . Więc twierdzą, że jeden został udowodniony.

\begin{aligned} \sum_{e \in E^{'}} w^{'} (e) & \leq \sum_{e \in E} w (e) - w (b) \\ < (2 k - 1) F_{k} (m) - (2 k - 1) \\ = (2 k - 1) (min_{w -distributing d} F_{k} (d) - 1) \\ \leq (2 k - 1) (min_{w^{'} -distributing d^{'}} F_{k} (d_{d^{'}}) - 1) \\ \leq (2 k - 1) min_{w^{'} -distributing d^{'}} F_{k} (d^{'}) \end{aligned}

$\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^{'})

$G'(V', E')$

w^{'}

$w'$

G

$G$

G (V, E)

$G(V,E)$

w

$w$

Dla dowolnego wierzchołka zdefiniuj osiągalny z wierzchołka jeśli istnieje ścieżka , tak że . Niech . $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 \}$

Twierdzenie dwa: $V_r = V$
Dowód zastrz dwa Przypuśćmy . Dla każdego wierzchołka i , ponieważ nie można osiągnąć z , jeśli jest krawędzią, a następnie Rozważmy indukowana konfiguracja i , gdzie , jest indukowanym wykresem i gdzie . Dla każdego -distributing funkcji , $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'}$ gdzie jest taki sam jak na i taki sam jak na innych krawędziach. Zauważ, że ponieważ wszystkie wierzchołki z nie mniej niż kulkami w środku znajdują się w . Następnie Więc, i $d_{d'}$ $d'$ $E'$ $m$ $F_k(d_{d'})= F_k(d')$ $k$ $V_\ell\subset V_r$

\begin{aligned} \sum_{e \in E^{'}} w^{'} (e) & \leq \sum_{e \in E} w (e) \\ < (2 k - 1) F_{k} (m) \\ = (2 k - 1) min_{w -distributing d} F_{k} (d) \\ \leq (2 k - 1) min_{w^{'} -distributing d^{'}} F_{k} (d_{d^{'}}) \\ \leq (2 k - 1) min_{w^{'} -distributing d^{'}} F_{k} (d^{'}) \end{aligned}

$\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^{'})

$G'(V', E')$

w^{'}

$w'$

G

$G$ . Nie może to być prawdą przy założeniu, że i . Więc twierdzą, że dwa zostały udowodnione.

G (V, E)

$G(V,E)$

w

$w$

Udowodnijmy teraz twierdzenie.

Ponieważ i , istnieje ścieżka , with , i . Stwórzmy nową funkcję -dystrybucji z , aby $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 & if (e, u) = ({u_{i}, u_{i + 1}}, u_{i}) for some 0 \leq i \leq m \\ m ({u_{i}, u_{i + 1}}, u_{i + 1}) + 1 & if (e, u) = ({u_{i}, u_{i + 1}}, u_{i + 1}) for some 0 \leq i \leq m \\ m (e, u) & otherwise \end{cases}

$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$ i zgadza się, z wyjątkiem wszystkich wierzchołków i , i . Możemy zastosować tę procedurę do aby uzyskać . Powtarzając ten czas na wystarczająco dużą , otrzyma się -distributing funkcji z . jednak, że jest minimum wśród funkcji dystrybuującej $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$ . Ta sprzeczność pokazuje, że udowodniliśmy twierdzenie Erel-Apass.

— John L.
źródło

Przeczytałem dowód, wygląda dobrze. W rzeczywistości, jeśli dobrze rozumiem, jest to jeszcze bardziej ogólne, ponieważ pozwala na dowolny wykres - moje pytanie jest szczególnym przypadkiem, w którym G jest kompletnym wykresem. Czy to jest poprawne? Kolejne pytanie: gdzie dokładnie dowód wykorzystuje fakt, że m jest takie, że Fk (m) jest minimalne? Widzę, że jest on używany tylko w ostatnim akapicie - czy poprzednie twierdzenia w dowodzie są prawdziwe bez tego faktu?

— Erel Segal-Halevi

Tak, twierdzenie jest poprawne dla każdego wykresu, ponieważ mówi „dla dowolnego (prostego skończonego) wykresu G (V, E)”. Minimalność z jest konieczne dla każdego z zastrz. Jeśli szukasz „kontrprzykładu”, dowiesz się, gdzie stosowana jest minimalność.

F_{k} (m)

$F_k(m)$

— John L.,