Return to Answer

Let us show that a required $k$-times bin-packing exists for some $k\le n^{n/2}$.

Let $V=\{(v_1,\dots,v_n)\in\{0,1\}^n:\sum_{i=1}^n d_iv_i\le s\}$ be the set of all admissible "bin packings". Then the convex hull $\operatorname{conv} V$ of $V$ is the set of all possible "schedules".

Let $e=(1,1,\dots,1)\in\mathbb R^n$. Then $r_\max=\sup\{r\in [0,1]:re\in\operatorname{conv} V\}$. Since the set $\operatorname{conv} V$ is compact, $r_\max$ is attained, that is $r_\max e\in \operatorname{conv} V$. We assume that the electricity division problem has a solution, so $r_\max>0$.

Here is an illustration, based on the example in the question:

The three blue points are the points in $V$, which are $(1,1,0)$, $(1,0,1)$ and $(0,1,1)$. The ray from the origin is $e\cdot \{r:r \ge 0\}$. The green point is the intersection of this ray with $\operatorname{conv} V$; its coordinates are $(2/3, 2/3, 2/3)$, which correspond to $r_{\max}=2/3$.

By Carathéodory's theorem, there exists an $n$ dimensional simplex $S$ with vertices in $V$ such that $r_\max e\in S$.

Let $V'$ be the set of the vertices of the face of $S$ of minimal dimension containing $r_\max e$. Clearly, $r_\max e$ is a boundary point of $S$, so $|V'|\le n$. In other words, the optimal electricity division can be constructed using most $n$ different configurations (in the example $V' = V$ and $|V'|=n=3$).

Let $(\lambda_v)_{v\in V'}$ be the barycentric coordinates of $r_\max e$, such that $\lambda_v>0$ for each $v\in V'$ and $\sum_{v\in V'}\lambda_v=1$ and $r_\max e =\sum_{v\in V'}\lambda_v v$. For instance, in the example $\lambda_v =1/3$ for each $v\in V'$.

We claim that the set $V'$ is linearly independent. Indeed, suppose for a contradiction that there exist disjoint nonempty subsets $V_1'$ and $V_2'$ of $V$ and positive numbers $(\mu_v)_{v\in V'_1\cup V_2'}$ such that $\sum_{v\in V_1'} \mu_v v=\sum_{v\in V_2'} \mu_v v$ and $\sum_{v\in V_1'} \mu_v \le \sum_{v\in V_2'} \mu_v$. Let $\nu=\min_{v\in V_2'} \lambda_v/\mu_v$. Then $$r_\max e =\sum_{v\in V'}\lambda_v v=\sum_{v\in V'}\lambda_v v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)=\sum_{v\in V'}\lambda_v' v,$$ where $$\lambda_v' v=\cases{ \lambda_v+\nu\mu_v, & if $v\in V_1'$,\\ \lambda_v-\nu\mu_v, & if $v\in V_2'$,\\ \lambda_v, & if $v\in V'\setminus (V_1'\cup V_2')$. }$$ Then $s=\sum_{v\in V'}\lambda_v'=\sum_{v\in V'}\lambda_v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)\le 1$, $\lambda_v'\ge 0$ for each $v\in V'$, and $\lambda_v'=0$ for some $v\in V_2'$. Then $s^{-1}r_\max e \in\operatorname{conv} V'\setminus\{v\}$, that contradicts to the minimality of $V'$.

Since the set $V''=V'\cup\{e\}$ is linearly dependent, by Lemma 2 from this answer to Integer coefficients in zero linear combinations of dependent vectors there exist integers $(\Delta_v)_{v\in V''}$ which are not all zeroes such that $|\Delta_v|\le n^{n/2}$ for each $v\in V''$ and $\sum_{v\in V''} \Delta_vv=0$. The set $V'$ is linearly independent, so $\Delta_e\ne 0$ and $e=\sum_{v\in V'} (-\Delta_v/\Delta_e) v=\sum_{v\in V'} (\lambda_v/r_\max) v$. Thus $-\Delta_v/\Delta_e=\lambda_v/r_\max>0$ for each $v\in V'$. Thus the coefficients $(\Delta_v)_{v\in V''}$ provide a required $|\Delta_e|$-times bin-packing.

Let us show that a required $k$-times bin-packing exists for some $k\le n^{n/2}$.

Let $V=\{(v_1,\dots,v_n)\in\{0,1\}^n:\sum_{i=1}^n d_iv_i\le s\}$ be the set of all admissible "bin packings". Then the convex hull $\operatorname{conv} V$ of $V$ is the set of all possible "schedules".

Let $e=(1,1,\dots,1)\in\mathbb R^n$. Then $r_\max=\sup\{r\in [0,1]:re\in\operatorname{conv} V\}$. Since the set $\operatorname{conv} V$ is compact, $r_\max$ is attained, that is $r_\max e\in \operatorname{conv} V$. We assume that the electricity division problem has a solution, so $r_\max>0$.

Here is an illustration, based on the example in the question:

The three blue points are the points in $V$, which are $(1,1,0)$, $(1,0,1)$ and $(0,1,1)$. The ray from the origin is $e\cdot \{r:r \ge 0\}$. The green point is the intersection of this ray with $\operatorname{conv} V$; its coordinates are $(2/3, 2/3, 2/3)$, which correspond to $r_{\max}=2/3$.

By Carathéodory's theorem, there exists an $n$ dimensional simplex $S$ with vertices in $V$ such that $r_\max e\in S$.

Let $V'$ be the set of the vertices of the face of $S$ of minimal dimension containing $r_\max e$. Clearly, $r_\max e$ is a boundary point of $S$, so $|V'|\le n$. In other words, the optimal electricity division can be constructed using most $n$ different configurations (in the example $V' = V$ and $|V'|=n=3$).

Let $(\lambda_v)_{v\in V'}$ be the barycentric coordinates of $r_\max e$, such that $\lambda_v>0$ for each $v\in V'$ and $\sum_{v\in V'}\lambda_v=1$ and $r_\max e =\sum_{v\in V'}\lambda_v v$. For instance, in the example $\lambda_v =1/3$ for each $v\in V'$.

We claim that the set $V'$ is linearly independent. Indeed, suppose for a contradiction that there exist disjoint nonempty subsets $V_1'$ and $V_2'$ of $V$ and positive numbers $(\mu_v)_{v\in V'_1\cup V_2'}$ such that $\sum_{v\in V_1'} \mu_v v=\sum_{v\in V_2'} \mu_v v$ and $\sum_{v\in V_1'} \mu_v \le \sum_{v\in V_2'} \mu_v$. Let $\nu=\min_{v\in V_2'} \lambda_v/\mu_v$. Then $$r_\max e =\sum_{v\in V'}\lambda_v v=\sum_{v\in V'}\lambda_v v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)=\sum_{v\in V'}\lambda_v' v,$$ where $$\lambda_v' v=\cases{ \lambda_v+\nu\mu_v, & if $v\in V_1'$,\\ \lambda_v-\nu\mu_v, & if $v\in V_2'$,\\ \lambda_v, & if $v\in V'\setminus (V_1'\cup V_2')$. }$$ Then $s=\sum_{v\in V'}\lambda_v'=\sum_{v\in V'}\lambda_v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)\le 1$, $\lambda_v'\ge 0$ for each $v\in V'$, and $\lambda_v'=0$ for some $v\in V_2'$. Then $s^{-1}r_\max e \in\operatorname{conv} V'\setminus\{v\}$, that contradicts to the minimality of $V'$.

Since the set $V''=V'\cup\{e\}$ is linearly dependent, by Lemma 2 from this answer to Integer coefficients in zero linear combinations of dependent vectors there exist integers $(\Delta_v)_{v\in V''}$ which are not all zeroes such that $|\Delta_v|\le n^{n/2}$ for each $v\in V''$ and $\sum_{v\in V''} \Delta_vv=0$. The set $V'$ is linearly independent, so $\Delta_e\ne 0$ and $e=\sum_{v\in V'} (-\Delta_v/\Delta_e) v=\sum_{v\in V'} (\lambda_v/r_\max) v$. Thus $-\Delta_v/\Delta_e=\lambda_v/r_\max>0$ for each $v\in V'$. Thus the coefficients $(|\Delta_v|)_{v\in V''}$ provide a required $|\Delta_e|$-times bin-packing.

Let us show that a required $k$-times bin-packing exists for some $k\le n^{n/2}$.

Let $V=\{(v_1,\dots,v_n)\in\{0,1\}^n:\sum_{i=1}^n d_iv_i\le s\}$ be the set of all admissible "bin packings". Then the convex hull $\operatorname{conv} V$ of $V$ is the set of all possible "schedules".

Let $e=(1,1,\dots,1)\in\mathbb R^n$. Then $r_\max=\sup\{r\in [0,1]:re\in\operatorname{conv} V\}$. Since the set $\operatorname{conv} V$ is compact, $r_\max$ is attained, that is $r_\max e\in \operatorname{conv} V$. We assume that the electricity division problem has a solution, so $r_\max>0$.

Here is an illustration, based on the example in the question:

The three blue points are the points in $V$, which are $(1,1,0)$, $(1,0,1)$ and $(0,1,1)$. The ray from the origin is $e\cdot \{r:r \ge 0\}$. The green point is the intersection of this ray with $V$; its coordinates are $(2/3, 2/3, 2/3)$, which correspond to $r_{\max}=2/3$.

By Carathéodory's theorem, there exists an $n$ dimensional simplex $S$ with vertices in $V$ such that $r_\max e\in S$.

Let $V'$ be the set of the vertices of the face of $S$ of minimal dimension containing $r_\max e$. Clearly, $r_\max e$ is a boundary point of $S$, so $|V'|\le n$. In other words, the optimal electricity division can be constructed using most $n$ different configurations (in the example $V' = V$ and $|V'|=n=3$).

Let $(\lambda_v)_{v\in V'}$ be the barycentric coordinates of $r_\max e$, such that $\lambda_v>0$ for each $v\in V'$ and $\sum_{v\in V'}\lambda_v=1$ and $r_\max e =\sum_{v\in V'}\lambda_v v$. For instance, in the example $\lambda_v =1/3$ for each $v\in V'$.

We claim that the set $V'$ is linearly independent. Indeed, suppose for a contradiction that there exist disjoint nonempty subsets $V_1'$ and $V_2'$ of $V$ and positive numbers $(\mu_v)_{v\in V'_1\cup V_2'}$ such that $\sum_{v\in V_1'} \mu_v v=\sum_{v\in V_2'} \mu_v v$ and $\sum_{v\in V_1'} \mu_v \le \sum_{v\in V_2'} \mu_v$. Let $\nu=\min_{v\in V_2'} \lambda_v/\mu_v$. Then $$r_\max e =\sum_{v\in V'}\lambda_v v=\sum_{v\in V'}\lambda_v v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)=\sum_{v\in V'}\lambda_v' v,$$ where $$\lambda_v' v=\cases{ \lambda_v+\nu\mu_v, & if $v\in V_1'$,\\ \lambda_v-\nu\mu_v, & if $v\in V_2'$,\\ \lambda_v, & if $v\in V'\setminus (V_1'\cup V_2')$. }$$ Then $s=\sum_{v\in V'}\lambda_v'=\sum_{v\in V'}\lambda_v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)\le 1$, $\lambda_v'\ge 0$ for each $v\in V'$, and $\lambda_v'=0$ for some $v\in V_2'$. Then $s^{-1}r_\max e \in\operatorname{conv} V'\setminus\{v\}$, that contradicts to the minimality of $V'$.

Since the set $V''=V'\cup\{e\}$ is linearly dependent, by Lemma 2 from this answer to Integer coefficients in zero linear combinations of dependent vectors there exist integers $(\Delta_v)_{v\in V''}$ which are not all zeroes such that $|\Delta_v|\le n^{n/2}$ for each $v\in V''$ and $\sum_{v\in V''} \Delta_vv=0$. The set $V'$ is linearly independent, so $\Delta_e\ne 0$ and $e=\sum_{v\in V'} (-\Delta_v/\Delta_e) v=\sum_{v\in V'} (\lambda_v/r_\max) v$. Thus $-\Delta_v/\Delta_e=\lambda_v/r_\max>0$ for each $v\in V'$. Thus the coefficients $(\Delta_v)_{v\in V''}$ provide a required $|\Delta_e|$-times bin-packing.

Let us show that a required $k$-times bin-packing exists for some $k\le n^{n/2}$.

Let $V=\{(v_1,\dots,v_n)\in\{0,1\}^n:\sum_{i=1}^n d_iv_i\le s\}$ be the set of all admissible "bin packings". Then the convex hull $\operatorname{conv} V$ of $V$ is the set of all possible "schedules".

Let $e=(1,1,\dots,1)\in\mathbb R^n$. Then $r_\max=\sup\{r\in [0,1]:re\in\operatorname{conv} V\}$. Since the set $\operatorname{conv} V$ is compact, $r_\max$ is attained, that is $r_\max e\in \operatorname{conv} V$. We assume that the electricity division problem has a solution, so $r_\max>0$.

Here is an illustration, based on the example in the question:

The three blue points are the points in $V$, which are $(1,1,0)$, $(1,0,1)$ and $(0,1,1)$. The ray from the origin is $e\cdot \{r:r \ge 0\}$. The green point is the intersection of this ray with $\operatorname{conv} V$; its coordinates are $(2/3, 2/3, 2/3)$, which correspond to $r_{\max}=2/3$.

By Carathéodory's theorem, there exists an $n$ dimensional simplex $S$ with vertices in $V$ such that $r_\max e\in S$.

Let $V'$ be the set of the vertices of the face of $S$ of minimal dimension containing $r_\max e$. Clearly, $r_\max e$ is a boundary point of $S$, so $|V'|\le n$. In other words, the optimal electricity division can be constructed using most $n$ different configurations (in the example $V' = V$ and $|V'|=n=3$).

Let $(\lambda_v)_{v\in V'}$ be the barycentric coordinates of $r_\max e$, such that $\lambda_v>0$ for each $v\in V'$ and $\sum_{v\in V'}\lambda_v=1$ and $r_\max e =\sum_{v\in V'}\lambda_v v$. For instance, in the example $\lambda_v =1/3$ for each $v\in V'$.

We claim that the set $V'$ is linearly independent. Indeed, suppose for a contradiction that there exist disjoint nonempty subsets $V_1'$ and $V_2'$ of $V$ and positive numbers $(\mu_v)_{v\in V'_1\cup V_2'}$ such that $\sum_{v\in V_1'} \mu_v v=\sum_{v\in V_2'} \mu_v v$ and $\sum_{v\in V_1'} \mu_v \le \sum_{v\in V_2'} \mu_v$. Let $\nu=\min_{v\in V_2'} \lambda_v/\mu_v$. Then $$r_\max e =\sum_{v\in V'}\lambda_v v=\sum_{v\in V'}\lambda_v v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)=\sum_{v\in V'}\lambda_v' v,$$ where $$\lambda_v' v=\cases{ \lambda_v+\nu\mu_v, & if $v\in V_1'$,\\ \lambda_v-\nu\mu_v, & if $v\in V_2'$,\\ \lambda_v, & if $v\in V'\setminus (V_1'\cup V_2')$. }$$ Then $s=\sum_{v\in V'}\lambda_v'=\sum_{v\in V'}\lambda_v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)\le 1$, $\lambda_v'\ge 0$ for each $v\in V'$, and $\lambda_v'=0$ for some $v\in V_2'$. Then $s^{-1}r_\max e \in\operatorname{conv} V'\setminus\{v\}$, that contradicts to the minimality of $V'$.

Since the set $V''=V'\cup\{e\}$ is linearly dependent, by Lemma 2 from this answer to Integer coefficients in zero linear combinations of dependent vectors there exist integers $(\Delta_v)_{v\in V''}$ which are not all zeroes such that $|\Delta_v|\le n^{n/2}$ for each $v\in V''$ and $\sum_{v\in V''} \Delta_vv=0$. The set $V'$ is linearly independent, so $\Delta_e\ne 0$ and $e=\sum_{v\in V'} (-\Delta_v/\Delta_e) v=\sum_{v\in V'} (\lambda_v/r_\max) v$. Thus $-\Delta_v/\Delta_e=\lambda_v/r_\max>0$ for each $v\in V'$. Thus the coefficients $(\Delta_v)_{v\in V''}$ provide a required $|\Delta_e|$-times bin-packing.

Let us show that a required $k$-times bin-packing exists for some $k\le n^{n/2}$.

Let $V=\{(v_1,\dots,v_n)\in\{0,1\}^n:\sum_{i=1}^n d_iv_i\le s\}$ be the set of all admissible "bin packings". Then the convex hull $\operatorname{conv} V$ of $V$ is the set of all possible ``schedules''.

Let $e=(1,1,\dots,1)\in\mathbb R^n$. Then $r_\max=\sup\{r\in [0,1]:re\in\operatorname{conv} V\}$. Since the set $\operatorname{conv} V$ is compact, $r_\max$ is attained, that is $r_\max e\in \operatorname{conv} V$. We assume that the electricity division problem has a solution, so $r_\max>0$.

Here is an illustration, based on the example in the question:

The three blue points are the points in $V$, which are $(1,1,0)$, $(1,0,1)$ and $(0,1,1)$. The ray from the origin is $e\cdot \{r:r \ge 0\}$. The green point is the intersection of this ray with $V$; its coordinates are $(2/3, 2/3, 2/3)$, which correspond to $r_{\max}=2/3$.

By Carathéodory's theorem, there exists an $n$ dimensional simplex $S$ with vertices in $V$ such that $r_\max e\in S$.

Let $V'$ be the set of the vertices of the face of $S$ of minimal dimension containing $r_\max e$. Clearly, $r_\max e$ is a boundary point of $S$, so $|V'|\le n$. In other words, the optimal electricity division can be constructed using most $n$ different configurations (in the example $V' = V$ and $|V'|=n=3$).

Let $(\lambda_v)_{v\in V'}$ be the barycentric coordinates of $r_\max e$, such that $\lambda_v>0$ for each $v\in V'$ and $\sum_{v\in V'}\lambda_v=1$ and $r_\max e =\sum_{v\in V'}\lambda_v v$. For instance, in the example $\lambda_v =1/3$ for each $v\in V'$.

We claim that the set $V'$ is linearly independent. Indeed, suppose for a contradiction that there exist disjoint nonempty subsets $V_1'$ and $V_2'$ of $V$ and positive numbers $(\mu_v)_{v\in V'_1\cup V_2'}$ such that $\sum_{v\in V_1'} \mu_v v=\sum_{v\in V_2'} \mu_v v$ and $\sum_{v\in V_1'} \mu_v \le \sum_{v\in V_2'} \mu_v$. Let $\nu=\min_{v\in V_2'} \lambda_v/\mu_v$. Then $$r_\max e =\sum_{v\in V'}\lambda_v v=\sum_{v\in V'}\lambda_v v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)=\sum_{v\in V'}\lambda_v' v,$$ where $$\lambda_v' v=\cases{ \lambda_v+\nu\mu_v, & if $v\in V_1'$,\\ \lambda_v-\nu\mu_v, & if $v\in V_2'$,\\ \lambda_v, & if $v\in V'\setminus (V_1'\cup V_2')$. }$$ Then $s=\sum_{v\in V'}\lambda_v'=\sum_{v\in V'}\lambda_v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)\le 1$, $\lambda_v'\ge 0$ for each $v\in V'$, and $\lambda_v'=0$ for some $v\in V_2'$. Then $s^{-1}r_\max e \in\operatorname{conv} V'\setminus\{v\}$, that contradicts to the minimality of $V'$.

Since the set $V''=V'\cup\{e\}$ is linearly dependent, by Lemma 2 from this answer there exist integers $(\Delta_v)_{v\in V''}$ which are not all zeroes such that $|\Delta_v|\le n^{n/2}$ for each $v\in V''$ and $\sum_{v\in V''} \Delta_vv=0$. The set $V'$ is linearly independent, so $\Delta_e\ne 0$ and $e=\sum_{v\in V'} (-\Delta_v/\Delta_e) v=\sum_{v\in V'} (\lambda_v/r_\max) v$. Thus $-\Delta_v/\Delta_e=\lambda_v/r_\max>0$ for each $v\in V'$. Thus the coefficients $(\Delta_v)_{v\in V''}$ provide a required $|\Delta_e|$-times bin-packing.

Let us show that a required $k$-times bin-packing exists for some $k\le n^{n/2}$.

Let $V=\{(v_1,\dots,v_n)\in\{0,1\}^n:\sum_{i=1}^n d_iv_i\le s\}$ be the set of all admissible "bin packings". Then the convex hull $\operatorname{conv} V$ of $V$ is the set of all possible "schedules".

Let $e=(1,1,\dots,1)\in\mathbb R^n$. Then $r_\max=\sup\{r\in [0,1]:re\in\operatorname{conv} V\}$. Since the set $\operatorname{conv} V$ is compact, $r_\max$ is attained, that is $r_\max e\in \operatorname{conv} V$. We assume that the electricity division problem has a solution, so $r_\max>0$.

Here is an illustration, based on the example in the question:

The three blue points are the points in $V$, which are $(1,1,0)$, $(1,0,1)$ and $(0,1,1)$. The ray from the origin is $e\cdot \{r:r \ge 0\}$. The green point is the intersection of this ray with $V$; its coordinates are $(2/3, 2/3, 2/3)$, which correspond to $r_{\max}=2/3$.

By Carathéodory's theorem, there exists an $n$ dimensional simplex $S$ with vertices in $V$ such that $r_\max e\in S$.

Let $V'$ be the set of the vertices of the face of $S$ of minimal dimension containing $r_\max e$. Clearly, $r_\max e$ is a boundary point of $S$, so $|V'|\le n$. In other words, the optimal electricity division can be constructed using most $n$ different configurations (in the example $V' = V$ and $|V'|=n=3$).

Let $(\lambda_v)_{v\in V'}$ be the barycentric coordinates of $r_\max e$, such that $\lambda_v>0$ for each $v\in V'$ and $\sum_{v\in V'}\lambda_v=1$ and $r_\max e =\sum_{v\in V'}\lambda_v v$. For instance, in the example $\lambda_v =1/3$ for each $v\in V'$.

We claim that the set $V'$ is linearly independent. Indeed, suppose for a contradiction that there exist disjoint nonempty subsets $V_1'$ and $V_2'$ of $V$ and positive numbers $(\mu_v)_{v\in V'_1\cup V_2'}$ such that $\sum_{v\in V_1'} \mu_v v=\sum_{v\in V_2'} \mu_v v$ and $\sum_{v\in V_1'} \mu_v \le \sum_{v\in V_2'} \mu_v$. Let $\nu=\min_{v\in V_2'} \lambda_v/\mu_v$. Then $$r_\max e =\sum_{v\in V'}\lambda_v v=\sum_{v\in V'}\lambda_v v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)=\sum_{v\in V'}\lambda_v' v,$$ where $$\lambda_v' v=\cases{ \lambda_v+\nu\mu_v, & if $v\in V_1'$,\\ \lambda_v-\nu\mu_v, & if $v\in V_2'$,\\ \lambda_v, & if $v\in V'\setminus (V_1'\cup V_2')$. }$$ Then $s=\sum_{v\in V'}\lambda_v'=\sum_{v\in V'}\lambda_v+\nu(\sum_{v\in V_1'} \mu_v v-\sum_{v\in V_2'} \mu_v v)\le 1$, $\lambda_v'\ge 0$ for each $v\in V'$, and $\lambda_v'=0$ for some $v\in V_2'$. Then $s^{-1}r_\max e \in\operatorname{conv} V'\setminus\{v\}$, that contradicts to the minimality of $V'$.

Since the set $V''=V'\cup\{e\}$ is linearly dependent, by Lemma 2 from this answer to Integer coefficients in zero linear combinations of dependent vectors there exist integers $(\Delta_v)_{v\in V''}$ which are not all zeroes such that $|\Delta_v|\le n^{n/2}$ for each $v\in V''$ and $\sum_{v\in V''} \Delta_vv=0$. The set $V'$ is linearly independent, so $\Delta_e\ne 0$ and $e=\sum_{v\in V'} (-\Delta_v/\Delta_e) v=\sum_{v\in V'} (\lambda_v/r_\max) v$. Thus $-\Delta_v/\Delta_e=\lambda_v/r_\max>0$ for each $v\in V'$. Thus the coefficients $(\Delta_v)_{v\in V''}$ provide a required $|\Delta_e|$-times bin-packing.