2007 Qualifying Quiz

You may also be interested in the printable (PDF) format.

1. Suppose we have n marbles numbered 1 through n and n+1 slots numbered 1 through n+1. Initially I place the marbles in slots 1 through n in any order of my choice, leaving slot n+1 empty. Your goal is to return the marbles to their correct order, with each marble in the appropriately numbered slot. You do this through a sequence of moves, where each move consists of transferring a marble from its current slot to the slot that is currently vacant. What is the maximum number of moves that might be needed, assuming I arrange the marbles so as to make your task as difficult as possible? (Your answer, of course, should depend on n. Don't forget to show that it really is the maximum.)

2. Find all positive integers (if any) not divisible by 5 whose expansion in base 5 is the reverse of their expansion in base 8. Don't forget to prove that there are no other solutions.

3. After Mathcamp 2006, seven friends agreed to stay in touch with each other by writing letters. Two months later, each of them had already sent a letter to exactly three of their six friends.

  1. Show that it is possible that each of the friends received exactly three letters.
  2. Is it possible that each of the friends received letters from exactly those to whom he or she sent letters? Either show how it can happen or prove that it's impossible.

4. Every day for dinner, Adina makes herself a salad, an entree, and a dessert. Being a good cook, she knows how to make lots of different dishes of each type. Her goal is to go a whole year (365 days) without having a meal that duplicates two of the three items on a previous meal. For instance, she can make the same salad on two different days, but then the entrees and the desserts on those days must be different. What is the minimum total number of dishes (salads plus desserts plus entrees) that Adina needs to know how to make in order to achieve her goal? Explain why this number suffices and why a smaller number is not enough. (Note: the number of dishes of each type does not need to be the same.)

5. Let's call a positive integer n nice if one can split the set {1,2,3, ..., n} into two disjoint sets S and T with the property that the average of the elements of S is an element of T and the average of the elements of T is an element of S. For instance, 4 is a nice integer: the split {1,3}, {2,4} works.

  1. Which even integers are nice?
  2. Show that prime numbers are never nice.

6. Suppose all the integers have been colored red, green, and blue (one color per integer), such that:

  1. the sum of any two green integers (equal or unequal) is blue;
  2. the sum of any two blue integers (equal or unequal) is green;
  3. the negative of any blue integer is green and vice versa.

How many such colorings are there in which 2007 is green? Describe them and prove that there are no others.

7. On a table in a dark room are n hats numbered 1 through n. A group of k Mathcampers, with k < n, comes into the room, and each camper puts on one of the hats at random, without seeing its number. The campers go back outside, where they can see each other's hats (but not their own). Each student announces to the others the largest and the smallest number that he or she can see. What is the probability that all the students can now deduce their own hat numbers with no further communication,

  1. if n=6, k=5?
  2. in general, as a function of n and k?

8. An ant is placed on an n-inch ruler. It chooses one of two directions randomly, with each direction equally likely, and starts walking in that direction. Every time it reaches an inch mark, a malicious human spins it around so that it loses all sense of direction and again heads off at random. If the ant reaches the 0 mark on the ruler, the human turns it around and makes it go back. When the ant reaches n, the human lets it go. If the ant was initially placed at the k inch mark, what is the average number of inches it will have to walk until it is set free, as a function of k and n?

9. Here is a solitaire game that you can play. Start with a deck of n cards, and mix them so that some are face up and some are face down. Lay them out in a straight line. A turn in this game consists of removing a face-up card and flipping over its immediate neighbors, if any. (Two cards are not considered immediate neighbors if there used to be a card between them that is now gone.) You win if you succeed in removing all n cards. Describe all initial configurations of cards that are winnable, explain how to win them, and show that all other configurations are unwinnable.

10. Hallie is teaching geometry to Warren. She tells him that the three medians, the three angle bisectors, and the three altitudes of a triangle each meet at a point (the centroid, incenter, and orthocenter respectively). Warren gets a little confused and draws a certain triangle ABC along with the median from vertex A, the altitude from vertex B, and the angle bisector from vertex C. Hallie is surprised to see that the three segments meet at a point anyway! She notices that all three sides measure an integer number of inches, that the side lengths are all distinct, and that the side across from vertex C is 13 inches in length. How long are the other two sides?



Problems 1, 2, 4, 5, 6, 7, and 8 copyright Mark Krusemeyer.