0
$\begingroup$

Let $S$ be a set of $N$ balls $\{b_1, \cdots, b_N\}$, each with weight $w(b_j), j = 1, \cdots, N$. For a subset $A \subseteq S$, define

$$\displaystyle W(A) = \sum_{a \in A} w(a).$$

Initially, $S$ is partitioned into two bins $A_0 \cup B_0 = S_0 = S$ (with $A_0 \cap B_0 = \emptyset$) such that the weights $W(A) = W(B)(1 + \kappa_0)$, where $\kappa_0$ may be interpreted as an arbitrarily small quantity. Without loss of generality, we assume that $W(B_0) \geq W(A_0)$.

At each step $k \geq 1$, we shuffle $S$ and put them into new bins forming the partition $S = A_k \cup B_k$, with $W(B_k) \geq W(A_k)$ and subject to $W(B_k) = W(A_k)(1 + \kappa_k)$, where $\kappa_k$ can be assumed to be bounded by some function of $W(S)$ which goes to zero as $W(S) \rightarrow \infty$.

Does there exist an absolute constant $c$, independent of any of the parameters above, such that there exist two indices $i < j \leq c$ satisfying $W(B_i \cap B_j) \geq \frac{1}{4} W(S)$?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ You want $c$ to be independent of $N$? $\endgroup$
    – Sam Hopkins
    Commented Nov 22, 2023 at 20:34
  • 2
    $\begingroup$ This question (without a restriction on $N$) seems equivalent to a well-known problem about whether there is an infinite sequence of subsets $E_i$ of $[0,1]$ such that $|E_i|\ge \frac 12$ but $|E_i\cap E_j|<\frac 14$ for all $i\ne j$. Such a sequence does exist though you cannot replace $\frac 14$ by any smaller number here. $\endgroup$
    – fedja
    Commented Nov 22, 2023 at 23:34
  • $\begingroup$ @fedja could you provide a reference or give a more precise statement? If so, I would gladly accept the answer, thank you! $\endgroup$
    – Stanley Yao Xiao
    Commented Nov 23, 2023 at 0:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .