Selecting Four Courses
A university is designing a minor and must choose exactly four of seven proposed courses: P, Q, R, S, T, U and V. The rules are: if P is chosen, Q must also be chosen; R and S cannot both be chosen; at least one of T and U must be chosen; and if V is chosen, R must be chosen. The committee wants to know whether any course is unavoidable, how many valid combinations include V, and how many include exactly one of P and Q.
1. Is any of the seven courses required in every valid selection? Justify your answer.
Read the worked answer
No course is forced. To prove this, each course can be omitted by at least one valid selection:
P omitted: {Q, R, T, U}; Q omitted: {R, T, U, V}; R omitted: {P, Q, S, T}; S omitted: {P, Q, R, U}; T omitted: {P, Q, R, U} (U satisfies the T-or-U rule); U omitted: {P, Q, R, T}; V omitted: {P, Q, R, T}.
Each set has exactly four courses, satisfies P → Q, never contains both R and S, includes T or U, and includes R whenever V is present. Since every course can be absent from some valid selection, none is necessary. The tempting answer is R, because V pulls R in, but R is easily dropped by omitting V.
2. How many valid selections contain V? List them.
Read the worked answer
If V is chosen, R must be chosen. Since R and S cannot coexist, S is excluded. Two places remain, so the selection is V, R plus two of P, Q, T and U.
Choosing two from {P, Q, T, U} gives six pairs, but P without Q is forbidden. The pair {P, T} fails, and so does {P, U}; {P, Q} is allowed.
Valid pairs: {P, Q}, {Q, T}, {Q, U}, {T, U}. That gives four valid selections:
- {V, R, P, Q}
- {V, R, Q, T}
- {V, R, Q, U}
- {V, R, T, U}
The T-or-U rule is automatically satisfied in all four because each contains T or U.
3. How many valid selections contain exactly one of P and Q?
Read the worked answer
If P is chosen, Q must be chosen, so 'exactly one' forces Q to be chosen and P to be excluded.
So the selection is Q plus three courses from {R, S, T, U, V}, subject to R and S not both appearing and V requiring R.
Enumerate the valid triples:
- {R, T, U} - valid
- {R, T, V} - valid, since V has R
- {R, U, V} - valid
- {S, T, U} - valid, since no R
Triples containing both R and S fail, and triples with V but no R fail. Adding Q gives four selections: {Q, R, T, U}, {Q, R, T, V}, {Q, R, U, V}, {Q, S, T, U}.
Answer: four.