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.

Some of 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. The Walrus Ice Cream shop offers six distinct flavors of ice cream, arranged side by side in the display case. Walrus wishes to make the store look different from day to day by rearranging the order of the flavors. To avoid the nasty ice crystals that form when opening and closing the case, Walrus consults the company Scrambler. At the start of each day, their machines refill the six flavors in the following specific order: chocolate, strawberry, vanilla, pistachio, coffee, and blueberry. They have buttons on the side which can be used to rearrange the flavors according to specific internal mechanisms called moves. Scrambler offers three different products: the Juggler, the Frogger, and the Whirligig, each with its own set of moves. All three are described in their online simulator here:

   Scrambler! Product Catalog

   Walrus is debating which product to purchase. To get more information on the subtle differences between Scrambler's products, Walrus schedules a meeting with their sales rep, Eggbeater.

   Walrus: "So how exactly do we use these?"

   Eggbeater: "Well, once you choose your product, then each morning you just click 'New Goal' in the product catalogue, and it will give you a random attainable arrangement based on the product you purchased. Then using our website, you can try to find a sequence of moves that will get you to that day's arrangement."

   Walrus: "OK, I like that. I like both the Frogger and the Juggler. Which one will give me more ways to rearrange my flavors?"

   Eggbeater: "Well, it's a bit complicated. The Frogger will give you more arrangements to choose from, but there are some arrangements that the Juggler can produce that the Frogger cannot produce."

   Walrus: "It looks like with the Whirligig though, you can get any possible arrangement?"

   Eggbeater: "Not quite. The Whirligig actually only gets you half of all possible arrangements. But that is still a lot more than both the Juggler and the Frogger combined. On the other hand, the Juggler and the Frogger both allow some arrangements that are unavailable via the Whirligig. Perhaps you should buy all three machines?"

   Verify the truth of Eggbeater's claims by carrying out the following tasks.

   1. Find, with proof, a specific arrangement that the Juggler can produce that the Frogger cannot.
   2. Find, with proof, a specific arrangement that the Frogger can produce that the Juggler cannot.
   3. Calculate exactly how many arrangements each of the Juggler and the Frogger can produce.
   4. Find, with proof, an arrangement that the Juggler can produce that the Whirligig cannot.
   5. Find, with proof, an arrangement that the Frogger can produce that the Whirligig cannot.
   6. Prove that the Whirligig can produce exactly half of all possible arrangements.

2. A small marble is trapped in an otherwise empty container that has been ejected from a space station and is floating in space. No force is currently acting on the container or the marble, but due to the shaking of the container during the ejection process, the marble is now bouncing around inside the container.

   When it hits the side of the container at a point $P$, it bounces off as follows. If $\tau$ is the tangent plane to the container at point $P$, then if the marble is traveling along ray $r$ before hitting $P$, it continues along the ray $r'$ formed by reflecting the extension of $r$ beyond $P$ across the plane $\tau$.

   If the marble's path loops back on itself and enters a repeating pattern, we say it is a cyclic path. The bounce count of a cyclic path is the number of distinct points on the container that the marble hits along its path.

   1. If the container is a sphere, describe all cyclic paths that the marble could take. What bounce counts are possible?
   2. Suppose the container is the surface formed by rotating an ellipse with foci $A$ and $B$ about the line $AB$ (i.e., a prolate spheroid). What are the possible bounce counts for cyclic paths which pass through $A$?
   3. What are the possible bounce counts for a cyclic path if the container is a cube? Assume that the marble always hits points on the faces of the cube, not the edges or corners.

3. Andre, Bernice, Carl, and Donna are gnomes, and all four of them are friends with each other, except for Andre and Donna who aren't acquainted. The gnomes each have a number of cupcakes, and each distinct such assignment of numbers is called a configuration of cupcakes. For instance, Andre having one cupcake, Bernice having four cupcakes, and Carl and Donna having no cupcakes is one possible cupcake configuration.

   Gnomes are naturally friendly and generous creatures. If any gnome has at least one cupcake for each of their friends, then they will share by giving one cupcake to each friend—even if they don't have a cupcake left over for themselves! We say that a cupcake configuration is generous if at least one gnome has enough cupcakes to share, and otherwise we say that it is settled.

   Whenever gnomes meet, they each share their cupcakes, if they can, once every minute. If multiple gnomes are able to share at once, then they all share at the same time. Gnomes are so generous that they will continue to share cupcakes with each other until they reach a settled configuration. In some cases, this means that they get stuck in a sharing loop and never stop! If a configuration results in endless sharing, we call it very generous.

   Andre, Bernice, Carl, and Donna meet one day for a cupcake party. Between the four of them, they have five cupcakes in total.

   1. How many possible settled configurations can the group be in? How many generous configurations?
   2. How many of the generous configurations of five cupcakes are very generous?

   Let $G$ denote a collection of (finitely many) gnomes such that each gnome in $G$ has at least one friend in $G$. (Gnomes are not considered friends with themselves.)

   3. When the gnomes in $G$ meet for a cupcake party, what is the minimum number of cupcakes needed so that every configuration is very generous?
   4. Let $k$ be the number of unordered pairs of gnomes in $G$ that are friends. For example, $k = 5$ for Andre, Bernice, Carl, and Donna. Prove that there is a very generous configuration of $k$ cupcakes for $G$.

4. The broken addition button, $\oplus$, on Pima's calculator adds nonnegative integers in binary, but never carries any digits! For example, $7\oplus 5=2$, $4\oplus 3=7$, $43\oplus 58=17$, and $1024\oplus 1024=0$. The multiplication button, $\otimes$, works fine when multiplying by powers of $2$, but uses the same non-carrying addition, $\oplus$, when adding several such terms (when distributing the first factor across the second factor expressed as a sum of distinct powers of $2$). For example, $$7\otimes 11=7\otimes (8\oplus 2\oplus 1)=(7\otimes 8) \oplus (7\otimes 2) \oplus (7\otimes 1)=56\oplus 14\oplus 7=49.$$ Similarly, $4\otimes 3=12$, and $43\otimes 58=1758$.

   (In your solutions, use $+, \cdot$ for ordinary addition and multiplication, and $\oplus, \otimes$ for Pima addition and multiplication.)

   1. Make the addition table for $m\oplus n$ for $0\leq m,n\leq 15$ and the multiplication table for $m\otimes n$ for $0\leq m,n\leq 7$.
   2. Consider the sequence of Pima squares, $$1 \otimes 1=1,~2\otimes 2=4,~3\otimes 3=5,~4\otimes 4=16,~5\otimes5=17,~6\otimes 6=20, \ldots.$$ Which numbers are Pima squares? In other words, determine with proof all numbers of the form $n \otimes n$ for some positive integer $n$.
   3. For ordinary multiplication we can test an integer to see if it is divisible by $3$ by checking if the sum of its decimal digits is divisible by $3$. Find a similar divisibility-by-three test for Pima multiplication, i.e., determine with proof all numbers of the form $3 \otimes n$ for some positive integer $n$.
   4. Pima plays the following game on her calculator. Whenever a positive integer is even she divides it by $2$, but if it is odd she Pima-multiplies it by $3$ and then Pima-adds $1$. Then she continues to play with her new number obtained in this way. For example, if she plays starting with $33$ she obtains the sequence, $$33, 98, 49, 82, 41, 122, 61, 70, 35, 100, 50, 25, 42, 21, 62, 31, 32, 16, 8, 4, 2, 1, 2, 1, \ldots.$$ Prove or disprove that no matter what positive integer she starts with she will eventually reach the number $1$.