Brainteasers

These are often used in techy interviews. This is a collection of the ones that are amusing.

There are 25 horses with fixed speeds. You can race 5 horses at a time to determine an ordering on their speeds. What is the fewest number of races that you need to determine the top 3 horses?

4 wine glasses are on a turntable. You are blindfolded and are allowed to feel 2 glasses and change their orientations. When you let go, if all the glasses are up or all down, the audience applauds and you win. Otherwise, an adversary spins the turntable and you repeat the feeling and toggling step. Find the minimum $n$ such that there exists a strategy that is guaranteed to win after at most $n$ steps.

Extension: Now replace the wine glasses with baked bean tins, so you can’t feel the orientation of them. What is $n$ now?

Extension: Now go back to wine glasses, but there are now $N$ glasses on the turntable arranged in a circle, and at each step you are allowed to feel and toggle $k$. What is $n$ as a function of $N$ and $k$?

There is a chessboard covered in coins that are either heads or tails. An adversary places a ruby under one of the squares. Fred is shown where the ruby is. Fred must flip exactly one of the coins on the board. Fred now leaves the room and Eric enters. Eric has not seen the ruby or the configuration of coins beforehand. Eric and Fred need to decide on a coding so that Eric can deduce which square the ruby is under.

See a 3b1b video for the answer.

A rectangle is formed from many sub-rectangles, show that if each sub-rectangle has at least one side being integer length then the big rectangle also has one side of integer length.

Take a function $f:R^2\to R$. Suppose that given any square of points $a,b,c,d\in R^2$, we have that $f(a)+f(b)+f(c)+f(d)=0$. Prove that $f$ is zero everywhere.

Extension: Generalise the result to any fixed shape.

Find two infinite subsets of $A,B\subseteq N$ such that each $n\in N$ can be written uniquely as $a+b$ for some $a\in A$ and $b\in B$.

Take a point $(x,y)$ on the unit square $x,y\in [0,1]$, chosen uniformly at random, find the probability of $\lceil x/y\rceil$ being odd. Find the probability that $x/y$ rounded to the nearest integer is odd.

100 people are wearing hats, each has a number from 1 to 100 (numbers can repeat). They can see everyone else's hat but not their own. The challenge is they need to agree on a strategy such that everyone shouts a number at once and if at least one person shouts the number on their hat, you win.

100 people are in a line with either red or blue hats on. The guard goes from back to front and asks each person to say what colour their own hat is. What is the best strategy to maximise the number of correct hat guesses.

100 prisoners. Each day one is adversarially selected to enter a room containing a switch which they can toggle. Find a strategy so that one of the prisoners can declare that everyone has entered the room at least once.

A river with shores A and B has 6 islands (denoted by an x) with 13 bridges between them as shown below:

================================= A
          |    |    |
          x -- x -- x
          |    |    |
          x -- x -- x
          |    |    |
================================= B

Suppose that there is a storm, and each bridge has a 50% chance of collapsing in the storm. What is the probability that you can cross the bridge?

100 people get on a plane. Guy 1 forgets his ticket and sits in a random spot. Subsequent people will either sit in their allocated seat or sit in a random spot if their seat is taken. What is the probability that the last person to get on the plane gets his seat?

Check out a game called Hex: prove that there is no such thing as a draw in Hex. Extension: prove there exists a winning strategy for player 1.

You’re on a circular train with N carriages hooked up in a loop. You don’t know what N is. Each carriage has a light bulb you can turn on or off, and the bulbs start in an unknown configuration. How can you figure out N by walking around from carriage to carriage and manipulating the light switches?

1. Some quanty puzzles from George

I believe the origin of some of these is the Practical Guide to Quantitative Finance Interviews by Xinfeng Zhou.

There is one amoeba in a pond. After every minute, an amoeba may die, stay the same, split into two, or split into 3 - each with equal probability. All offspring behave identically and independently. What is the probability the population dies out?

A derangement is a permutation where all the elements move (i.e (2,3,1) is a derangement but (3,2,1) isn’t). What is the proportion of all permutations of n objects that are derangements, as n tends to infinity

You have a random number generator which generates uniform 0 to 1 numbers. You start pressing it repeatedly, adding up the numbers as you go. What is the expected number of values you generate before the cumulative sum exceeds 1?

Suppose you and I each have a RNG ~ Uniform(0, 1). We each generate a number and have the option to a) stick with it, or b) spin again (but you must then stick with the second number). Both of us do this process completely independently, and we have no knowledge of the other person's numbers or whether they re-rolled. Once we have both settled on a number, we compare them and the higher number wins. What's the best strategy?

You have two shuffled decks of 52 cards. You lay them both out in two rows. What is the expected number of columns that have the same card on the top and bottom rows.

There is an island with Chameleons. There are 13 reds, 15 greens and 17 blues. Two of a different colour can bang, at which point they both become the third colour. Is there a way that they can all become the same colour?