1
$\begingroup$

Fifteen students are sitting around a large circular table for a study session. The teacher has made only six copies of the review guide. No student should get more than one copy of the review guide and any student who does not get one should be able to read a neighbor’s copy. If the students are distinguishable, but the review guides are identical, how many ways are there to distribute the six review guides to the fifteen students subject to these conditions?

First I would find ways to arrange the fifteen students so

$(15-1)! = 14!$

Then to arrange the $6$ copies of the review guide, I would use combination so

$15~C~6 = 5005$

But when I multiply these $2$ numbers, I get a huge number.

Do I even need to arrange the fifteen students, or is the answer just $5005$ or is it wrong altogether?

$\endgroup$
  • 1
    $\begingroup$ Two things: 1) I assume (only assume) that the question considers the students already seated - so no arranging the students - and you are only supposed to hand out the copies. 2) $15 C 6$ would be how many ways there are to give out the copies if no student should get more than one. However, here it might be that there are students for which the neighbors on both sides did not get a copy, that would be a problem... $\endgroup$ – Dirk Apr 13 '17 at 7:03
  • $\begingroup$ Can you calculate the combination of consequent 3 or more students that have no copy? because 3 students without a copy will lead to a state that middle student can read none. then You'll have the combinations which every student gets to read a copy I guess. $\endgroup$ – Taha Paksu Apr 13 '17 at 7:08
  • $\begingroup$ The combination of 3 students not having a copy 3C0 plus the combination of 4 not having plus combination of 5 plus combination of 6? $\endgroup$ – s_healy Apr 13 '17 at 7:14
  • $\begingroup$ Yes that's what I've meant. Isn't that a reasonable solution? BTW that was my first comment on this site :) $\endgroup$ – Taha Paksu Apr 13 '17 at 7:24
  • 1
    $\begingroup$ Instead of thinking about where the copies go, think about the gaps between them. There are six gaps, consisting of a total of 9 students, and each gap can only be 0, 1, or 2 students. In how many ways can the gaps be arranged? $\endgroup$ – Jaap Scherphuis Apr 13 '17 at 8:52
0
$\begingroup$

Let the students seat themselves at wish. This can be done in $15!$ ways, resp., in $14!$ ways up to rotations, or in ${1\over2}\cdot14!$ ways up to rotations and reflections.

We now have to distribute the booklets. At the end $6$ students will hold a booklet. In between them there are six slots containing $0$, $1$, or $2$ students each. Denote by $x_i\geq0$ the number of slots containing $i$ students. Then $$x_0+x_1+x_2=6,\qquad x_1+2x_2=9\ ,$$ hence $$x_1=3-2x_0,\qquad x_2=3+x_0\ .$$ It follows that $x_0\in\{0,1\}$, so that we obtainthe two admissible solutions $${\rm (a)}\quad (1,1,4),\qquad{\rm (b)}\quad(0,3,3)\ .$$

(a) As $x_0=1$ there are two adjacent students receiving a booklet. We can choose these in $15$ ways and then the "unary" slot in $5$ ways, makes $75$.

(b) In order to count the possible arrangements assume that one of the booklets is marked. The marked booklet can be handed out to any of the $15$ students, so that a chain of $14$ students is generated. $5$ among these will get an "ordinary" booklet. The arrangement of slot-sizes between all booklet holders can be encoded as a word of length $6$ over the alphabet $\{1,2\}$, like so: $221121$. There are ${6\choose3}=20$ such words containing $3$ ones and $3$ twos. Makes ${15\cdot20\over6}=50$ possibilities, the factor $6$ in the denominator coming from the overcounting caused by marking a booklet.

It follows that the booklets can be distributed in $75+50=125$ admissible ways to the $15$ students already sitting around the table..

$\endgroup$
  • $\begingroup$ It turns out that you do have to arrange the students so would you just multiply final answer by 14! because 15-1 due due to the round table. Also for A why couldn't i just do 6! / 4!1!1! for a case with 4 2 people gap, 1 one person gap and a zero person gap 222210 $\endgroup$ – s_healy Apr 19 '17 at 21:25
  • $\begingroup$ Your $6!/4!$ count is not suited for a round table. What if the transition seat 15/seat 1 is in the midst of a two person gap? $\endgroup$ – Christian Blatter Apr 20 '17 at 8:02
  • $\begingroup$ Ok I understand and is the multiplication of 15 necessary in (a) and (b) iif we multiply the whole thing by 14! $\endgroup$ – s_healy Apr 21 '17 at 0:57
  • $\begingroup$ After the students have taken seats we are talking about a cyclic graph with labeled vertices. This means that translating all booklets one seat to the right creates a new arrangement. $\endgroup$ – Christian Blatter Apr 22 '17 at 18:15

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.