Back to my homepage. For some problems I have listed a very rough estimate of how long it took me to solve it.
• Find a 10 digit number using the digits 0-9 once each such that the substring of the first k digits is divisible by k, k = 1..10. (15 minutes)
• You play three independent games alternatingly against two opponents, A and B. You have a higher chance of beating A than beating B. To maximize your probability of winning two consecutive games, should you play against A, B, A or against B, A, B? (5 minutes)
• A rectangular tray of brownies has had a rectangular piece removed somewhere in the middle. What is an easy way to find a single straight-line cut that divides the remaining brownie into two equal areas? (1 minute)
• Take a long narrow strip of paper and cut two long parallel slits along it. Without cutting the paper, can you braid the three strands twice? source (I have not yet solved this problem.)
• What is the most number of chess pieces you can place on a chess board such that no two pieces are attacking the same number of pieces? (Created by Eric) (15 minutes)
• Using the digits 0 through 9 once each, and regular mathematical operations (*, -, +, /, ^), approximate e. Can be done to 1025 digits. (I did not attempt to solve this problem as I saw the answer with the problem.) Variant: use the integers 0 through 9 once each (i.e., digit concatenation not permitted)
• You are one of k prisoners in a jail with k indistinguishable cells arranged in a circle, so that each cell has exactly two neighbors. Every day the warden re-arranges which cells the prisoners are put in; each prisoner has no information about the rearrangement, even whether they are in the same cell from the previous day or any way of leaving information in their cell for the next occupant. Every night each prisoner can communicate a single bit of information to the occupant of the cell to your right by turning on or off their light; this is done simultaneously. Your goal is determine k. Before the first day you devise a strategy which is distributed to the other prisoners, who will follow your procedure exactly, and to the warden, who will choose re-arrangements to defeat your strategy if possible. Show a strategy which is guaranteed to get the correct value of k in finite time. (Note that your strategy can (and must) distinguish you from the other prisoners, but the other k - 1 prisoners are indistinguishable from each other.) (20 hours)

Variant by Eric (I don't know the answer): What if you are not one of the prisoners (so there is no distinguished prisoner), but each of the prisoners is given access to an independent source of random numbers? Is there a strategy that finds the correct value in expected value finite time?

• 100 people are standing in a row, and each is given either a black or white hat. Each person can see the hats of the people in front of them, but not their own hat or the hats of those behind them. Each person, starting from the back (the person who can see everyone else) publicly announces a guess for what color their hat is; no other communication is allowed. Devise a strategy so that at most one guess is incorrect. (1 minute)
• An arbitrary (typically infinite, not necessarily countably infinite) number of people are given hats, each either black or white. Each person can see every hat but their own. Each person privately guesses the color of their hat. Show there exists a strategy so that finitely many guesses are wrong. Formally: a person's observation is the set of people other than themself that has a white hat. A strategy is a tuple, one for each person, of functions that map that person's observation to either "black" or "white". Prove there exists a strategy so that the number of wrong guesses is necessarily finite in every case. (20 minutes)
• Suppose p is a prime and n > 1 is an integer such that n | p-1 and p | n3-1. Prove that 4p-3 is a perfect square. (15 minutes)
• Can the unit square [0, 1] x [0, 1] be colored with three colors so that any pair of points with the same color have a distance between them of at most one? (5 minutes)
• Suppose you have six distinct points in the interior of the unit disk. (1) Does there necessarily exist two of those points whose distance is less than 1? (2) Is it possible to add a seventh point which is the nearest neighbor of all six of those points? (10 minutes)
• Start with 1 and repeatedly multiply by a random real number chosen uniformly in the range [0, A]. What is the critical value C such that for A < C the product almost surely goes to zero and for A > C the product almost surely goes to infinity? (10 minutes)
• You have 13 coins which are indistinguishable except that possibly one of them is not the same weight as the others. You have another object whose weight is equal to that of the typical coin. You have a two-pan balance which, given some objects in the two pans, reveals whether the pans carry the same weight or otherwise which one is heavier. Show that you can identify whether there is a distinguished coin, and if so which one is the distinguished coin and whether it is heavier or lighter in three weighings. (15 minutes)
• You have 24 coins like in the previous puzzle. You have a three-pan balance that shows the relative weights of the three pans, unless all three are different in which case it explodes and ends the universe. You also have some string and tape. Show you can identify if there is a distinguished coin, which one it is, and whether it is heavier or lighter in three weighings. Without string and tape, show 15 coins is possible. (15 minutes)
• You have an urn with a red ball and a blue ball. Every step you draw a ball from the urn, return the ball and add another ball of the same color as the one you drew. After N steps, what is the probability the urn contains k red balls? (30 minutes)
• Consider a prime p and an integer b > 1. Write p in base b, and make a polynomial f(x) whose coefficients are the digits of p in base b (so that in particular f(b) = p). Prove that f(x) is irreducible over the integers. (requires complex analysis)
• Show there exists a proper subring of the real numbers R whose quotient field is R. (Extra: Classify all fields which has such a proper subring.) (Created by Brian Lawrence, first solved and generalized by Eric.) (requires field theory / theory of transcendental extensions)
• Using addition, subtraction, multiplication, and division, make the number 24 from the numbers 3, 3, 8, and 8.
• Does there exist a convex polyhedron where each face has a different number of sides? (1 minute)
• Let R be the reals, Z be the integers, and X = R / Z. Suppose S is a Lebesgue measurable subset of X such that S + x = S for all rationals x. Show that the measure of S is 0 or 1. (Created by Eric.)
• Characterize which polynomials p(x) with rational coefficients have an integer value p(n) for every integer n.
• Make a network of logic gates using only AND, OR, and NOT gates that takes three inputs A, B, and C and produces three outputs NOT A, NOT B, and NOT C. You are only permitted to use two NOT gates. In general, how many inputs can you negate using only k NOT gates? (30 minutes)
• There is an unknown infinite sequence (of real numbers, say) aj. A finite number of people each do the following: they privately choose positive integers j and learn the value aj of the sequence at position j. They can do this any number of times (including infinitely many times) with their choice of which positions to examine depending on the values they have seen so far. Afterwards, they privately guess the value aj of the sequence at some position j that they had not examined. Prove that their exists a strategy such that at most one of the people will guess incorrectly. Easier version: there is a countably infinite number of people, and at most finitely many may guess incorrectly.
• Six players play a game such that in each round, each player receives a different number of points from 1 to 6. The game ends when at the end of some round one of the players has reached at least 60 points. What is the maximum possible difference in the two highest point totals at the end of the game? (5 minutes)
• Given a real number x0 > 1, let xi+1 be a random number chosen in the interval [0, xi]. What is the expected value of the largest k with xk > 1? (10 minutes)
• How would you wrap a string around two nails in a wall in such a way that you can hang an object on the nails with the string, but if either nail is removed the object falls down? How do you wrap a string around n nails such that if you remove any one the object falls down?
• Consider a sphere of radius R, which has an infinite cylinder (whose axis passes through the sphere's center) removed from it. The resulting figure has a height of h (along the cylinder's axis). What is its volume? No calculus is required.
• Find all functions f(x) from positive reals to positive reals such that there exists a constant C such that for all x f(f(x)) = x^4 and f(x) <e; C x2. (45 minutes)
• Given that

1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + 1/7 - 1/8 + 1/9 - 1/10 + ...

equals ln(2), what is

1 - 1/2 - 1/4 + 1/3 - 1/6 - 1/8 + 1/5 - 1/10 - 1/12 + 1/7 - ...

equal to? (2 minutes)

• Consider a grid of squares with an even number of rows and columns colored with four colors such that each 2 by 2 subregion features all four colors. Prove that the corners are different colors. (5 minutes)
• I publicly announce two functions f and g from positive integers to positive integers. I privately choose a number x and privately tell Alice the value of f(x) and Bob g(x). I alternatingly ask Alice and Bob indefinitely if they know the value of x, and they publicly answer either "yes" or "no".
• Does there exist a choice of functions f and g such that, no matter what value of x was chosen, the value of x can be deduced by someone who hears Alice's and Bob's answers (and knows f and g but not f(x) or g(x))? (15 minutes)
• Consider a simple, undirected graph where each node has an odd degree, and each node is given one of two colors. We apply the following operation: the color of each node is simultaneously changed to the color that was the majority color of its neighbors. Show that if this operation is repeatedly applied, each node (non-uniformly) eventually either stabilizes to a single color or switches color after each application. (1 hour)
• For n > 3, prove that 1! + 2! + ... + n! is not a perfect square. (4 minutes)
• Prove there exists a constant C > 1 such that if a0 < a1 < ... < an are positive integers with n > 1 and 1 / a0 ... 1 / an forming an arithmetic sequence, then a0 > Cn. Requires some well-known number theory. (5 hours)
• Let S(n) be the least positive integer such that n2 cannot be written as a sum of S(n) squares. Prove that S(n) <e; n2 - 13 for n > 3 and that S(n) = n2 - 13 infinitely often.
• Consider a circle. By randomly chosing three points on its circumference, we can make a triangle. What is the probability that two such triangles chosen this way overlap? (5 minutes)
• You are trying to open a combination lock with n wheels, with each wheel having k positions. However, you know that one of the wheels (you don't know which one) is broken so that the lock will open so long as all of the other wheels are set correctly, regardless of the setting on the broken wheel. How many combinations do you need to try to open the lock? (10 minutes)
• John, James, and William are identical twins; John and James always lie and William always tells the truth. You run into one of them on the street and want to know if he is John (since John owes you money). What three-word question can you ask to determine if he is John? (1 minute)
• You have 9n identical coins, except that one is lighter than the others. You also have three two-pan balances, two of which are accurate, and the third of which produces arbitrary results. Determine which coin is the lightest in at most 3n+2 weighings. (20 minutes)
• If f(n) = n + floor(sqrt(n)), prove that for any positive integer n, the sequence n, f(n), f(f(n)), ... eventually contains a perfect square. (5 minutes)
• 2^N distinguishable people are each randomly given a white or black hat. Each person can see the other people's hats but not their own. Each person can then simultaneously either guess "white", guess "black", or pass. They collectively win if at least one person guesses a color, and everyone who guesses correctly names the color of their own hat. What strategy maximizes the chance of their winning?
• A list of n integers has a sum of 1. Prove that there is a unique index in the list such that the partial sums starting from that index (wrapping around to the beginning of the list if the end is reached) are all positive. (10 minutes)