-1
$\begingroup$

Suppose there are $n$ bins each having $k$ objects. Assume that capacity of each bin is also $k$. Now we want to rearrange the objects such that each bin contains $k$ objects but this time if $x,y$ belong to the same bin, then $x,y$ were in different bins in the original arrangement.

Questions:

  1. Does there always exist such a rearrangements? why ?

  2. What is the official name of this problem in the literature ?

Any link/hint would be helpful.

$\endgroup$
4
  • $\begingroup$ When bins capacity is one the counting version of the problem known as derangement. But I think your problem is better suited at math.se. $\endgroup$
    – Saeed
    Sep 10 '14 at 18:17
  • $\begingroup$ @Saeed I dont think a derangement is the $k=1$ case. In fact the in the $k=1$ case any arrangement is vacuously admitted. The requirement is not that all items change bins, but that if two items share a bin in the new arrangement, they must have not shared a bin in the initial arrangement. $\endgroup$ Sep 11 '14 at 6:03
  • $\begingroup$ @SashoNikolov, I read it in the way that, they are not allowed to be in their original bin and also they are not allowed to be in same bin as their initial bin. $\endgroup$
    – Saeed
    Sep 11 '14 at 8:34
  • $\begingroup$ @SashoNikolov is correct, when k=1, then any permutation is valid $\endgroup$
    – Dibyayan
    Sep 11 '14 at 8:41
2
$\begingroup$

Maybe I miss something, but it looks obvious that if $k<=n$ then you can rearrange the objects in the simplest way. Number the objects of each bin from 0 to k-1 and move object i to the i'th next bin.

Before:
bin A: {A0, A1, A2}
bin B: {B0, B1, B2}
bin C: {C0, C1, C2}
bin D: {D0, D1, D2}

After:
bin A: {A0, D1, C2}
bin B: {B0, A1, D2}
bin C: {C0, B1, A2}
bin D: {D0, C1, B2}

$\endgroup$
2
$\begingroup$

Question 1: No

counterexample: bin 1 = $[1,2,3]$, bin 2 = $[4,5,6]$

$\endgroup$
1
  • $\begingroup$ What if we put the restriction of k<n ? $\endgroup$
    – Dibyayan
    Sep 11 '14 at 2:24

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.