200 Delegates and a Conference Hall

200 delegates attend a conference is held in a hall. The hall has 7 doors, marked A , B , , G A,B,\ldots, G . At each door, an entry book is kept, and the delegates entering through that door sign it in the order in which they enter. If each delegate is free to enter any time and through any door he likes, how many different sets of seven lists could arise in all?

If the answer can be expressed an n P k ^nP_k for some positive integers n , k n,k , find (the minimium value of) n + k n+k .

Details and Assumptions :

  • Assume that every person signs only at his first entry.
  • n P k = n ! ( n k ) ! \large ^nP_k=\dfrac{n!}{(n-k)!} .


The answer is 406.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Mark Hennings
Apr 4, 2016

Suppose that D D delegates go through d d doors. Consider the numbers 1 , 2 , 3 , , D 1,2,3,\ldots,D and d 1 d-1 copies of 0 0 . Since the d 1 d-1 copies of 0 0 are indistinguishable, there are ( D + d 1 ) ! ( d 1 ) ! = D + d 1 P D \frac{(D+d-1)!}{(d-1)!} \; =\; {}^{D+d-1}P_D ways in which these symbols can be ordered.

The list of numbers before the first 0 0 is the list of delegates through the first door (in order). The list of numbers between the first 0 0 and the second 0 0 is the list of delegates through the second door (in order), and so on. Thus D + d 1 P D {}^{D+d-1}P_D is the number of possible sets of signing-in lists.

In the case that D = 200 D=200 and d = 7 d=7 , the number of signing-in lists is 206 P 200 {}^{206}P_{200} , making the answer 406 \boxed{406} .

A very easy solution to understand. Upvoted(+1)

Shanthanu Rai - 5 years, 2 months ago
Shanthanu Rai
Apr 2, 2016

Let a,b,c,d,e,f,g be the number of persons entering through the A,B,C,D,E,F,G respectively.
Then,
a+b+c+d+e+f+g=200
Therefore number of ways of dividing 200 into 7 parts = 7 + 200 1 C 200 ^{7+200-1} C _{200} = 206 C 200 ^{206}C_{200} = 206 C 6 ^{206}C_6
The total number of ways of dividing 200 persons into 7 sets containing a,b,c,d,e,f,g persons repectively = 200 ! a ! b ! c ! d ! e ! f ! g ! \frac{200!}{a!b!c!d!e!f!g!}
But the persons in the set of door A can be arranged in a ! a! ways. Same holds for the other sets.
So, total number of ways of dividing 200 persons into 7 sets = 200 ! a ! b ! c ! d ! e ! f ! g ! × a ! b ! c ! d ! e ! f ! g ! \frac{200!}{a!b!c!d!e!f!g!} \times a!b!c!d!e!f!g! = 200 ! 200!
\therefore Required number = 206 C 200 × 200 ! ^{206}C_{200} \times 200! = 206 P 200 \boxed{^{206}P_{200}}



There is a one line solution to this problem.

Hint: Modify the stars and bars approach to permutations.

Calvin Lin Staff - 5 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...