Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
$1$? If person $i$ selects object $i$, we are done. Or are you realting to the birthday problem? –  AlexR Sep 12 '13 at 12:41
    
@AlexR nopes! i have reframed the question .have a look.! –  TSP1993 Sep 12 '13 at 12:52
    
Still, this is much closer to probability, than to combinatorics. –  AlexR Sep 12 '13 at 12:56
    
@AlexR any idea how to solve this? –  TSP1993 Sep 12 '13 at 13:00
    
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. –  Gerry Myerson Sep 12 '13 at 13:04
show 6 more comments

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
    
so how to solve this ? –  TSP1993 Sep 12 '13 at 14:12
    
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. –  AlexR Sep 12 '13 at 21:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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