The 2018 Prove it! Math Academy has come to a close. Many thanks to the Prove it! Math students and instructors for making our fourth year’s program a fantastic and memorable experience!

Check back in January 2019 for announcements and additional information. In the meantime, feel free to browse our Facebook page.

2018 Admissions Test

Instructions for the Student

Complete as many of the parts of the four problems below as you can. Show your work and fully explain all of your answers. You may either type your solutions and print them to a PDF file, or write them by hand and scan them to a PDF file. Submit your solutions by uploading that PDF file along with your online application.

These problems are intentionally challenging and you are not expected to solve them all completely. They are designed to give you the chance to demonstrate how you wrestle with mathematical problems. Partial solutions and observations should be submitted in the event that you do not find a complete solution. All work should be entirely your own. You should not discuss the problems with anyone else, whether online or in person.

The problems are listed below. A printable PDF version of the test is also available.

Have fun!

Problems

  1. At Walrus Ice Cream, the only available flavors are chocolate and vanilla. Kevin will order a cone with $n$ scoops of vanilla and $n$ scoops of chocolate, stacked on the cone in some order. Kevin prefers chocolate to vanilla, and he is more content eating a vanilla scoop if he knows that there is a lot of chocolate ice cream below it. Kevin defines the chocolate base score as the sum of the number of chocolate scoops below each vanilla scoop in the cone. (For example, if the cone has scoops VCCVVC from top to bottom, the chocolate base score is $3+1+1=5$.)
    1. If $n=3$, what are all the possible chocolate base scores for Kevin’s ice cream cone? For each score, how many different cones (arrangements of flavors) yield this score?
    2. Prove that for all nonnegative integers $n$ and $k$, the number of cones that earn a chocolate base score of $k$ equals the number of cones that earn a chocolate base score of $n^2-k$.
    3. Define $C(n,k)$ as the number of cones that have $n$ scoops of each flavor and a chocolate base score of $k$. Prove that for every natural number $k$, there exists a natural number $N_k$ such that for all natural numbers $n\ge N_k$, $C(n,k)=C(N_k, k)$. What is the smallest such number $N_k$ in terms of $k$? Prove your answer.
    4. Show that for all $n\ge 5$ and all integers $k$ between $1$ and $n$ inclusive, $$C(n,k)\lt C(n,k+1).$$ In other words, the number of cones with a given chocolate base score increases as the base score increases, at least up to score $n+1$. Does it ever decrease?
  2. Your favorite special-purpose calculator only takes positive integers as inputs and only returns positive integers as outputs.
    1. You carelessly leave this calculator out overnight, and a team of mischievous calculator gnomes strikes! They add a button to your calculator labeled $\boxdot$. Curious to discover what it does, you punch in $2 \boxdot 3$, and find it returns $18$. A few more experiments reveal that this new operation is not commutative; in particular, whenever $m\lt n$, the value of $n \boxdot m$ is less than $m \boxdot n$. Further investigation reveals that for all $m,n$, the arithmetic mean of $m \boxdot n$ and $n \boxdot m$ is always just $mn$ times the arithmetic mean of $m$ and $n$. Curious! You try computing their geometric mean, and notice that it is always $mn$ times the geometric mean of $m$ and $n$. Find, with proof, a formula for $m \boxdot n$ in terms of $m$ and $n$.
    2. You leave your calculator out again, and the calculator gnomes, pleased with your unraveling of the inner workings of their first button, install yet another button, labeled $\star$. Fortunately, you speak Gnomish and translate the gnomes’ instruction manual as follows:

      These are always true you see,
      for positive integers $m$, $n$, and $p$!

      1. $m(m \star (np))$ $= (m \star n)(m \star p)$
      2. $(mn) \star p$ $= m(n \star (p^m))$
      3. $(m+1) \star n$ $= ((m \star n)+(1 \star n)^m)n$
      Find, with proof, a formula for $m \star n$ in terms of $m$ and $n$.
  3. The Mathical Monsters collectible card game is played with decks of distinct cards chosen from a library of official playing cards. The local club is holding a Mathical Monsters card game tournament, but only certain decks are legal for tournament play. The collection of legal decks is chosen to satisfy the following property.

    Card Exchange Property: For any two legal decks $X$ and $Y$, if $y$ is a card in deck $Y$ but not in deck $X$, then there exists some card $x$ in deck $X$ but not in deck $Y$ such that the two decks that are obtained by exchanging cards $x$ and $y$ are also legal.
    For instance, if the deck $abc$ (short for the deck containing cards $a$, $b$, and $c$) and the deck $bde$ are both legal, then since $d$ is in $bde$ but not in $abc$ we must be able to trade card $d$ for one of the cards from the deck $abc$ that is not in $bde$ (i.e., for at least one of $a$ or $c$, but possibly not both) and end up with two legal decks.
    1. As a simple example, suppose that the library of official playing cards consists of just four cards: Abelian Archon ($a$), Binary Basilisk ($b$), Cartesian Chimera ($c$), and Differentiable Dragon ($d$). One member suggests the decks $ab, ac, ad, cd$ for the collection of legal decks for the tournament. Does this collection satisfy the Card Exchange Property?
    2. Now suppose that there are $100$ cards in the library of official playing cards, and that a collection of legal decks has been chosen that satisfies the Card Exchange Property. At the weekly card game club meeting, players exchange cards with each other one card at a time, ensuring that each trade results in a legal deck. If $A$ and $B$ are legal decks, is it always possible to trade cards in this way to acquire deck $B$ starting with deck $A$? Assume that enough players are present that every legal deck is owned by some player at all times, and that it is always possible to find a player willing to make any legal trade.
    3. Card collectors in the club like to collect Transversal Collections of cards: collections which contain at least one card from every legal deck, but for which no card can be removed while preserving this property. Show that if $C_1$ and $C_2$ are transversal collections of cards which both contain a card $c$, then there is another transversal collection consisting of cards in $C_1$ and $C_2$ which doesn’t contain card $c$.
  4. The famous 3-4-5 triangle has many nice properties, but what about its simpler cousin, the 2-3-4 triangle? We say that a triangle with integer side lengths is expandable if one of the triangles formed by the lines containing two of its sides and the angle bisector of one of its external angles is similar to the original triangle.
    1. Prove that a 2-3-4 triangle is expandable.
    2. Find all expandable triangles with no side length greater than $10$.
    3. Prove that there exists an expandable triangle with longest side length $n$ if and only if $n$ is not square-free. (An integer is said to be square-free if it is not divisible by the square of any prime.)

Next: Online Application