1. There are 26 students at Logic Camp; 18 of them always tell the truth and the other 8 always lie. Of course, everyone at the camp knows who is who. One day, n campers are sitting in a circle. Each of them says: "Exactly one of my two neighbors is a liar." For what values of n > 2 is this possible? (See note 1.)
2. Several Mathcampers are hiking on Mount St. Helens when it suddenly starts raining. Luckily, some of them brought umbrellas, so they huddle in groups, with one umbrella per group. Within each group, the space under the umbrella might not be split equally. Any person who ends up with less than a quarter of an umbrella will get soaked. If two thirds of the groups are larger than 5 people, prove that at least a quarter of the hikers will get soaked. (See Note 2.)
3. The increasing sequence 1,3,4,9,10,12,13,... consists of all those positive integers which are powers of 3 or sums of distinct powers of 3. Of the first googol (10100) terms in the sequence, how many are powers of 3?
4. Every Spanish citizen is assigned an ID that consists of eight digits (0–9) and one letter. The letter is not assigned randomly: only 23 letters are used, which correspond to the 23 possible remainders on dividing the eight-digit number by 23. The letter acts as a "check symbol": if somebody makes a mistake when entering the number, chances are that the resulting ID will not be valid (the letter will be wrong) and the error will be detected right away.
5. The diagonals of quadrilateral ABCD intersect in point E. Given that |AB|=|CE|, |BE|=|AD|, and ∠AED = ∠BAD, determine the ratio |BC| / |AD|. (|XY| means the length of the segment from point X to point Y.)
6. A cat is trying to catch a mouse in each of the labyrinths (a), (b), and (c):
The cat starts at vertex C and the mouse at vertex M. The cat and the mouse take turns moving, with the cat moving first; each move is from a vertex to an adjacent vertex. If the cat ever gets to the same vertex as the mouse, it catches the mouse. In which (if any) of the three labyrinths can the cat catch the mouse, assuming the mouse makes no stupid moves? (A "stupid move" is a move after which the cat has a strategy that guarantees it can catch the mouse, where it didn't have one before.)
7. Consider an infinite chessboard, with numbers in each square. Initially all of the numbers are 0, except for a single 1 on a black square. Go through a series of steps: at every step, replace each number with the sum of its four neighbors (all numbers get replaced simultaneously).
8. Amy, Brian, and CoScott are playing a game, with Dana as the judge. Dana puts eight stickers (four red and four blue) in a bowl, then draws two at random for each player and sticks them to their foreheads. Each player can see both of the other players' stickers, but not his or her own or the two left in the bowl. Dana then asks Amy whether she knows the colors of her stickers. If Amy does not, Dana asks Brian whether he knows his colors, then CoScott, then Amy again, then Brian again, and so on. The game ends if one of the players can logically deduce his or her colors. What is the probability that the game ends on one of Amy's turns? Brian's? CoScott's? What is the probability that it never ends at all?
9. You are in charge of a project to design a card-shuffling machine for a deck of n cards, initially ordered from 1 to n. The machine will repeatedly take the top card and re-insert it randomly into the deck, so that all positions for the inserted card are equally likely (including the top and bottom). The machine can keep track of where each insertion happens, so that at every point the current order of the cards is known. Your job is to tell the machine in advance when it should stop shuffling. In your instructions, you can refer to the current state of the deck (e.g. "Go until card 2 is on the bottom, then go until card n-1 is third from the top, then shuffle 5 more times, then stop"). You want to program the machine so that when it stops, all permutations of the deck will be equally likely. What instructions should you give to the machine? (Be sure to prove that these instructions really do lead to all permutations being equally likely.) With these instructions, how many insertions will it take, on average, until the machine stops?
10. Asaf is investigating rectangles drawn in the plane such that every vertex has integer coordinates. (The sides of the rectangle need not be parallel to the coordinate axes.) He considers two rectangles to be the same if one can be obtained by rotating and/or translating the other.
Problems 1 and 7 copyright Mark Krusemeyer.