GRE | Antimatroid, The

Posts Tagged ‘GRE’

Mathematics Test Practice Questions

I’ve had a fairly busy month, so I haven’t had a lot of time to work on any projects. I’ve got a few in the pipeline, but none really mature enough yet to get a write-up. I’ve been playing with the idea of graduate school for a couple years now and have always felt that a strong mathematics background is a good basis for pursuing more interesting (computer science) topics. So, this past week I’ve been working my way through the Mathematics Test Practice Book to see how well I’d fare. The examination seems fairly aggressive allowing for roughly 2.5 minutes per problem for 66 problems. I’m a little more methodical in my ways, so I would certainly take more time than what’s allotted. Nonetheless, I thought I’d share my take on a handful of problems from different subject matters that I found of particular interest:

Let $P_{1}$ be the set of all primes, $\{2, 3, 5, 7,\ldots \}$ , and for each integer $n$ , let $P_{n}$ be the set of all prime multiples of n, $\{2n, 3n, 5n, 7n, \ldots \}$ . Which of the following intersections is nonempty?

$P_{1} \cap P_{23}$

$P_{7} \cap P_{21}$

$P_{12} \cap P_{20}$

$P_{20} \cap P_{24}$

$P_{5} \cap P_{25}$

Given $P_{n} \cap P_{m}$ , we’ll pick two elements (one from each set) and solve for $n p_{1}^{(i)} = m p_{1}^{(j)}$ . We then assume that $n, m$ are of the form $a p_{1}^{(k)}$ where $a$ is a composite. Thus, $a p_{1}^{(j)} p_{1}^{(i)} = a p_{1}^{(i)} p_{1}^{(j)}$ , we can conclude that $p_{1}^{(j)}p_{1}^{(i)} \in P_{n} \cap P_{m}$ . Thus, D is the correct answer.

For what value of $b$ is the line $g(x) = 10x$ tangent to the curve $h(x) = e^{bx}$ at some point in the xy-plane?

Using operator notation, a line tangent to a curve is given by $T_{x_{0}} f = \frac{df}{dx}(x_{0})(x - x_{0}) + f(x_{0})$ . To solve for $b$ we solve for $T_{x_{0}} h = g \implies 10x = be^{b x_0}(x - x_0) + e^{b x_0} \implies 10x = be^{b x_0}x + e^{b x_0}(1 - bx_0)$

Which yields the following two equations: $10 = be^{b x_0}$ and $0 = e^{b x_0}(1 - bx_0)$ since $e^{b x_0}$ will never equal zero, we can conclude $0 = 1 - b x_0 \implies 1 = bx_0 \implies x_0 = \frac{1}{b}$ . Substituting for $x_{0}$ yields $10 = b e^{b \frac{1}{b}} \implies 10 = be \implies b = \frac{10}{e}$ .

Suppose that two binary operations, denoted by $\oplus$ and $\odot$ , are defined on a nonempty set $S$ , and that the following conditions are satisfied for all $x$ , $y$ and $z$ in $S$ :

(1) (Closure) $x \oplus y, x \odot y \in S$
(2) (Associativity) $x \oplus (y \oplus z) = (x \oplus y) \oplus z$ and $x \odot (y \odot z) = (x \odot y) \odot z$
(3) (Commutativity) $x \oplus y = y \oplus x$

Also, for each $x \in S$ and for each positive integer $n$ , the elements $nx$ and $x^n$ are defined recursively as follows:

(4) (Identity Element) $1x = x^1 = x$
(5) and if $kx$ and $x^k$ have been defined, then $(k + 1)x = kx \oplus x$ and $x^{k + 1} = x^k \odot x$

Which of the following must be true?

I only

II only

III only

II and III only

I, II and III

I.) $(x \odot y)^n = x^n \odot y^n$ s.t. $x, y \in S, n \in \mathbb{Z}^{+}$

Assume $x \odot y \in S$ , from which we assume $(x \odot y) \odot (x \odot y) \in S$ . If (3) were defined for $\odot$ , we could swap either side then apply (2) reducing it down to the recursive definition (5) and have a proof. Since that isn’t the case, we can’t conclude that $(x \odot y)^n = x^n \odot y^n$ .

II.) $n (x \oplus y) = nx \oplus ny$ s.t. $x,y \in S, n \in \mathbb{Z}^{+}$

Given (1) we can construct $(x \oplus y) = 1 (x \oplus y)$ by using (4). We can state $2 (x \oplus y) = 1 (x \oplus y) \oplus (x \oplus y)$ from (5), leading to $2 (x \oplus y) = (x \oplus y) \oplus (y \oplus x)$ by way of (3). $2 (x \oplus y) = x \oplus (y \oplus (y \oplus x))$ and $2 (x \oplus y) = x \oplus ((y \oplus y) \oplus x)$ by (2). From (5) $2 (x \oplus y) = x \oplus (2y \oplus x)$ . Unfolding that set of steps leads to the following: $2 (x \oplus y) = x \oplus (x \oplus 2y)$ , $2 (x \oplus y) = (x \oplus x) \oplus 2y$ and $2 (x \oplus y) = 2x \oplus 2y$ . If we were to continue down this path for $n = \{3, 4, 5,\dotsc\}$ then we would find that $n (x \oplus y) = nx \oplus ny$ .

III.) $x^m \odot x^n = x^{m+n}$ s.t. $x \in S, m,n \in \mathbb{Z}^{+}$ .

Starting with (5): $x^{m + 1} = x^m \odot x$ we introduce an additional $x$ , $x^{m + 1} \odot x = (x^m \odot x) \odot x$ and then apply (2) $x^{m + 2}= x^m \odot (x \odot x)$ which leads to $x^{m + 2} = x^m \odot x^2$ . The same set of steps once again leads to $x^{m + 2} \odot x = (x^m \odot x^2) \odot x$ $x^{m + 3} = x^m \odot (x^2 \odot x)$ $x^{m + 3} = x^m \odot x^3$ . By induction, we can conclude $x^{m + n} = x^m \odot x^n$ .

At a banquet, 9 women and 6 men are to be seated in a row of 15 chairs. If the entire seating arrangement is to be chosen at random, what is the probability that all of the men will be seated next to each other in 6 consecutive positions?

I’m going to use the notation $y_{M}$ to denote a number of men ( $Y_{M}$ for the total number of men), $x_{W}$ to denote a number of women ( $X_{W}$ for the total) and $S$ to denote the number of seats. A sequence of this notation such as $3_{W} 6_{M} 6_{W}$ indicates a sequence of three women, six men and six women seated amongst the fifteen seats. Given the definition, we are interested in the probability of $P[ \bigcup_{i = 0}^{X_{W}} {i_{W}Y_{M}(X_{W} - i)_{W}}]$ . Since there are a fixed number of seats and no two people can occupy the same seat, we know that the number of permutations of $S = S!$ is the total number of possible arrangements (our sample space). There are $Y_{M}!$ ways in which the men can be arranged and there are $X_{W}!$ ways in which the women can be arranged in the remaining seats. Since there are $X_{W} + 1$ ways to “slide” the group of men along the seats we can conclude that:

$\displaystyle P[ \bigcup_{i = 0}^{X_{W}} {i_{W}Y_{M}(X_{W} - i)_{W}}] = \frac{(X_{W}+1) X_{W}! Y_{M}!}{S!}$

Given the question, the solution is

$\displaystyle P[ 0_{W}6_{M}9_W \cup 1_{W}6_{M}8_W \cup 2_{W}6_{M}7_W \cdot 9_{W}6_{M}0_W] = \frac{10 * 9! 6!}{15!} = \frac{10! 6!}{15!}$

If $\displaystyle z = e^{\frac{2 \pi i}{5}}$ , then $w = 1 + z + z^2 + z^3 + 5z^4 + 4z^5 + 4z^6 + 4z^7 + 4z^8 + 5z^9 =$ ?

$0$

$4 e^{\frac{3 \pi i}{5}}$

$5 e^{\frac{4 \pi i}{5}}$

$-4 e^{\frac{2 \pi i}{5}}$

$-5 e^{\frac{3 \pi i}{5}}$

First thing to observe is that $z$ is the 5’th root of unity which carries with it two properties:

$z^5 = 1$
$\displaystyle \sum_{k = 0}^{4} z^k = 0$

Proof of property (1) is trivial, proof of property (2) is basic proof of the geometric series:

$\displaystyle \sum_{k = 0}^{n} z^k = a \implies \sum_{k = 1}^{n+1} z^k = z a \implies\displaystyle \sum_{k = 1}^{n+1}{z^k} - \sum_{k = 0}^{n}{z^k} = z a - a \implies$
$\displaystyle z^{n+1} - 1 = a (z - 1) \implies a = \frac{z^{n+1} - 1}{z - 1}$
$\displaystyle \therefore \sum_{k = 0}^{n} z^k = \frac{z^{n+1} - 1}{z - 1}$

Given these properties, we begin to evaluate $w$ by separating the terms into reducible portions:

$\displaystyle w = (1 + z + z^2 + z^3 + z^4) + 4z^4(1 + z + z^2 + z^3 + z^4) + 5(z^4 z^5) \implies$
$\displaystyle w = (1 + 4z^4)\sum_{k = 0}^{4}{z^k} + 5(z^4 1) \implies w = 5z^4 \implies w = 5 e^{\frac{8 \pi i}{5}} \implies$
$\displaystyle w = 5 e^{\pi i} e^{\frac{3 \pi i}{5}} \implies w = -5 e^{\frac{3 \pi i}{5}}$

If $\lfloor{x}\rfloor$ denotes the greatest integer not exceeding x, then $\int_{0}^{\infty}{\lfloor{x}\rfloor e^{-x} dx} =$

$\frac{e}{e^2 - 1}$

$\frac{1}{e - 1}$

$\frac{e - 1}{e}$

$1$

$+\infty$

When $x \in \mathbb{Z}$ , we have a discontinuity in the function that we are integrating because of the floor function. To resolve this issue, we need to break up the integral into a sum of integrals as follows: $\displaystyle \int_{0}^{\infty}{\lfloor{x}\rfloor e^{-x} dx} = \sum_{n = 0}^{\infty} n \int_{n}^{n+1}{e^{-x} dx} = \sum_{n = 0}^{\infty} n (-e^{-x})\rvert_{n}^{n+1} =$ $\displaystyle \sum_{n = 0}^{\infty} n (-e^{-(n+1)} + e^{-n}) = \sum_{n = 0}^{\infty} n \left( \frac{1}{e^n} - \frac{1}{e e^n} \right) = \left( 1 - \frac{1}{e} \right) \sum_{n = 0}^{\infty} n \frac{1}{e}^n$ .

Now we are left with a series that looks similar to a geometric series, so we evaluate it using a similar proof, then return to evaluating the integral.

$\displaystyle \sum_{n = 0}^{m} n x^n = a \implies x \sum_{n = 0}^{m} n x^n = x a \implies \sum_{n = 0}^{m} n x^{n+1} = x a \implies$
$\displaystyle \sum_{n = 0}^{m} n x^{n+1} - \sum_{n = 0}^{m} n x^n = (x - 1) a \implies - \sum_{n = 1}^{m}{x^n} + m x^{m+1} = a(x-1)$ .

(This last step can be produced by expanding the series.) We see that we have a geometric series (without the first term) which was proved earlier. From these facts we can conclude:

$\displaystyle a = \frac{- (\frac{x^n - 1}{x - 1} - 1) + m x^{m+1}}{x-1}$ .

As we take the limit of $m \to \infty$ of this expression (assuming $x < 1$ for convergence) we find:

$\displaystyle a = \frac{- (\frac{- 1}{x - 1} - 1)}{x-1} \implies a = \frac{\frac{1}{x - 1}+1}{x-1} \implies a = \frac{\frac{x}{x - 1}}{x-1} \implies a = \frac{x}{(x-1)^2}$
$\displaystyle \therefore \sum_{n = 0}^{\infty} n x^n = \frac{x}{(x-1)^2}$ .

Returning to evaluating the integral, we now find:

$\displaystyle \int_{0}^{\infty}{\lfloor{x}\rfloor e^{-x} dx} = \frac{e - 1}{e} \frac{\frac{1}{e}}{(\frac{1}{e}-1)^2} = \frac{e - 1}{e} \frac{e}{(1-e)^2} = \frac{e - 1}{(-1)^2(e-1)^2} = \frac{1}{e-1}$ .

The four shaded circles in Figure 1 above are congruent and each is tangent to the large circle and to two of the other shaded circles. Figure 2 is the result of replacing each of the shaded circles in Figure 1 by a figure that is geometrically similar to Figure 1. What is the ratio of the area of the shaded portion of Figure 2 to the area of the shaded portion of Figure 1?

$\frac{1}{2 \sqrt{2}}$

$\frac{1}{1 + \sqrt{2}}$

$\frac{4}{1 + \sqrt{2}}$

$\left( \frac{\sqrt{2}}{1+\sqrt{2}} \right)^2$
$\left( \frac{2}{1+\sqrt{2}} \right)^2$

The first goal is to construct one of the shaded circles in Figure 1. Once the circle has been constructed, we know that the scaling factor of Figure 1 onto Figure 2 will be the radius of the shaded circle (assuming the bounding circle is the unit circle).

Starting with the unit circle, $U$ , centered at the origin, $A$ select points $B = (1, 0)$ and $C = (0, 1)$ on $U$ . Construct the midpoint $D = (\frac{1}{2}, \frac{1}{2})$ to construct the line $\overleftarrow{A}\overrightarrow{D} = x$ . The intersection of $\overleftarrow{A}\overrightarrow{D}$ with $U$ leads to the point $E = (\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2})$ . Let $\overleftarrow{F}\overrightarrow{G} = -x + \sqrt{2}$ be perpendicular to $\overleftarrow{A}\overrightarrow{D}$ at $E$ . Points $F = (0, \sqrt{2})$ and $G (\sqrt{2}, 0)$ . We can now construct two angle bisectors: $\overleftarrow{F}\overrightarrow{J} = -(1+\sqrt{2})x + \sqrt{2}$ and $\overleftarrow{I}\overrightarrow{G} = (1 - \sqrt{2})x + 2 - \sqrt{2}$ . The intersection of these two lines is $H = ( \sqrt{2} - 1, \sqrt{2} - 1)$ . Which implies the inscribed circle $\mathcal{I} = (x - \sqrt{2} + 1)^2 + (y - \sqrt{2} + 1)^2 = (\sqrt{2} - 1)^2$ .

Thus, the area of $\mathcal{I}$ is $\pi (\sqrt{2} - 1)^2$ and the total shaded area in Figure 1 is $4 \pi (\sqrt{2} - 1)^2$ . To figure out the shaded area of Figure 2, we’ll scale Figure 1 down by a factor of $\sqrt{2} - 1$ and multiply by 4 yielding $16 \pi (\sqrt{2} - 1)^4$ . These two areas give a ratio of: $\displaystyle \frac{16 \pi (\sqrt{2} - 1)^4}{4 \pi (\sqrt{2} - 1)^2} = \frac{4 (\sqrt{2} - 1)^2}{1} \frac{(\sqrt{2}+1)^2}{(\sqrt{2}+1)^2} = \frac{(2(\sqrt{2} - 1)(\sqrt{2}+1))^2}{(\sqrt{2}+1)^2} = \left( \frac{2}{\sqrt{2}+1} \right)^2$ .