Elementary Number Theory and Combinatorics Questions and Answers

Answer: A

There are 7 such subsets.

The even integers in X are 2, 4 and 6. A subset containing only even integers is any subset of {2, 4, 6}, and excluding the empty set leaves

\[ 2^{3} - 1 = 7 \]

They are {2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6} and {2, 4, 6}. The answer 8 counts the empty set as well, which the question excludes; 3 counts only the even numbers themselves, and 1 counts only the full set {2, 4, 6}.

Answer: A

The number of words is 24.

PNTU has 4 distinct letters, and a word of three distinct letters is an ordered arrangement of 3 of them:

\[ {}^{4}P_{3} = 4 \times 3 \times 2 = 24 \]

\(2^{4} = 16\) counts subsets of the 4 letters, \(4^{2} = 16\) counts two-letter words with repetition, and \(4^{6}\) has no connection with the count.

Answer: A

The value that must work is 10.

There are 7 days of the week. By the pigeonhole principle, any group of 8 or more people must contain two born on the same day of the week, while a group of 7 or fewer can have everyone on a different day.

So the property is guaranteed only when \(n \ge 8\). Of the options, only 10 qualifies. With 7, 6 or 5 people each person can have a different day, so the property can fail.

Answer: D

There are 30 non-empty proper subsets.

A set with 5 elements has \(2^{5} = 32\) subsets in all. A proper subset excludes X itself, and non-empty excludes \(\varnothing\), so

\[ 2^{5} - 2 = 30 \]

31 removes only one of the two (either the empty set or X), 32 counts every subset, and 16 is \(2^{4}\), the number of subsets of a four-element set.

Answer: D

Of the options, the value that works is \(k = 15\).

For coprime 3 and 8, the largest integer that is not a non-negative combination \(3a + 8b\) is the Frobenius number

\[ 3 \cdot 8 - 3 - 8 = 13 \]

So every integer from 14 onwards can be written with 3's and 8's (14 = 3 + 3 + 8, 15 = 3 × 5, 16 = 8 + 8, and adding 3's covers the rest), while 13 cannot.

Any valid k must therefore exceed 13, which rules out 6, 8 and 9 (each would require 13 to be representable). Of the four choices only 15 has the property; the smallest such k is 14, which is not offered.

Answer: B

\(\mathbf{Z}_{12}\) has 4 units.

A class a is a unit mod 12 exactly when \(\gcd(a, 12) = 1\). Those classes are 1, 5, 7 and 11, so there are \(\varphi(12) = 12\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 4\) units. Each is its own inverse: \(5^{2} = 25 \equiv 1\), \(7^{2} = 49 \equiv 1\), \(11^{2} = 121 \equiv 1\).

3 and 5 miscount the coprime residues, and 2 counts only \(\pm 1\).