What this discrete math set covers
Logic and proof methods
Build converses and contrapositives, and choose between direct proof, contraposition, contradiction, and induction.
Sets, relations, and functions
Use inclusion-exclusion on set sizes, and count or classify functions as injective, surjective, or bijective.
Counting and recurrences
Choose between permutations and combinations, and unroll a recurrence relation term by term to find a later value.
Graphs and number theory
Apply the handshake lemma and connectivity rules, and use the Euclidean algorithm for gcd, lcm, and modular arithmetic.
Choose the right pressure
100 worked discrete math questions
Attempt each question before opening the reasoning. Every item belongs to the same original library used by the workspace above.
Question 1: What is the contrapositive of: If a graph is a tree, then it is connected?
Skill: logic · Level: Build
- If a graph is not connected, then it is not a tree.
- If a graph is connected, then it is a tree.
- If a graph is not a tree, then it is not connected.
- Every connected graph is a tree.
Show the worked answer
- Write the statement as $P\Rightarrow Q$.
- Its contrapositive is $\neg Q\Rightarrow\neg P$: not connected implies not a tree.
Answer: If a graph is not connected, then it is not a tree.
Question 2: How many subsets does a set with $6$ elements have?
Skill: sets and counting · Level: Build
- 12
- 36
- 64
- 720
Show the worked answer
- There are $2$ choices for each of $6$ elements.
- $2^6=64$ subsets.
Answer: 64
Question 3: How many five-character codes use two distinct letters followed by three distinct digits?
Skill: combinatorics · Level: Apply
- $26\cdot25\cdot10\cdot9\cdot8$
- $26^2\cdot10^3$
- $\binom{26}{2}\binom{10}{3}$
- $52\cdot30$
Show the worked answer
- The letters have $26$ then $25$ choices.
- The digits have $10$, $9$, then $8$ choices; multiply all five counts.
Answer: $26\cdot25\cdot10\cdot9\cdot8$
Question 4: A connected graph has $14$ vertices, each of degree $3$. How many edges does it have?
Skill: graph theory · Level: Apply
- 18
- 21
- 28
- 42
Show the worked answer
- The sum of degrees is $14(3)=42$.
- Each edge contributes twice, so $E=42/2=21$.
Answer: 21
Question 5: How many onto functions exist from a $4$-element set to a $2$-element set?
Skill: functions and inclusion-exclusion · Level: Stretch
- 12
- 14
- 16
- 24
Show the worked answer
- There are $2^4=16$ functions in total.
- Exactly two miss one codomain value, so $16-2=14$ are onto.
Answer: 14
Question 6: A recurrence satisfies $a_n=2a_{n-1}+1$ with $a_1=2$. What is $a_5$?
Skill: recurrence relations · Level: Stretch
- 31
- 47
- 63
- 95
Show the worked answer
- $a_2=5$, $a_3=11$, and $a_4=23$.
- $a_5=2(23)+1=47$.
Answer: 47
Question 7: Sets $A$ and $B$ have $11$ and $10$ elements, with $3$ elements in both. Find $|A\cup B|$.
Skill: sets and inclusion-exclusion · Level: Build
- 18
- 21
- 3
- 24
Show the worked answer
- Add the set sizes: $11+10=21$.
- Subtract the $3$ shared elements: $|A\cup B|=18$.
Answer: 18
Question 8: In how many orders can $4$ distinct books be arranged on a shelf?
Skill: permutations · Level: Apply
- 16
- 12
- 25
- 24
Show the worked answer
- There are $4$ choices, then $3$, continuing to $1$.
- The count is $4!=24$.
Answer: 24
Question 9: How many $3$-person committees can be selected from $7$ people?
Skill: combinations · Level: Stretch
- 343
- 6
- 35
- 21
Show the worked answer
- Use $\binom{7}{3}$.
- The number is $35$.
Answer: 35
Question 10: Let $p$ be false and $q$ be false. What is the truth value of $p\to q$?
Skill: propositional logic · Level: Build
- both true and false
- true
- false
- cannot be determined
Show the worked answer
- Here $p$ is false and $q$ is false.
- Therefore $p\to q$ is true.
Answer: true
Question 11: A graph has vertex degrees $2, 3, 4, 5$. If such a graph exists, how many edges does it have?
Skill: graph theory · Level: Apply
- 7
- 14
- 4
- 9
Show the worked answer
- The degree sum is $14$.
- By the handshake lemma, the edge count is $14/2=7$.
Answer: 7
Question 12: A recurrence is $a_0=3$ and $a_n=a_{n-1}+4$. Find $a_{6}$.
Skill: recurrences · Level: Stretch
- 23
- 7
- 24
- 27
Show the worked answer
- After $6$ steps, the total increase is $6(4)$.
- $a_{6}=3+6(4)=27$.
Answer: 27
Question 13: Find $27\bmod 4$.
Skill: modular arithmetic · Level: Build
- 1
- 7
- 3
- 6
Show the worked answer
- $27=6(4)+3$.
- The remainder is $3$.
Answer: 3
Question 14: Write decimal $8$ in binary.
Skill: number representation · Level: Apply
- 8
- 1000
- 1001
- 111
Show the worked answer
- The powers of two selected by $8$ determine its binary digits.
- The binary representation is $1000_2$.
Answer: 1000
Question 15: Among students, $13$ study logic, $11$ study graphs, and $4$ study both. How many study at least one?
Skill: inclusion-exclusion · Level: Stretch
- 20
- 24
- 4
- 28
Show the worked answer
- $13+11=24$ counts the shared students twice.
- Subtract $4$ to get $20$.
Answer: 20
Question 16: If $11$ objects are placed into $4$ boxes, what minimum number must be in at least one box?
Skill: pigeonhole principle · Level: Build
- 2
- 4
- 5
- 3
Show the worked answer
- $11/4=2.750$.
- Rounding up gives $\lceil 11/4\rceil=3$.
Answer: 3
Question 17: Sets $A$ and $B$ have $12$ and $12$ elements, with $4$ elements in both. Find $|A\cup B|$.
Skill: sets and inclusion-exclusion · Level: Apply
- 4
- 28
- 20
- 24
Show the worked answer
- Add the set sizes: $12+12=24$.
- Subtract the $4$ shared elements: $|A\cup B|=20$.
Answer: 20
Question 18: In how many orders can $5$ distinct books be arranged on a shelf?
Skill: permutations · Level: Stretch
- 32
- 120
- 25
- 20
Show the worked answer
- There are $5$ choices, then $4$, continuing to $1$.
- The count is $5!=120$.
Answer: 120
Question 19: How many $4$-person committees can be selected from $8$ people?
Skill: combinations · Level: Build
- 70
- 32
- 4096
- 24
Show the worked answer
- Use $\binom{8}{4}$.
- The number is $70$.
Answer: 70
Question 20: Let $p$ be true and $q$ be false. What is the truth value of $p\to q$?
Skill: propositional logic · Level: Apply
- true
- cannot be determined
- both true and false
- false
Show the worked answer
- Here $p$ is true and $q$ is false.
- Therefore $p\to q$ is false.
Answer: false
Question 21: A graph has vertex degrees $3, 4, 5, 6$. If such a graph exists, how many edges does it have?
Skill: graph theory · Level: Stretch
- 4
- 11
- 9
- 18
Show the worked answer
- The degree sum is $18$.
- By the handshake lemma, the edge count is $18/2=9$.
Answer: 9
Question 22: A recurrence is $a_0=4$ and $a_n=a_{n-1}+5$. Find $a_{7}$.
Skill: recurrences · Level: Build
- 35
- 39
- 34
- 9
Show the worked answer
- After $7$ steps, the total increase is $7(5)$.
- $a_{7}=4+7(5)=39$.
Answer: 39
Question 23: Find $34\bmod 5$.
Skill: modular arithmetic · Level: Apply
- 4
- 6
- 1
- 9
Show the worked answer
- $34=6(5)+4$.
- The remainder is $4$.
Answer: 4
Question 24: Write decimal $11$ in binary.
Skill: number representation · Level: Stretch
- 1100
- 1010
- 11
- 1011
Show the worked answer
- The powers of two selected by $11$ determine its binary digits.
- The binary representation is $1011_2$.
Answer: 1011
Question 25: Among students, $14$ study logic, $12$ study graphs, and $5$ study both. How many study at least one?
Skill: inclusion-exclusion · Level: Build
- 5
- 31
- 21
- 26
Show the worked answer
- $14+12=26$ counts the shared students twice.
- Subtract $5$ to get $21$.
Answer: 21
Question 26: If $12$ objects are placed into $5$ boxes, what minimum number must be in at least one box?
Skill: pigeonhole principle · Level: Apply
- 4
- 3
- 2
- 5
Show the worked answer
- $12/5=2.400$.
- Rounding up gives $\lceil 12/5\rceil=3$.
Answer: 3
Question 27: Sets $A$ and $B$ have $13$ and $14$ elements, with $5$ elements in both. Find $|A\cup B|$.
Skill: sets and inclusion-exclusion · Level: Stretch
- 22
- 27
- 5
- 32
Show the worked answer
- Add the set sizes: $13+14=27$.
- Subtract the $5$ shared elements: $|A\cup B|=22$.
Answer: 22
Question 28: In how many orders can $6$ distinct books be arranged on a shelf?
Skill: permutations · Level: Build
- 36
- 30
- 64
- 720
Show the worked answer
- There are $6$ choices, then $5$, continuing to $1$.
- The count is $6!=720$.
Answer: 720
Question 29: How many $2$-person committees can be selected from $9$ people?
Skill: combinations · Level: Apply
- 81
- 2
- 36
- 18
Show the worked answer
- Use $\binom{9}{2}$.
- The number is $36$.
Answer: 36
Question 30: Let $p$ be false and $q$ be true. What is the truth value of $p\to q$?
Skill: propositional logic · Level: Stretch
- both true and false
- true
- false
- cannot be determined
Show the worked answer
- Here $p$ is false and $q$ is true.
- Therefore $p\to q$ is true.
Answer: true
Question 31: A graph has vertex degrees $4, 5, 6, 7$. If such a graph exists, how many edges does it have?
Skill: graph theory · Level: Build
- 11
- 22
- 4
- 13
Show the worked answer
- The degree sum is $22$.
- By the handshake lemma, the edge count is $22/2=11$.
Answer: 11
Question 32: A recurrence is $a_0=5$ and $a_n=a_{n-1}+6$. Find $a_{8}$.
Skill: recurrences · Level: Apply
- 47
- 11
- 48
- 53
Show the worked answer
- After $8$ steps, the total increase is $8(6)$.
- $a_{8}=5+8(6)=53$.
Answer: 53
Question 33: Find $41\bmod 6$.
Skill: modular arithmetic · Level: Stretch
- 1
- 11
- 5
- 6
Show the worked answer
- $41=6(6)+5$.
- The remainder is $5$.
Answer: 5
Question 34: Write decimal $14$ in binary.
Skill: number representation · Level: Build
- 14
- 1110
- 1111
- 1101
Show the worked answer
- The powers of two selected by $14$ determine its binary digits.
- The binary representation is $1110_2$.
Answer: 1110
Question 35: Among students, $15$ study logic, $13$ study graphs, and $6$ study both. How many study at least one?
Skill: inclusion-exclusion · Level: Apply
- 22
- 28
- 6
- 34
Show the worked answer
- $15+13=28$ counts the shared students twice.
- Subtract $6$ to get $22$.
Answer: 22
Question 36: If $13$ objects are placed into $6$ boxes, what minimum number must be in at least one box?
Skill: pigeonhole principle · Level: Stretch
- 2
- 6
- 4
- 3
Show the worked answer
- $13/6=2.167$.
- Rounding up gives $\lceil 13/6\rceil=3$.
Answer: 3
Question 37: Sets $A$ and $B$ have $14$ and $16$ elements, with $2$ elements in both. Find $|A\cup B|$.
Skill: sets and inclusion-exclusion · Level: Build
- 2
- 32
- 28
- 30
Show the worked answer
- Add the set sizes: $14+16=30$.
- Subtract the $2$ shared elements: $|A\cup B|=28$.
Answer: 28
Question 38: In how many orders can $7$ distinct books be arranged on a shelf?
Skill: permutations · Level: Apply
- 128
- 5040
- 49
- 42
Show the worked answer
- There are $7$ choices, then $6$, continuing to $1$.
- The count is $7!=5040$.
Answer: 5040
Question 39: How many $3$-person committees can be selected from $10$ people?
Skill: combinations · Level: Stretch
- 120
- 30
- 1000
- 6
Show the worked answer
- Use $\binom{10}{3}$.
- The number is $120$.
Answer: 120
Question 40: A graph has vertex degrees $5, 6, 7, 8$. If such a graph exists, how many edges does it have?
Skill: graph theory · Level: Apply
- 4
- 15
- 13
- 26
Show the worked answer
- The degree sum is $26$.
- By the handshake lemma, the edge count is $26/2=13$.
Answer: 13
Question 41: A recurrence is $a_0=6$ and $a_n=a_{n-1}+7$. Find $a_{9}$.
Skill: recurrences · Level: Stretch
- 63
- 69
- 62
- 13
Show the worked answer
- After $9$ steps, the total increase is $9(7)$.
- $a_{9}=6+9(7)=69$.
Answer: 69
Question 42: Find $48\bmod 7$.
Skill: modular arithmetic · Level: Build
- 6
- 1
- 13
- 7
Show the worked answer
- $48=6(7)+6$.
- The remainder is $6$.
Answer: 6
Question 43: Write decimal $17$ in binary.
Skill: number representation · Level: Apply
- 10010
- 10000
- 17
- 10001
Show the worked answer
- The powers of two selected by $17$ determine its binary digits.
- The binary representation is $10001_2$.
Answer: 10001
Question 44: Among students, $16$ study logic, $14$ study graphs, and $3$ study both. How many study at least one?
Skill: inclusion-exclusion · Level: Stretch
- 3
- 33
- 27
- 30
Show the worked answer
- $16+14=30$ counts the shared students twice.
- Subtract $3$ to get $27$.
Answer: 27
Question 45: If $14$ objects are placed into $3$ boxes, what minimum number must be in at least one box?
Skill: pigeonhole principle · Level: Build
- 6
- 5
- 4
- 3
Show the worked answer
- $14/3=4.667$.
- Rounding up gives $\lceil 14/3\rceil=5$.
Answer: 5
Question 46: Sets $A$ and $B$ have $15$ and $18$ elements, with $3$ elements in both. Find $|A\cup B|$.
Skill: sets and inclusion-exclusion · Level: Apply
- 30
- 33
- 3
- 36
Show the worked answer
- Add the set sizes: $15+18=33$.
- Subtract the $3$ shared elements: $|A\cup B|=30$.
Answer: 30
Question 47: In how many orders can $8$ distinct books be arranged on a shelf?
Skill: permutations · Level: Stretch
- 64
- 56
- 256
- 40320
Show the worked answer
- There are $8$ choices, then $7$, continuing to $1$.
- The count is $8!=40320$.
Answer: 40320
Question 48: How many $4$-person committees can be selected from $11$ people?
Skill: combinations · Level: Build
- 14641
- 24
- 330
- 44
Show the worked answer
- Use $\binom{11}{4}$.
- The number is $330$.
Answer: 330
Question 49: A graph has vertex degrees $6, 7, 8, 9$. If such a graph exists, how many edges does it have?
Skill: graph theory · Level: Stretch
- 15
- 30
- 4
- 17
Show the worked answer
- The degree sum is $30$.
- By the handshake lemma, the edge count is $30/2=15$.
Answer: 15
Question 50: A recurrence is $a_0=7$ and $a_n=a_{n-1}+8$. Find $a_{10}$.
Skill: recurrences · Level: Build
- 79
- 15
- 80
- 87
Show the worked answer
- After $10$ steps, the total increase is $10(8)$.
- $a_{10}=7+10(8)=87$.
Answer: 87
Question 51: Find $55\bmod 3$.
Skill: modular arithmetic · Level: Apply
- 2
- 4
- 1
- 18
Show the worked answer
- $55=18(3)+1$.
- The remainder is $1$.
Answer: 1
Question 52: Write decimal $20$ in binary.
Skill: number representation · Level: Stretch
- 20
- 10100
- 10101
- 10011
Show the worked answer
- The powers of two selected by $20$ determine its binary digits.
- The binary representation is $10100_2$.
Answer: 10100
Question 53: Among students, $17$ study logic, $15$ study graphs, and $4$ study both. How many study at least one?
Skill: inclusion-exclusion · Level: Build
- 28
- 32
- 4
- 36
Show the worked answer
- $17+15=32$ counts the shared students twice.
- Subtract $4$ to get $28$.
Answer: 28
Question 54: If $15$ objects are placed into $4$ boxes, what minimum number must be in at least one box?
Skill: pigeonhole principle · Level: Apply
- 3
- 5
- 6
- 4
Show the worked answer
- $15/4=3.750$.
- Rounding up gives $\lceil 15/4\rceil=4$.
Answer: 4
Question 55: Sets $A$ and $B$ have $16$ and $20$ elements, with $4$ elements in both. Find $|A\cup B|$.
Skill: sets and inclusion-exclusion · Level: Stretch
- 4
- 40
- 32
- 36
Show the worked answer
- Add the set sizes: $16+20=36$.
- Subtract the $4$ shared elements: $|A\cup B|=32$.
Answer: 32
Question 56: In how many orders can $3$ distinct books be arranged on a shelf?
Skill: permutations · Level: Build
- 7
- 6
- 9
- 8
Show the worked answer
- There are $3$ choices, then $2$, continuing to $1$.
- The count is $3!=6$.
Answer: 6
Question 57: How many $2$-person committees can be selected from $12$ people?
Skill: combinations · Level: Apply
- 66
- 24
- 144
- 2
Show the worked answer
- Use $\binom{12}{2}$.
- The number is $66$.
Answer: 66
Question 58: Let $p$ be true and $q$ be true. What is the truth value of $p\to q$?
Skill: propositional logic · Level: Stretch
- false
- cannot be determined
- both true and false
- true
Show the worked answer
- Here $p$ is true and $q$ is true.
- Therefore $p\to q$ is true.
Answer: true
Question 59: A graph has vertex degrees $7, 8, 9, 10$. If such a graph exists, how many edges does it have?
Skill: graph theory · Level: Build
- 4
- 19
- 17
- 34
Show the worked answer
- The degree sum is $34$.
- By the handshake lemma, the edge count is $34/2=17$.
Answer: 17
Question 60: A recurrence is $a_0=8$ and $a_n=a_{n-1}+9$. Find $a_{11}$.
Skill: recurrences · Level: Apply
- 99
- 107
- 98
- 17
Show the worked answer
- After $11$ steps, the total increase is $11(9)$.
- $a_{11}=8+11(9)=107$.
Answer: 107
Question 61: Find $62\bmod 4$.
Skill: modular arithmetic · Level: Stretch
- 2
- 15
- 6
- 3
Show the worked answer
- $62=15(4)+2$.
- The remainder is $2$.
Answer: 2
Question 62: Write decimal $23$ in binary.
Skill: number representation · Level: Build
- 11000
- 10110
- 23
- 10111
Show the worked answer
- The powers of two selected by $23$ determine its binary digits.
- The binary representation is $10111_2$.
Answer: 10111
Question 63: Among students, $18$ study logic, $16$ study graphs, and $5$ study both. How many study at least one?
Skill: inclusion-exclusion · Level: Apply
- 5
- 39
- 29
- 34
Show the worked answer
- $18+16=34$ counts the shared students twice.
- Subtract $5$ to get $29$.
Answer: 29
Question 64: If $16$ objects are placed into $5$ boxes, what minimum number must be in at least one box?
Skill: pigeonhole principle · Level: Stretch
- 6
- 4
- 3
- 5
Show the worked answer
- $16/5=3.200$.
- Rounding up gives $\lceil 16/5\rceil=4$.
Answer: 4
Question 65: Sets $A$ and $B$ have $17$ and $22$ elements, with $5$ elements in both. Find $|A\cup B|$.
Skill: sets and inclusion-exclusion · Level: Build
- 34
- 39
- 5
- 44
Show the worked answer
- Add the set sizes: $17+22=39$.
- Subtract the $5$ shared elements: $|A\cup B|=34$.
Answer: 34
Question 66: How many $3$-person committees can be selected from $13$ people?
Skill: combinations · Level: Stretch
- 2197
- 6
- 286
- 39
Show the worked answer
- Use $\binom{13}{3}$.
- The number is $286$.
Answer: 286
Question 67: A graph has vertex degrees $8, 9, 10, 11$. If such a graph exists, how many edges does it have?
Skill: graph theory · Level: Apply
- 19
- 38
- 4
- 21
Show the worked answer
- The degree sum is $38$.
- By the handshake lemma, the edge count is $38/2=19$.
Answer: 19
Question 68: A recurrence is $a_0=9$ and $a_n=a_{n-1}+10$. Find $a_{12}$.
Skill: recurrences · Level: Stretch
- 119
- 19
- 120
- 129
Show the worked answer
- After $12$ steps, the total increase is $12(10)$.
- $a_{12}=9+12(10)=129$.
Answer: 129
Question 69: Find $69\bmod 5$.
Skill: modular arithmetic · Level: Build
- 1
- 9
- 4
- 13
Show the worked answer
- $69=13(5)+4$.
- The remainder is $4$.
Answer: 4
Question 70: Write decimal $26$ in binary.
Skill: number representation · Level: Apply
- 26
- 11010
- 11011
- 11001
Show the worked answer
- The powers of two selected by $26$ determine its binary digits.
- The binary representation is $11010_2$.
Answer: 11010
Question 71: Among students, $19$ study logic, $17$ study graphs, and $6$ study both. How many study at least one?
Skill: inclusion-exclusion · Level: Stretch
- 30
- 36
- 6
- 42
Show the worked answer
- $19+17=36$ counts the shared students twice.
- Subtract $6$ to get $30$.
Answer: 30
Question 72: If $17$ objects are placed into $6$ boxes, what minimum number must be in at least one box?
Skill: pigeonhole principle · Level: Build
- 2
- 6
- 4
- 3
Show the worked answer
- $17/6=2.833$.
- Rounding up gives $\lceil 17/6\rceil=3$.
Answer: 3
Question 73: Sets $A$ and $B$ have $18$ and $24$ elements, with $2$ elements in both. Find $|A\cup B|$.
Skill: sets and inclusion-exclusion · Level: Apply
- 2
- 44
- 40
- 42
Show the worked answer
- Add the set sizes: $18+24=42$.
- Subtract the $2$ shared elements: $|A\cup B|=40$.
Answer: 40
Question 74: How many $4$-person committees can be selected from $14$ people?
Skill: combinations · Level: Build
- 1001
- 56
- 38416
- 24
Show the worked answer
- Use $\binom{14}{4}$.
- The number is $1001$.
Answer: 1001
Question 75: A graph has vertex degrees $9, 10, 11, 12$. If such a graph exists, how many edges does it have?
Skill: graph theory · Level: Stretch
- 4
- 23
- 21
- 42
Show the worked answer
- The degree sum is $42$.
- By the handshake lemma, the edge count is $42/2=21$.
Answer: 21
Question 76: A recurrence is $a_0=10$ and $a_n=a_{n-1}+11$. Find $a_{13}$.
Skill: recurrences · Level: Build
- 143
- 153
- 142
- 21
Show the worked answer
- After $13$ steps, the total increase is $13(11)$.
- $a_{13}=10+13(11)=153$.
Answer: 153
Question 77: Find $76\bmod 6$.
Skill: modular arithmetic · Level: Apply
- 4
- 12
- 2
- 10
Show the worked answer
- $76=12(6)+4$.
- The remainder is $4$.
Answer: 4
Question 78: Write decimal $29$ in binary.
Skill: number representation · Level: Stretch
- 11110
- 11100
- 29
- 11101
Show the worked answer
- The powers of two selected by $29$ determine its binary digits.
- The binary representation is $11101_2$.
Answer: 11101
Question 79: Among students, $20$ study logic, $18$ study graphs, and $3$ study both. How many study at least one?
Skill: inclusion-exclusion · Level: Build
- 3
- 41
- 35
- 38
Show the worked answer
- $20+18=38$ counts the shared students twice.
- Subtract $3$ to get $35$.
Answer: 35
Question 80: If $18$ objects are placed into $3$ boxes, what minimum number must be in at least one box?
Skill: pigeonhole principle · Level: Apply
- 8
- 6
- 3
- 7
Show the worked answer
- $18/3=6.000$.
- Rounding up gives $\lceil 18/3\rceil=6$.
Answer: 6
Question 81: Sets $A$ and $B$ have $19$ and $26$ elements, with $3$ elements in both. Find $|A\cup B|$.
Skill: sets and inclusion-exclusion · Level: Stretch
- 42
- 45
- 3
- 48
Show the worked answer
- Add the set sizes: $19+26=45$.
- Subtract the $3$ shared elements: $|A\cup B|=42$.
Answer: 42
Question 82: How many $2$-person committees can be selected from $15$ people?
Skill: combinations · Level: Apply
- 225
- 2
- 105
- 30
Show the worked answer
- Use $\binom{15}{2}$.
- The number is $105$.
Answer: 105
Question 83: A graph has vertex degrees $10, 11, 12, 13$. If such a graph exists, how many edges does it have?
Skill: graph theory · Level: Build
- 23
- 46
- 4
- 25
Show the worked answer
- The degree sum is $46$.
- By the handshake lemma, the edge count is $46/2=23$.
Answer: 23
Question 84: A recurrence is $a_0=11$ and $a_n=a_{n-1}+12$. Find $a_{14}$.
Skill: recurrences · Level: Apply
- 167
- 23
- 168
- 179
Show the worked answer
- After $14$ steps, the total increase is $14(12)$.
- $a_{14}=11+14(12)=179$.
Answer: 179
Question 85: Find $83\bmod 7$.
Skill: modular arithmetic · Level: Stretch
- 1
- 13
- 6
- 11
Show the worked answer
- $83=11(7)+6$.
- The remainder is $6$.
Answer: 6
Question 86: Write decimal $32$ in binary.
Skill: number representation · Level: Build
- 32
- 100000
- 100001
- 11111
Show the worked answer
- The powers of two selected by $32$ determine its binary digits.
- The binary representation is $100000_2$.
Answer: 100000
Question 87: Among students, $21$ study logic, $19$ study graphs, and $4$ study both. How many study at least one?
Skill: inclusion-exclusion · Level: Apply
- 36
- 40
- 4
- 44
Show the worked answer
- $21+19=40$ counts the shared students twice.
- Subtract $4$ to get $36$.
Answer: 36
Question 88: If $19$ objects are placed into $4$ boxes, what minimum number must be in at least one box?
Skill: pigeonhole principle · Level: Stretch
- 4
- 6
- 7
- 5
Show the worked answer
- $19/4=4.750$.
- Rounding up gives $\lceil 19/4\rceil=5$.
Answer: 5
Question 89: Sets $A$ and $B$ have $20$ and $28$ elements, with $4$ elements in both. Find $|A\cup B|$.
Skill: sets and inclusion-exclusion · Level: Build
- 4
- 52
- 44
- 48
Show the worked answer
- Add the set sizes: $20+28=48$.
- Subtract the $4$ shared elements: $|A\cup B|=44$.
Answer: 44
Question 90: How many $3$-person committees can be selected from $16$ people?
Skill: combinations · Level: Stretch
- 560
- 48
- 4096
- 6
Show the worked answer
- Use $\binom{16}{3}$.
- The number is $560$.
Answer: 560
Question 91: A graph has vertex degrees $11, 12, 13, 14$. If such a graph exists, how many edges does it have?
Skill: graph theory · Level: Apply
- 4
- 27
- 25
- 50
Show the worked answer
- The degree sum is $50$.
- By the handshake lemma, the edge count is $50/2=25$.
Answer: 25
Question 92: A recurrence is $a_0=12$ and $a_n=a_{n-1}+13$. Find $a_{15}$.
Skill: recurrences · Level: Stretch
- 195
- 207
- 194
- 25
Show the worked answer
- After $15$ steps, the total increase is $15(13)$.
- $a_{15}=12+15(13)=207$.
Answer: 207
Question 93: Find $90\bmod 3$.
Skill: modular arithmetic · Level: Build
- 0
- 30
- 3
- 1
Show the worked answer
- $90=30(3)+0$.
- The remainder is $0$.
Answer: 0
Question 94: Write decimal $35$ in binary.
Skill: number representation · Level: Apply
- 100100
- 100010
- 35
- 100011
Show the worked answer
- The powers of two selected by $35$ determine its binary digits.
- The binary representation is $100011_2$.
Answer: 100011
Question 95: Among students, $22$ study logic, $20$ study graphs, and $5$ study both. How many study at least one?
Skill: inclusion-exclusion · Level: Stretch
- 5
- 47
- 37
- 42
Show the worked answer
- $22+20=42$ counts the shared students twice.
- Subtract $5$ to get $37$.
Answer: 37
Question 96: If $20$ objects are placed into $5$ boxes, what minimum number must be in at least one box?
Skill: pigeonhole principle · Level: Build
- 7
- 4
- 5
- 6
Show the worked answer
- $20/5=4.000$.
- Rounding up gives $\lceil 20/5\rceil=4$.
Answer: 4
Question 97: Sets $A$ and $B$ have $21$ and $30$ elements, with $5$ elements in both. Find $|A\cup B|$.
Skill: sets and inclusion-exclusion · Level: Apply
- 46
- 51
- 5
- 56
Show the worked answer
- Add the set sizes: $21+30=51$.
- Subtract the $5$ shared elements: $|A\cup B|=46$.
Answer: 46
Question 98: How many $4$-person committees can be selected from $17$ people?
Skill: combinations · Level: Build
- 83521
- 24
- 2380
- 68
Show the worked answer
- Use $\binom{17}{4}$.
- The number is $2380$.
Answer: 2380
Question 99: A graph has vertex degrees $12, 13, 14, 15$. If such a graph exists, how many edges does it have?
Skill: graph theory · Level: Stretch
- 27
- 54
- 4
- 29
Show the worked answer
- The degree sum is $54$.
- By the handshake lemma, the edge count is $54/2=27$.
Answer: 27
Question 100: A recurrence is $a_0=13$ and $a_n=a_{n-1}+14$. Find $a_{16}$.
Skill: recurrences · Level: Build
- 223
- 27
- 224
- 237
Show the worked answer
- After $16$ steps, the total increase is $16(14)$.
- $a_{16}=13+16(14)=237$.
Answer: 237