6
$\begingroup$

This may be a question with a well known answer, but I've been thinking on it for two days, and can't quite come up with a satisfactory answer.

Consider the problem of dividing $p n$ bins numbered $1$ through $pn$ into $p m + 1$ segments by placing $pm$ balls. If we let $k = pn - pm \bmod pm+1$, then we can show that we may attain a placement of the $pm$ balls such that there are exactly $(pm+1) - k$ segments of empty bins of length $\lfloor \frac{pn-pm}{pm+1} \rfloor$ and $k$ segments of empty bins of length $\lceil \frac{pn-pm}{pm + 1} \rceil$.

Here's the tricky question: can we accomplish this task while ensuring that there are exactly $m$ balls in each interval $[(j-1)n + 1, jn]$, for $j \in \{1, 2, \dots, p\}$?

Every concrete example I work through answers in the affirmative, but I can't seem to get an algorithmic way of doing it, or mathematical proof that one such arrangement exists.

For particular examples, it always seems to work. See an example below with $p = 2,$ $n = 7,$ $m = 2.$

1| |X| | |X|1|X| | |X| | |

where 1 denotes the beginning of a new 'period', and | denotes the 'wall' of a bin, and X denotes a ball. Note that 1 and | both denote 'walls' of bins.

$\endgroup$
4
  • $\begingroup$ Your example is actually not regular. You want ||X|||X|||X|||X||. $\endgroup$ Mar 25 '16 at 0:34
  • $\begingroup$ Not sure I agree with that; my example has $pn = 14$ bins, with $7$ in each period. Yours appears to only have $12$ bins? $\endgroup$
    – notwatson
    Mar 31 '16 at 14:08
  • $\begingroup$ I count 14. Are you counting the extreme ones? $\endgroup$ Mar 31 '16 at 18:35
  • $\begingroup$ Ah, no I was not. I only counted bins as spaces with lines on either side. So, I missed the two most extreme bins in your example. Thanks! $\endgroup$
    – notwatson
    Apr 5 '16 at 18:09
2
$\begingroup$

For $0 \leq i \leq pm+1$, define $$ x_i = \left\lfloor i \frac{pn+1}{pm+1} \right\rfloor. $$ We put ball $i$ in bin $i$ for $1 \leq i \leq pm$. The length of the $i$th space (for $1 \leq i \leq pm+1$) is $$ x_i - x_{i-1} = \left\lfloor i \frac{pn+1}{pm+1} \right\rfloor - \left\lfloor (i-1) \frac{pn+1}{pm+1} \right\rfloor \in \left\{ \left\lfloor \frac{pn+1}{pm+1} \right\rfloor, \left\lceil \frac{pn+1}{pm+1} \right\rceil \right\}, $$ so your first condition is satisfied (the spaces are as equal to each other as possible).

For your second condition, we need to verify that $1 \leq x_1,\ldots,x_m \leq n$, $n+1 \leq x_{m+1},\ldots,x_{2m} \leq 2n$, and so on. It's clearly enough to verify that $x_{Cm} \leq Cn$ for $1 \leq C \leq p$ and that $x_{Cm+1} > Cn$ for $0 \leq C < p$. For the first condition, we have $$ x_{Cm} = \left\lfloor Cm \frac{pn+1}{pm+1} \right\rfloor < Cm \frac{pn+1}{pm+1} + 1 = \frac{Cpmn + Cm + pm + 1}{pm+1} \\ < \frac{Cpmn + Cn + pm + 1}{pm+1} = Cn+1, $$ using your implicit assumption $m < n$. For the second condition, $$ x_{Cm+1} = \left\lfloor (Cm+1) \frac{pn+1}{pm+1} \right\rfloor \geq (Cm+1) \frac{pn+1}{pm+1} = \frac{Cpmn + Cm + pn + 1}{pm+1} \\ \geq \frac{Cpmn + Cn + pm + 1}{pm+1} = Cn+1, $$ using $Cm + pn \geq Cn + pm$, which follows from $(p-C)(n-m) \geq 0$.

$\endgroup$
1
  • $\begingroup$ Looks as if you're on track to hit 100K rep before long; see here. Congratulations! Wish I could see it happen, but I'm for bed. $\endgroup$ Mar 25 '16 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.