-1
$\begingroup$

Given the set $X=\{1,2,\ldots,n\}$; $\,\,$ $n=mp=kq$ where $m,k,p,q$ are positive integers.

Please help me to programme an algorithm that realizes random generation of the following two partitions of $X$: $$ \mathcal{D}_{1} = \big\{A_{i}\big\}_{i=1}^{p}; \quad \bigcup_{i=1}^{p} A_{i} = X; \quad A_{i_{1}} \cap A_{i_{2}} = \emptyset \quad (i_{1} \neq i_{2}); \quad |A_{i}|=m, \quad i=\overline{1,p} $$ and $$ \mathcal{D}_{2} = \big\{B_{j}\big\}_{j=1}^{q}; \quad \bigcup_{j=1}^{q} B_{j} = X; \quad B_{j_{1}} \cap B_{j_{2}} = \emptyset \quad (j_{1} \neq j_{2}); \quad |B_{j}|=k, \quad j=\overline{1,q} $$ such that $$ A_{i} \cap B_{j} = \emptyset, \quad i=\overline{1,p}, \quad j=\overline{1,q}. $$

Here, as usual, $|S|$ denotes the number of elements of the set $S$.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We expect you to make a serious effort on your own and to show us in the question what you tried, where you got stuck, and formulate a more specific question about your problem. We can't help you unless you show us what you've tried and where you got stuck. This is not a "problem-solving-outsourcing" site, where you copy-paste your exercise problem and we solve it for you. $\endgroup$ – D.W. Nov 8 '14 at 1:15
1
$\begingroup$

There do not exist such partitions $D_1$ and $D_2$. Recall your assumptions: $$\bigcup\limits_{i=1}^{p} A_i=X,\;\bigcup\limits_{i=1}^{q} B_i=X$$ It follows, that for each $x\in X$ there exists a set $A_k$ $(k\in\{1,...,p\})$ and a set $B_j$ $(j\in\{1,...,p\})$ such that $x\in A_k$ and $x\in B_j$. Therefore $x\in (B_j\cap A_k)$ which contradicts that $B_j\cap A_k=\emptyset $.

$\endgroup$

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