0
$\begingroup$

Suppose we have $n$ differnt persons and $n$ different objects.They have to select from the the objects such that every pair of person has at least one uncommon object.
What is the minimum number of objects that they should select?
EDIT
Its also given that every person can select as many objects as he wants.
But every pair should have at least one uncommon object each.
So find the total minimum number of objects that they should select out of n. CLARIFICATION
For ever pair of person $A$ and $B$, $A$ must have an object that $B$ doesn't have and $B$ must have an object that $A$ doesnt have.
EXAMPLE
For $n=5$ there are $5$ persons $\{A,B,C,D,E\}$ and objects numbered $\{1,2,3,4,5\}$.
The min. number of objects they should select is $4$.
$$\begin{align*} A: & (3,1)\\ B: & (3,2)\\ C: & (3,4)\\ D: & (4,1)\\ E: & (1,2) \end{align*}$$ This is one possible combination, but the minimum total is $4$ elements.

$\endgroup$
  • $\begingroup$ $1$? If person $i$ selects object $i$, we are done. Or are you realting to the birthday problem? $\endgroup$ – AlexR Sep 12 '13 at 12:41
  • $\begingroup$ @AlexR nopes! i have reframed the question .have a look.! $\endgroup$ – TSP1993 Sep 12 '13 at 12:52
  • $\begingroup$ Still, this is much closer to probability, than to combinatorics. $\endgroup$ – AlexR Sep 12 '13 at 12:56
  • $\begingroup$ @AlexR any idea how to solve this? $\endgroup$ – TSP1993 Sep 12 '13 at 13:00
  • $\begingroup$ I don't see what's wrong with the original comment by @Alex. If person $i$ selects object $i$, then each person in a pair has an object the other person in the pair doesn't have. Clarification needed. $\endgroup$ – Gerry Myerson Sep 12 '13 at 13:04
0
$\begingroup$

In OP's example, there could be person $F$ with objects 2 and 4. So there are ${4\choose 2}$ people choosing two from four objects.

Suppose there are $N$ objects, and everyone chooses $k$ objects.

To answer the opposite question from the OP, what is the maximum number of people that can choose from $N$ objects, it would be ${N\choose\lfloor N/2 \rfloor}$ people.

$\endgroup$
0
$\begingroup$

Reformulating the question to match the example (OP: copy this if it's correct)

For a number of $n$ persons, who pick a number of Objects $A_i \subset \Omega$.
What is the minimum number of elements of $\Omega$, such that the persons can pick objects fulfilling the following condition? $$A_i \setminus A_j \neq \emptyset \qquad \forall\ i \neq j \in \{1, \ldots, n\}$$


Ansatz based on Michaels' observations

Let $N$ be even, so we don't have to worry about $\lfloor \cdot \rfloor$. Then we want $$\begin{align*}n \lesssim \binom{N}{N/2} & = \frac{N(N-1)(N-2) \ldots (N/2)}{(N/2)(N/2 - 1) \ldots} \\ & = \prod_{k=0}^{N/2-1} \frac{N-k}{N/2 - k} = 2^{N/2} \prod_{k=1}^{N/2-1} \frac{N-k}{N-2k} \\ & = 2^{N/2} \prod_{k=1}^{N/2 - 1} \left(1 + \frac{k}{N-2k}\right) \end{align*}$$ Where $\lesssim$ denotes, that $N$ should be chosen such, that $N-1$ doesn't fulfill the $<$ restriction, but $N$ does.

$\endgroup$
  • $\begingroup$ so how to solve this ? $\endgroup$ – TSP1993 Sep 12 '13 at 14:12
  • $\begingroup$ Edited to put a little thought into it. We need to find a good representation of the product. Either by recursion, or by explicit evaluation. $\endgroup$ – AlexR Sep 12 '13 at 21:16

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.