1
$\begingroup$

I had a discrete maths test today and this question was the last one and it really threw me off.

During a 13 week semester ( no breaks in between ), a student must sit 3 exams >for a particular course. However, he must sit them in order, i.e 1st -> 2nd -> 3rd. In other words, you must first sit the 1st exam, then the 2nd then the 3rd. so can't sit the second exam without having sat the 1st one, etc..

If he can only sit one exam per week, in how many ways can the student sit the exams.

I tried during inclusion/exclusion principle but it got messy real quick. I also thought of doing the lines and dots method but figured it's wrong since the dots are not identical.

I'm just curious how to do this.

the second part of the question was

Suppose they are not allowed to sit two exams in consecutive weeks, now in how >many ways can the student sit the exams.

I didn't even attempt the second part as I did not have time.

Any help would be greatly appreciated.

$\endgroup$
  • $\begingroup$ What do you mean by "sit an exam"? Do you mean write an exam? And what do you mean by sitting/writing them in order? $\endgroup$ – Daniel P May 21 '18 at 10:42
  • $\begingroup$ Think of it this way: let $x_1$ is the week number of the first exam, $x_2$ is the number of weeks between the first and second exam, and $x_3$ is the number of weeks between the second and third exam. Then you get a restriction $$ x_1 + x_2 + x_3 = 13 $$ How many integer solutions are there to this equation? $\endgroup$ – Matti P. May 21 '18 at 10:43
  • $\begingroup$ @DanielP yea sit an exam as in write/take or whatever you want to call it. and in order so 1st one must be sat/taken before 2nd, and 2nd before 3rd $\endgroup$ – Billi May 21 '18 at 10:44
  • $\begingroup$ @MattiP. but does this ensure that the 1st exam is always sat before the 2nd, and 2nd before third? plus i don't think that equation is quite right. isn't it more like: x1 + x2 + x3 + .... + x13 = 3? with x1-13 at most 1? $\endgroup$ – Billi May 21 '18 at 10:47
  • $\begingroup$ It seems to me that the first question is asking in how many ways can the student select three of the thirteen weeks in the semester in which to sit an exam? Do you know how to answer that question? $\endgroup$ – N. F. Taussig May 21 '18 at 10:47
0
$\begingroup$

During a $13$-week semester, a student must sit $3$ exams for a particular course. However, he must sit them in order (the first exam must precede the second and the second must precede the third). If he can only sit one exam per week, in how many ways can he sit the exams?

Method 1: Since he must sit the exams in order, his examination schedule is completely determined by choosing during which three of the thirteen weeks he schedules an exam. Hence, there are $$\binom{13}{3}$$ ways for the student to schedule his exams.

Method 2: This method is less efficient, but I am adding it to address the questions raised in the comments.

Suppose the student takes the $k$th examination in week $a_k$. Define \begin{align*} x_1 & = a_1\\ x_2 & = a_2 - a_1\\ x_3 & = a_3 - a_2\\ x_4 & = 13 - x_3 \end{align*} Then $$x_1 + x_2 + x_3 + x_4 = 13 \tag{1}$$ Observe that $x_1$ is a positive integer. Since the student cannot sit two examinations in the same week and the exams must be sat in order $x_2$ and $x_3$ are also positive integers. Since the student can sit an examination in the last week, $x_4$ is a nonnegative integer.

We can transform equation 1 into an equation in the positive integers by setting $x_4' = x_4 + 1$. Substituting $x_4' - 1$ for $x_4$ in equation 1 yields \begin{align*} x_1 + x_2 + x_3 + x_4' - 1 & = 13\\ x_1 + x_2 + x_3 + x_4' & = 14 \tag{2} \end{align*} Equation 2 is an equation in the positive integers that is equivalent to equation 1. A particular solution of equation 2 corresponds to the placement of three addition signs in the $13$ spaces between successive ones in a row of $14$ ones. $$1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1\square 1 \square 1 \square 1 \square 1 \square 1 \square 1$$ For instance, choosing the third, seventh, and thirteenth spaces yields $$1 1 1 + 1 1 1 1 + 1 1 1 1 1 1 + 1$$ which corresponds to the solution $x_1 = 3$, $x_2 = 4$, $x_3 = 6$, $x_4' = 1$ ($x_4 = 0$) or $a_1 = 3$, $a_2 = 7$, $a_3 = 13$. The number of such solutions is the number of ways we can select three of the thirteen spaces between successive ones in a row of fourteen ones in which to place an addition sign, which is $$\binom{13}{3}$$

Suppose a student cannot sit an exam in consecutive weeks. In how many ways can the student sit the exams?

We arrange ten blue balls and three green balls so that no two of the green balls are consecutive.

Line up ten blue balls in a row. This creates eleven spaces, nine between successive blue balls and two at the ends of the row. $$\square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square$$ To ensure that the three green balls are separated, choose three of these eleven spaces for the green balls. For instance, if we choose the third, sixth, and eleventh spaces, we obtain $$\color{blue}{\bullet} \color{blue}{\bullet} \color{green}{\bullet} \color{blue}{\bullet} \color{blue}{\bullet} \color{blue}{\bullet} \color{green}{\bullet} \color{blue}{\bullet} \color{blue}{\bullet} \color{blue}{\bullet} \color{blue}{\bullet} \color{blue}{\bullet} \color{green}{\bullet}$$ Now number the balls from left to right. The numbers on the green balls are the examination weeks. In this case, they are $a_1 = 3$, $a_2 = 7$, and $a_3 = 13$. The number of such solutions is the number of ways we can select three of these eleven spaces in which to insert a green ball. Hence, there are $$\binom{11}{3}$$ ways to schedule the exams so that the student does not sit exams in consecutive weeks.

$\endgroup$
3
$\begingroup$

(Edited the answer to fit all criterias.)

Choose the 3 weeks out of 13 on which the student writes the exam. On the first chosen week the first exam, the second chosen week the second exam, third week the third.

There is a known mathematical formula for choosing $k$ instances from $n$, which is calculated by $${n\choose k} = \frac{n!}{k!(n-k)!}$$ Note that this already fits the criteria of writing the exams in order. It just selects $3$ weeks out of $13$, and on the $n^{th}$ selected week ($n \in \{1,2,3\}$) you write the $n^{th}$ exam.

In this case: $${13\choose 3} = \frac{13!}{3!(13-3)!} = 268$$

However, if you need to have at least $1$ week off before you write the next exam, you really only have $11$ objects to order (instead of $13$):

  • (First exam's week + a week off)
  • (Second exam's week + a week off)
  • (Third exam's week)
  • (Other exam free weeks)$\times 8$

You need to choose $3$ places out of $11$ to fit these weeks (or double weeks) into the semester, so the answer is: $${11\choose 3} = \frac{11!}{3!(11-3)!} = 165.$$

$\endgroup$
  • $\begingroup$ A minor error: There are $8$ other exam free weeks since $13 - 2 - 2 - 1 = 8$. With that change, you will have $11$ objects: the first exam week and week off, the second exam week and week off, the third exam week, and the other eight weeks. $\endgroup$ – N. F. Taussig May 21 '18 at 11:08
  • $\begingroup$ Thanks, I corrected it. $\endgroup$ – Daniel P May 21 '18 at 11:12

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.