2
$\begingroup$

A university is determining the dates for tests in January. There can be a test on every day in January(all $31 $of them), but each two tests have to have at least $2$ free days in between them. (so if there was a test on Monday, the next one can be on Thursday or later)

How many ways are there to arrange tests in this manner?

I'm guessing inclusion-exclusion would be a way to solve this, but I'm not really sure how to put it because everything I've wanted to do seems to overcount things. Maybe it could be seen as a multiset and look for specific permutations but I'm really not sure.

I would really appreciate any hints whatsoever.

$\endgroup$
2
$\begingroup$

You want to see in how many ways you can arrange $6$ letters T ("test") and $25$ letters F ("free day") in a row so that there are at least two letters F between each two letters T?

To solve this, extract those (five) pairs of letters F between T's, and you get to arrange, freely, $6$ letters T and $15$ letters F in the row. This can be done in $\binom{21}{6}$ ways.

Example:

$$FFTFFFFFTFFFTFFFFFFTFFTFFFFFFTF$$

(exam on Jan 3rd, 9th, 13th, 20th, 23th 30th) maps into the sequence:

$$FFTFFFTFTFFFFTTFFFFTF$$

and vice versa.

$\endgroup$
  • $\begingroup$ Thanks a lot for the idea! Nice solution! I came up with another way once I saw this. This is gonna be helpful with some other problems too, good job!! :) $\endgroup$ – Collapse Feb 1 '18 at 18:56
0
$\begingroup$

You could have used star and bars method too. Let $x_i$ ($2\le i \le 6$) represent the number of free days between two tests while $x_1$ and $x_7$ represent the number of free days before and after the last test. Hence we have $x_i\ge 2$ ($2\le i \le 6$) Hence by star and bars method we have to find non negative integral solutions of $$x_1+x_2+x_3+x_4+x_5+x_6+x_7= 15$$

Hence the answer would simply be $\binom {21}{6}$

$\endgroup$
0
$\begingroup$

Misunderstood Question

Before, I noticed that the title specified $6$ test, I computed all the possible test days.

Use atoms of $\left(x+x^3\right)$ representing a free day, $x$, or a test and two free days, $x^3$.

We also need to note that we can end in two or more free days, $1$, or one free day, $x^2$, or no free days, $x$, represented by $1+x+x^2$

This can be counted by the coefficient of $x^{31}$ in $$ (1+x+x^2)\sum_{k=0}^\infty\left(x+x^3\right)^k =\frac{1+x+x^2}{1-x-x^3} $$ which is $183916$.


Another way to count is to add up the number of ways to have $k$ tests. $$ \begin{align} &\sum_{k=0}^{11}\left[\vphantom{\binom{31}{k}}\right.\overbrace{\binom{31-2k}{k}}^{\substack{\text{ending in $2$ or}\\\text{more days off}}}+\overbrace{\binom{32-2k}{k-1}}^{\substack{\text{ending in $0$}\\\text{days off}}}+\overbrace{\binom{31-2k}{k-1}}^{\substack{\text{ending in $1$}\\\text{days off}}}\left.\vphantom{\binom{31}{k}}\right]\\ &=\sum_{k=0}^{11}\binom{33-2k}{k} \end{align} $$ which is also $183916$.


Six Test Month

Once I notice the $6$ test days, all the question really needed was the second approach above, using only the $k=6$ term. That gives, as other answers say $$ \binom{21}{6}=54264 $$


Another Approach

Similar to the first answer to the misunderstood question above, arrange $6$ "test and two free" days and $31-6\cdot3=13$ "free days". To handle the problem a test cannot happen on the last day or the day before the last day, we add $2$ "free days" to January and ignore them at the end. Thus, we arrange $6$ "test and two free" and $15$ "free days" giving a total number of ways of $$ \binom{15+6}{6}=\binom{21}{6}=54264 $$

$\endgroup$

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.