Matching bins up to shuffling II

Question

Suppose a school purchases a set $\mathcal{S}$ of balls, say

$$\displaystyle \mathcal{S} = \{b_1, b_2, \cdots, b_n\}$$

with $n$ very large. The balls $b_j$ are pairwise distinct and have distinct weights; by abuse of notation, we simply say that $b_j$ is the real number representing the weight of the $j$-th ball, normalized so that

$$\displaystyle \sum_{j=1}^n b_j = 1.$$

Further assume that the weights of the balls are such that for any two distinct, disjoint subcollections of balls $\mathcal{S_1}, \mathcal{S}_2$ the total weights of the balls in $\mathcal{S_1}$ and $\mathcal{S}_2$ are different. We also fix a positive number $0 < \delta < 1/3$.

On each day, the balls are given to the children to play. At the end of each day, the custodian collects the balls and put them in one of three bins. The custodian does not care about which ball goes where, but does care to make sure that the total weights in each of the bins is not too large. He does not use a scale and can only approximate the weights by hand. In other words, he ensures that the total weight of the balls in each bin lies in the interval $(0, (1- \delta)/2)$.

The custodian also records six triples at the end of each day, corresponding to the set of balls in each bin and its permutations. In other words he records the triple

$$\displaystyle \left(\mathcal{S}_1^{(k)}, \mathcal{S}_2^{(k)}, \mathcal{S}_3^{(k)} \right)$$

as well as its permutations and the end of the $k$-th day.

Out of curiosity, the custodian computes, at the end of each day, the sums

$$\displaystyle \sum_{j=1}^3 \sum_{\sigma \in \mathfrak{S}_3} w \left(\mathcal{S}_j^{(k)} \cap \mathcal{S}_{\sigma(j)}^{(k^\prime)} \right)$$

for $0 \leq k^\prime \leq k$, $\mathfrak{S}_3$ is the symmetric group on three letters, and for a subset $\mathcal{B}$ of $\mathcal{S}$ we have

$$\displaystyle w(\mathcal{B}) = \sum_{b \in \mathcal{B}} b.$$

Let $m(\mathcal{S}, \delta)$ be the smallest positive integer $k$ such that

$$\displaystyle \max_{0 \leq k^\prime \leq k} \sum_{j=1}^3 \sum_{\sigma \in \mathfrak{S}_3} w \left(\mathcal{S}_j^{(k)} \cap \mathcal{S}_{\sigma(j)}^{(k^\prime)} \right) \geq 1 - \delta.$$

Is there a good estimate for $m(\mathcal{S}, \delta)$ in terms of $n = |\mathcal{S}|$ and $\delta$ only?

Answer 1

There is nothing in the problem statement to rule out $b_1=\frac23$ So $b_1>\frac{1-\delta}2.$

Also, maybe you want to say $0<k'<k.$ No harm in having a day $0$ after which the balls are collected. But no reason to. And wouldn't the allowed choice of $k'=k$ make $\displaystyle \sum_{j=1}^3 \sum_{\sigma \in \mathfrak{S}_3} w \left(\mathcal{S}_j^{(k)} \cap \mathcal{S}_{\sigma(j)}^{(k^\prime)} \right)=2?$

I think you could craft things so that the bin weights are always the same so $m=1$ or maybe $2?$ But maybe you want an upper bound valid for all (reasonable) $ \mathcal{S}$ of size $n?$

Take $\delta=\frac19-\frac{1}{10n}$ so $$\frac{1-\delta}2=\frac49+\frac{1}{20n}$$ Temporarily assign $b_1=b_2=\frac49$ (the heavy balls)and $b_i=\frac{1}{9(n-2)}$ for $i>2$ (the light balls). This does not meet your condition of $2^n$ distinct subset sums. But each heavy ball would need to be alone in its own bin, the addition of light ball would make the weight too high.

Now perturb all the weights by amounts less that $\frac{1}{n^2}$ to secure the $2^n$ distinct sums condition. This does not change the fact that every day the bin weights are $b_1,b_2,1-(b_1+b_2).$

There was nothing special about $\frac19.$