Given an initial sequence $a_1, a_2, \ldots, a_n$ of real numbers, we perform a series of steps.
At each step, we replace the current sequence $x_1,x_2,\ldots,x_n$
with the sequence $|x_1-a|,|x_2-a|,\ldots,|x_n-a|$ for some number $a$ that can vary with each step.

(a) Prove that no matter what sequence we start with, there is some way to do steps to reach the sequence $0,0,\ldots,0$.

(b) * Determine (with proof) the maximum, over all sequences of length $n$, of the minimum number of steps required to reach $0,0,\ldots,0$.

State precisely what is wrong with the following proof:

claim: For all positive integers $n$, it is the case that, in any set $S$ consisting of n marbles, all marbles in $S$ are the same color.

proof: By induction on $n$.

Base case ($n=1$): in any set $S$ consisting of a single marble, it is trivially true that all marbles in $S$ are the same color, because only one marble is in $S$.

Induction step ($n>1$): Assume inductively that the claim is true for all sets of $n-1$ marbles. Under this assumption, we will prove the claim for all sets of $n$ marbles.

Let $S$ be any set of $n$ marbles. Denote the marbles in $S$ as $M(1), M(2), \ldots, M(n)$. That is, $M(1)$ is the first marble, and so on. Form two size-$(n-1)$ subsets of $S$ as follows:

\[S_1 = \{M(1), M(2), ..., M(n-1)\}\]
\[S_2 = \{M(2), M(3), ..., M(n)\}.\]


Since $S_1$ has $n-1$ marbles, by the inductive assumption all marbles in $S_1$ are the same color.
Thus, $M(1), M(2), ..., M(n-1)$ are the same color.

Likewise, all marbles in $S_2$ are the same color. Thus, $M(n-1)$ and $M(n)$ are the same color.

Thus, $M(1), M(2), ..., M(n)$ are all the same color.

You are given a subset $S$ of $\{1,2,...,100\}$ with the following property:
for every quadruple $u,v,w,x$ of distinct numbers in $S$, the sum of $u$ and $v$
differs from the sum of $w$ and $x$. Must the size of $S$ be at most fifteen?
Prove your answer.

In a set of objects, each is either red or blue, and each is either round or square. There is at least one red object, at least one blue object, at least one round object, and at least one square object. Prove that there exist two objects that are different both in color and in shape.

25 boys and 25 girls sit around a table. Prove that it is always possible to find a person that sits next to two girls (one on each side of the person).

I write two different numbers, one on each hand.

You choose one of my hands at random, I show you the number on that hand.

You now guess whether the number you've seen is larger than the number you haven't seen.

Find a strategy for guessing such that, no matter what two numbers I write, you have GREATER THAN a 50% chance of being correct.

You are to cut out some pieces of paper.

You must be able to place your pieces of paper on an 8x8 checkerboard so that they exactly cover the checkerboard, minus _any_ one square.

That is, once your pieces are cut, if I identify to you _any_ of the squares on the checkerboard, you must be able to arrange all your pieces of paper (flat, not folded) on the checkerboard so that:

a) the pieces of paper don't overlap
b) the pieces of paper don't cover any area outside the checkerboard
c) the pieces of paper cover all of the checkerboard except the square I chose

The problem: figure out how to do this with three pieces of paper.

For example, it is easy to see how to do this with 63 pieces of paper -- use 63 1x1 squares of paper. Or, 32 pieces --- use a 4x8 piece and 31 1x1 pieces...

Can you apply the distributive law forever?

(Lipton)

You have an arithmetic expression that adds and multiplies some variables.

For example $(x + y) * (z + a * (b + c ))$ .

You repeatedly reply the distributive law to sub-expressions of the expression.
For example, you could replace $a*(b + c)$ with $(a * b + b * c)$.

Prove that you cannot do this infinitely many times.
Bound the number of times you can, given an expression with $N$ variables.

Elizabeth has a secret hiding place where she presently has 35 coins, 38 baseball cards, and 39 pieces of candy. Her younger brother John has his own secret hiding place, but that does not prevent him from taking things from Elizabeth's (her place isn't as secret as she thinks). John always takes two items at a time, each of a different kind so that the number won't decrease too quickly, and he always adds one item of the third kind. On day, some time later, Elizabeth is shocked to find that all the items in her hiding place were of the same kind. Is it possible that it is all candy?

* There are 10 cities in Fatland. Two airlines control all of the flights between the cities. Each pair of cities is connected by exactly one one flight (the flight connects the cities in both directions). Prove that one airline can provide two traveling cycles with each cycle passing through an odd number of cities and with no common cities shared by the two cycles.

5 pirates discover 100 gold coins.

Their protocol for dividing the loot is as follows.

The most senior pirate proposes an allocation (how much each pirate should get). All the pirates vote. If at least half agree to the allocation, then that is the allocation.

Otherwise, the senior pirate is executed and the process is repeated with the remaining 4 pirates (the second-most-senior pirate proposes an allocation, etc.), then, if necessary, with the remaining 3 pirates, and so on. If it gets down to the least senior pirate, she gets it all.

Assuming that each pirate has the following priorities, what will the most senior pirate propose?

priorities, in order of importance:
1) stay alive
2) get as much gold as possible
3) kill as many other pirates as possible

The vertices of a cycle with n vertices are labelled with integers. A "flip" operation takes three consecutive vertices with labels $(x,y,z)$ where $y<0$ and replaces the labels, respectively, with $(x+y, -y, z+y)$.

Prove or disprove: it is possible to label the vertices so that the sum of the labels is positive, and then to do an infinite sequence of flip operations.

Example: $(2,-1,0) \rightarrow (1,1,-1) \rightarrow (0,0,1)$ (and then you are stuck)

You have n discs labeled 1,2,3,...,n (not necessarily in that order),
stacked one on top of each other (sort of like towers of hanoi).

The basic operation you can do on the stack is the following:
take some disc, and all the discs above it, and flip over that
part of the stack. For example, you can take the following
stack:

3
1
4
5
6
2
-

and, by applying the basic operation starting at disc 5, you can get

5
4
1
3
6
2
-

The problem has two parts:

(a) Show that, no matter how a stack of n discs starts out, by applying
the basic operation repeatedly, you can get the discs stacked in order
(1 on top, 2 next, ..., n on the bottom) using at most 2*n basic operations.

(b) Show that, for any n, there is some way to order a stack of n discs
so that no matter how you apply the basic operations, at least n
basic operations are required to get the discs ordered. (In this part,
you have to specify a particular order that requires at least n basic
operations, AND you have to prove that there is no sequence of less
than n operations that orders the stack.)

You have a truck and 300 gallons of gas. You have to transport the gas, using the truck, to sell at the market 100 miles away. Your truck can carry at most 100 gallons of gas at any time, and it consumes 1 gallon of gas for every mile it travels. What's the maximum amount of gas you can get to the market? You have spare containers so you can leave gas along the way and come back and pick it up if you like.

For example, you could load up your truck with 100 gallons of gas and drive to the market. But then when you got to the market, you'd have no gas to sell, and worse, you would be stranded and could not get back to the rest of your gas.

The audience chooses 5 arbitrary cards from a regular 52-card deck, and hands those 5 cards to a magician.

The magician chooses 4 cards, then reveals those 4 cards one at a time to his assistant.

The assistant promptly tells the magician what the 5th card is.

QUESTION 1: Figure out how to do this. That is, figure out how to choose, for any size-5 subset of cards, an ordering of 4 of those cards so that the assistant can tell just from the 4 cards and the ordering of those 4 cards what the 5th is.

QUESTION 2: What's the largest deck (more than 52 cards) that this trick can be done with, assuming that the magician will be given 5 cards and he must choose 4 to reveal?

The Hamming distance between two equal-length bit strings is the number of positions in which they differ.
For example, the distance between 0001 and 0101 is 1.
Suppose that, for some integer n, there are K n-bit strings
such that every pair has Hamming distance at least 101.
Prove that there are K n+1-bit strings such that every pair has Hamming distance at least 102.

N+1 couples attend a dinner. At the end of the dinner, one person (Alice) asks each other person to write down the number of distinct people with whom he or she shook hands at the dinner. Surprisingly, all numbers 0,1,2,...,2N are written down. Assuming that no person shook hands with their partner, how many people did Alice shake hands with at the dinner?

Check out the towers of hanoi puzzle. (http://en.wikipedia.org/wiki/Tower_of_Hanoi.)

Prove carefully that to move $N$ discs from one peg to another takes AT LEAST $2^N-1$ moves, NO MATTER HOW YOU MOVE THE DISCS (so long as you never put any disc on top of a smaller disk).

Prove that every triple $x,y,z$ of real numbers satisfies the inequality $|x|+|y|+|z|-|x+y|-|x+z|-|y+z|+|x+y+z| \ge 0$.

We are given an infinite set of rectangles in the plane, where each rectangle has vertices of the form $(0,0), (n,0), (0,m) (n,m)$ for positive integers $m$ and $n$ ($m$ and $n$ vary from rectangle to rectangle).

(a) Prove that there exist two rectangles in the set such that one contains the other.

(b) * Prove or disprove: there must exist an infinite sequence $R_1,R_2,\ldots,R_n,\ldots$ of rectangles in the set such that $R_1$ is contained in $R_2$, $R_2$ is contained in $R_3$, and so on. ($R_i$ is contained in $R_{i+1}$ for each $i$).

Can you label each square of an 8 x 8 checkerboard with an integer, so that no two squares are labeled with the same integer and no two adjacent squares (up, down, left, right) have labels that differ by 8 or more?

[probabilistic method]

Say a subset S of the non-negative integers is a pairwise cover if every positive integer i can be expressed as the sum of two integers in S. Define the density of S to be the function f where f(n) = |S intersect {1,2,...,n}|. Prove the existence of a pairwise cover whose density is o(n).

Hint: Generate a random S as follows: for each i independently, put i in S with some probability p(i). Show that with positive probability S is a pairwise cover with density o(n).

The positive integers are to be partioned into several subsets A1,A2,...,An such that, for i=1,2,...,n, if x is in Ai then 2x is not in Ai. What is the minimum value of n?

$2^N$ (that's two raised to the power of N, where N can be arbitrarily large) robots are arranged shoulder to shoulder facing outwards in a circle. Each robot has limited memory - it can only remember O(1) bits of information, and can give or receive information only to the robot to its left and the robot to its right. Time proceeds in discrete rounds. In each round, each robot can communicate O(1) bits of information with the two robots to its right and left. Specifically, in each round, each robot sends O(1) bits to each of his neighboring robots, and then receives whatever bits those robots sent him or her. No robot knows in advance how many robots there are in the circle.

Initially, all robots are in a "waiting" state, in which they do nothing. At some round t (unknown in advance), a person presses a "go" button on one of the robots, activating that robot. In the next round, that robot communicates to its neighbors, activating them, and (as the time steps pass), the activated robots communicate with their neighbors, activating them in turn. All communication and robot state-changes happen according to some protocol that has been agreed upon and programmed into the robots in advance. Then, at some later time, all robots simultaneously self-destruct. (No robot self-destructs before this time.)

The challenge problem is to determine a protocol to program the robots with so that this will happen, subject to the constraints outlined above.

An example that doesn't quite work would be:

(1) The first robot (the one that the person touches at time t), at time t+1 sends the message "1" to the robot to its right. At time t+2, that robot in turn sends the same message to the robot to its right, and so on. In general, each robot follows the protocol "if I receive message "1" from the left, then in the next round, I send the message "1" to my right."

(2) While this is happening, the first robot counts the time steps as they pass. When, eventually, it receives the message from its left, it knows that the number of robots is equal to the number of time steps passed. Let this number be $2^N$. In the next round, the robot sends the following message to its right: "self-destruct after $2^N-1$ rounds." The recipient waits a round, then sends the following message to its right "self-destruct after $2^N-2$ rounds. In general, if a robot receives a message of the form "self-destruct after X rounds", then, in the next time step, it sends the following message to its right: "self-destruct after X-1 rounds". Also, each robot, after receiving a message of the form "self-destruct after X rounds", starts counting the rounds as they occur, and self-destructs once X more rounds have passed.

That's an example protocol, and it would allow the robots to self-destruct simultaneously. But it doesn't fit the criteria outlined for two reasons. First, it requires each robot to communicate more than O(1) bits of information in some rounds. (To communicate a number as large as $2^N$ requires N bits, and N can be arbitrarily large.) Second, it requires each robot (when counting down) to remember up to N bits of information.

The protocol you design must require each robot to remember, and to communicate, only O(1) bits of information at any given time, no matter how large N is!

N pirates stand in a line, facing forward, so that
pirate $1$ sees pirates $2,3,\ldots,N$,
pirate $2$ sees pirates $3,4,\ldots,N$,
pirate $3$ sees pirates $4,5,\ldots,N$,
etc.

Each pirate wears a hat, each hat is either red or blue, but no pirate knows the color of his own hat. More specifically, each pirate knows only the colors of the hats on the pirates that he sees.

An executioner asks each pirate, in order (pirate $1$, then $2$, etc), what the color of the pirate's hat is. Everyone can hear the pirate's answer. If the pirate answers correctly, the executioner spares the pirate. Otherwise, executioner executes the pirate.

The pirates have anticipated that they might face this situation, and have agreed on a protocol for answering in advance. Their goal is to have as few pirates killed as possible. The puzzle is to figure out what is the best they can do. That is, describe a protocol that minimizes the worst-case number of pirates killed. (Here worst-case is over all possible ways of coloring the hats red or blue.)

For example, one protocol would be that pirate $1$, when asked the color of her hat, answers with the color of pirate $2$'s hat. Pirate $2$ hears what pirate $1$ says, thus learning her own hat color, and then when she is asked, she simply gives the correct answer. Continuing in this way, half of the pirates lives are saved (in the worst case). Assume that the pirates cannot tell if a pirate is executed or not.

Given a finite sequence {x1,x2,...,xN}, shifting the sequence gives the sequence {x2,x3,...,xN,x1}. Prove that for any sequence of N real numbers, if the sum of the numbers is non-negative, then one can shift the sequence some number of times so that the resulting sequence has the following property: for each K <= N, the sum of the first K numbers in the resulting sequence is non-negative.

There are 30 students arranged in a circle, with their eyes closed. The instructor places a hat on each student's head. 20 of the hats are black, 10 are white. The students then open their eyes. They can see each other student's hat, but not their own hat.

The instructor says "At least one of you is wearing a black hat."

He then gives the following instruction:

"Any student who has determined that his or her hat is black, please sit down."

Of course, no one sits down, because nobody can see his or her own hat. (There are no mirrors in the room, and the students are not allowed to discuss what they see.)

A minute later, the instructor repeats the previous instruction:

"Any student who has determined that his or her hat is black, please sit down."

No-one moves.

The instructor repeats this same instruction every minute for the next thirty minutes.

QUESTION 1: what happens, and when?

QUESTION 2: State exactly what new piece of information the instructor provided when he said "At least one student's hat is black." After all, this fact was already known by every student.

I randomly shuffle a deck of cards, then start turning over the cards one at a time. You stop me at a time of your choice. If the next card (the one on top of the remaining deck) is red (hearts or diamonds), then you win, otherwise you lose. (If you never stop me, you lose.)

Prove or disprove: there is a strategy that you can follow so that you will win with probability GREATER THAN 50% (assuming the deck is randomly ordered at the start).

A real number is assigned to each vertex of a finite connected graph so that the number on any vertex is the arithmetic mean (average) of the numbers on the adjacent vertices. Prove that all vertices' numbers are equal.

copied from http://www.eecs.umich.edu/~qstout/wellprob.html

A community is building a series of wells, trying to space them to meet the growing demand. Whenever a new family joins the community, the other families move a bit to make room for the new one, and everyone ends up with the same amount of room. Fortunately, they all live on the open interval (0,1). Unfortunately, the wells can't move.

Initially there is no well. At each stage i, i=1,2, . . . the ith family arrives and a new well is drilled at a point from the open unit interval (0, 1), so that there will be i wells. The goal is to insure that after the new well is drilled, each of the i open subintervals (0, 1/i), (1/i, 2/i), . . ., ((i-1)/i, 1) contains exactly one well.

For example, suppose the following choices were made.

Stage 1: first well is drilled at 0.7. Then certainly the interval (0, 1) , corresponding to a single family being in the community, has a well.
Stage 2: a second family arrives, and a second well is drilled at 0.3. Now each of (0, 1/2) and (1/2, 1) has a well.
Stage 3: third well is drilled at 0.4. Now each of the three families, residing in (0, 1/3), (1/3, 2/3), and (2/3, 1) , has a well.
Stage 4: Oops, there is no place to correctly drill the fourth well, because (1/4, 2/4) already has two wells and hence no matter where the fourth well is placed, one family will be without a well.
However, if the second well had been put at 0.2, then it would have been possible to complete the fourth stage.
Can this process go on forever? Provide a proof.

If it can go on forever, then how should the locations be chosen? (There may not be a unique answer.)

If it cannot go on forever, what is the longest it can go?