All problems

A rigid planar shape must be moved around a right-angled corner in a hallway of width 1. What is the largest possible area of such a shape? Gerver's sofa has area about 2.2195. Prove that no shape with larger area can make the turn.

There are $n$ men and $n$ women, and each person ranks all members of the other group. A perfect matching is unstable if some man and woman both prefer each other to their assigned partners. Prove that a stable matching always exists, and give an algorithm that finds one in $\mathcal{O}(n^2)$ time.

Let $x_1,x_2,x_3,\dots$ be any infinite sequence with every $x_i$ equal to $+1$ or $-1$. Prove that for every $C$ there are positive integers $k$ and $d$ with $\left|{\sum }_{i=1}^k{x}_{id}\right|>C.$

You have 2 identical eggs and a building with 100 floors. There is an unknown threshold floor such that an egg breaks when dropped from that floor or above and survives from any floor below, and an egg that survives can be reused. What is the smallest number of drops that guarantees finding the…

Find the exact value of ${\sum }_{n=1}^{\infty }\frac{1}{n^2}=1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}+\cdots$ and prove that your answer is correct.

A stream of $n$ items is read once, from left to right. Using only a constant number of memory words, find an item that occurs more than $n/2$ times, assuming such an item exists. Then explain how a second pass can check whether a majority exists at all.

Königsberg had four land masses, two river banks and two islands. One island was joined to each bank by two bridges, the other island to each bank by one bridge, and a seventh bridge joined the two islands. Is there a walk that crosses every bridge exactly once? More generally, which connected…

A singly linked list either ends in a null pointer or eventually loops back into itself. Using $\mathcal{O}(1)$ extra memory and time linear in the number of nodes, decide whether it has a cycle, and if it does, find the first node on the cycle and the cycle length.

Using only a compass and an unmarked straightedge, can one construct in finitely many steps a square with exactly the same area as a given circle? Prove your answer.

Given an array of $n$ integers, some possibly negative, find a contiguous subarray with the largest sum. For example, in $[-2,1,-3,4,-1,2,1,-5,4]$ the best subarray is $[4,-1,2,1]$ with sum 6. Give an $\mathcal{O}(n)$ algorithm and prove it correct.