Green Book Speedrun Any%
This page is my attempt at getting through all the problems in A Practical Guide to Quantitative Financial Interviews, otherwise known as the Green Book, by Xinfeng Zhou.
I'll assume you already have a copy. If not, you can find one at your nearest local quant event.
Timer begins now.
Chapter 1 – General Principles
Meh, who cares. I say just YOLO be yourself during the interview. It's worked for me so far at least. You'll be fine.
Chapter 2 – Brain Teasers
Screwy pirates
This is the classic pirate game problem, which is so mainstream, it even has a TED-Ed video on it. The interested reader can try out a much harder version of this problem, Project Euler #950.
Tiger and sheep
Statement
\(100\) tigers and \(1\) sheep are put on a magic island that only has grass. Tigers can eat grass, but they would rather eat sheep. Assume that:
- Each time, only \(1\) tiger can eat \(1\) sheep, and that tiger itself will become a sheep after it eats the sheep.
- All tigers are smart and perfectly rational and they want to survive.
Will the sheep be eaten?
Observe that at any point, there will always be exactly \(1\) sheep on the island.
If there were \(1\) tiger on the island, then it should eat the sheep. If there were \(2\) tigers, \(X\) and \(Y\), then neither would want to eat the sheep. If \(X\) ate the sheep, then \(Y\) would eat \(X\), and vice versa. For \(3\) tigers, the sheep will be eaten. The first tiger that gets to it will leave the other \(2\) in a stalemate as before.
You get the idea by now. \(100\) is even, so the sheep will not be eaten.
River crossing
This is the bridge and torch problem, and naturally it also has a TED-Ed video. You can check out a much harder version, Bridging the Gap from the 2023 ICPC World Finals. I haven't solved it.
Birthday problem
Statement
Andy and Benny know that Cindy's birthday is one of the following dates:
Cindy tells Andy the month of her birthday, and tells Benny the day of her birthday.
Andy says: "I don't know Cindy's birthday; Benny doesn't know it either."
After hearing Andy, Benny replies: "I didn't know Cindy's birthday at first, but now I know."
Andy smiles and says: "Now I know it too!"
So when is Cindy's birthday?
This is a variant of the wonderful Cheryl's Birthday. The dates are different, so let's go through it together.
First, how can Andy confidently claim that Benny doesn't know Cindy's birthday? He must know that Benny wasn't given a day that could've uniquely identified Cindy's birthday.
If Cindy's birthday were Jun 7, Benny would immediately know which date it was, as none of the other dates are on the 7th. So if Andy was given Jun, he wouldn't be able to make that claim. Thus, we can eliminate Jun from our list of dates:
Similarly, because of Dec 2, we can eliminate Dec from our list of dates as well:
Now we move on to Benny. He now knows Cindy's birthday, so his given day must uniquely identify it from the remaining dates. This means it's not Sep 5 or Mar 5; both are on the 5th:
Andy, having gone through the same logic, now also knows Cindy's birthday. So it couldn't be Mar, since there are two dates left.
Therefore, Cindy's birthday is Sep 1.
Card game
Statement
A casino offers a card game involving a standard deck of \(52\) cards. You turn over a pair of cards each time:
- If both are black, they go to the dealer's pile.
- If both are red, they go to your pile.
- If one is black and one is red, they are discarded.
The process is repeated until you have gone through all \(52\) cards.
If you have strictly more cards in your pile, you win \(100\) dollars. Otherwise, you get nothing.
How much would you be willing to pay for this game?
Sigh. Okay. You got me. I spent way longer on this than I should have.
Let:
- \(X\) be the number of pairs where both cards are black;
- \(Y\) be the number of pairs where both cards are red;
- \(Z\) be the number of pairs where one card is red and one card is black.
Since there are exactly \(26\) black cards and \(26\) red cards, we have:
Thus, \(X = Y\), which means… wait, you'll always tie. So you'll actually never win this game.
Don't make a fool of yourself. Pay exactly \(0\) dollars for this game.
Burning ropes
Obligatory Wikipedia article and TED-Ed video.
Defective ball
Obligatory Wikipedia article and TED-Ed video. But FYI, I don't think I could've derived this on the spot. Then again, if you're using classic puzzles like this as a legitimate hiring procedure, you're doing it wrong.
Trailing zeros
Statement
How many trailing zeros are there in \(100\) factorial?
See Legendre's formula.
Horse race
Statement
There are \(25\) horses, each of which runs at a constant speed. All horses' speeds are unique.
Each race can have at most \(5\) horses. What is the minimum number of races needed to identify the \(3\) fastest horses?
This has apparently become folklore; there's not even a Wikipedia article for this one.
Split the \(25\) horses into \(5\) groups of \(5\) horses, \(A\), \(B\), \(C\), \(D\), and \(E\). Let \(A_1 > A_2 > A_3 > A_4 > A_5\) be the horses from race \(A\) in order (\(A_1\) is fastest, \(A_5\) is slowest), and do the same for the other \(4\) races.
Then we race \(A_1\), \(B_1\), \(C_1\), \(D_1\) and \(E_1\). Without loss of generality (and for the sake of convenience), suppose \(A_1 > B_1 > C_1 > D_1 > E_1\).
Now we can eliminate all horses that have (directly or indirectly) lost to at least \(3\) horses, since they could never be in the top \(3\). This already reduces our candidates all the way down to \(6\) horses: \(A_1\), \(A_2\), \(A_3\), \(B_1\), \(B_2\), and \(C_1\).
Obviously \(A_1\) is the fastest horse, so all we need to do is race the remaining \(5\) horses to determine the second and third fastest horses.
\(7\) races in total. It's pretty clear you can't do better than that.
Infinite sequence
Statement
Solve for \(x\) if \(x^{x^{x^{...}}} = 2\).
Haha, real funny. Just replace the infinite power tower with itself, so \(x^2 = 2\), which means \(x = \sqrt{2}\). Note that \(x = -\sqrt{2}\) doesn't work because I said so. Mathematicians would kill you over this, by the way.
Box packing
Statement
Can you pack \(53\) bricks of dimension \(1 \times 1 \times 4\) into a \(6 \times 6 \times 6\) box?
The book's solution implicitly assumes the bricks are axis-aligned. If you don't do this, you will waste many hours of your life and ruin your entire day. Not… speaking from experience.
Anyway:
..x...
...x..
x...x.
.x...x
..x...
...x..
...x..
..x...
.x...x
x...x.
...x..
..x...
x...x.
.x...x
...x..
..x...
x...x.
.x...x
.x...x
x...x.
..x...
...x..
.x...x
x...x.
..x...
...x..
x...x.
.x...x
..x...
...x..
...x..
..x...
.x...x
x...x.
...x..
..x...
Each brick occupies exactly \(1\) marked x. But there are only \(52\) of them, so \(53\) is impossible.
I'm totally fine. Yeah.
Calendar cubes
Statement
You have two cubes. Place a single digit on each of the faces so that you can arrange the numbers 01, 02, …, 31 using the two cubes. You can switch the order of the cubes if needed.
Try taking the problem statement at face value and you will quickly run into a logical contradiction: there just aren't enough faces on each die. The key "observation" is that you can rotate a \(6\) to get a \(9\). So \(\{0, 1, 2, 5, 7, 8\}\) and \(\{0, 1, 2, 3, 4, 9\}\) is one such valid numbering.
I like it, despite the cheap trick.
Door to offer
Statement
You are facing two doors. One leads to your job offer and the other leads to the exit. In front of each door is a guard. One guard always lies and the other always tells the truth. You can only ask one guard one yes/no question.
What should you ask to get the job offer?
This is a variant of Knights and Knaves. The usual setting has one door leading to heaven and one door leading to hell, though being unemployed is arguably hell in this job market.
Message delivery
Statement
Andy wants to communicate with his boyfriend Benny via a messenger service. Andy's documents are sent in a box, but unfortunately, the messenger service isn't secure: anything inside an unlocked box will inevitably get lost during delivery, including any locks placed inside one.
Andy and Benny each have exactly one high-security lock-and-key pair: Andy owns pair \(A\) and Benny owns pair \(B\). Lock \(A\) can only be opened with key \(A\), and lock \(B\) can only be opened with key \(B\).
How can Andy securely send his documents to Benny?
Lovers and their weird schemes.
Andy places his documents inside the box and locks it with his lock \(A\). The box is delivered to Benny, who then locks it again with his lock \(B\). The box is delivered back to Andy, who unlocks his lock \(A\) with his key \(A\). The box is delivered one last time to Benny, who can now open it with his key \(B\).
Why they couldn't just meet in person, I have no idea.
Last ball
Statement
A bag has \(20\) blue balls and \(14\) red balls. Each time, you randomly take out \(2\) balls (each ball has an equal probability of being taken).
You do not put the \(2\) balls back. Instead:
- If both balls have the same color, you add a blue ball to the bag;
- If they have different colors, you add a red ball to the bag.
You repeat this process until exactly \(1\) ball remains.
What color is the last ball? What if the bag has \(20\) blue balls and \(13\) red balls instead?
It's always parity this, parity that, eh?
For \(20\) blue balls and \(14\) red balls, observe that the number of red balls is always even, no matter what you do. Therefore, at the end, the last ball must be blue. Similarly, for \(20\) blue balls and \(13\) red balls, the last ball must be red.
Light switches
Statement
There is \(1\) light bulb inside a room and \(4\) switches outside. All switches are currently off and exactly \(1\) switch controls the light bulb. You may turn any number of switches on or off any number of times you want.
How many times do you need to go into the room to determine which switch controls the light bulb?
The canonical version that I know of involves \(3\) switches controlling \(3\) light bulbs, but this is no different.
Of course you can do it in \(2\) visits, but of course the interviewer won't be impressed. Here's how to do it in \(1\):
- Turn the first light switch on and wait a few minutes.
- Turn the first light switch off, turn the second light switch on, and wait a few minutes.
- Turn the second light switch off, immediately turn on the third light switch, and run inside.
Now, observe the state of the light bulb inside the room. If it's on, then obviously it's the third light switch. Otherwise, touch the light bulb. If it's very hot and your hands burn (ow oof owie), it's the second light switch. If it's just slightly warm, it's the first light switch. Lastly, if it's cold, it must be the fourth light switch.
Update: Okay, so the book's intended solution is to treat on/off and hot/cold as \(2\) separate things you can check for, which is how you obtain \(4\) separate states. I don't think I could physically bring myself to touch a light bulb that's on, so I'm good, thanks. This problem has a lot of unstated assumptions, anyway.
Quant salary
Statement
\(8\) quants from different banks are getting together for drinks. They are all interested in knowing the average salary of the group. Nevertheless, being cautious and humble individuals, everyone prefers not to disclose his or her own salary to the group. Can you come up with a strategy for the quants to calculate the average salary without knowing other people's salaries?
Narrowly avoided throwing up upon reading the statement. Anyway, I've heard of this before.
The first guy, we'll call him Andy, punches in a random number, \(X\), on his calculator. He then adds his salary to \(X\) and passes the calculator to the next person. Each subsequent person adds their own salary to the running total, which has been obfuscated by \(X\). The last person returns the calculator back to Andy, who can subtract \(X\) and divide by \(8\) to get the average salary.
If you want to be extra secure, each person can offset the running total by their own random number and cancel them out later, but \(1\) should be sufficient.
Coin piles
Statement
You are blindfolded. There are \(1000\) coins on the floor. \(980\) of the coins are tails up and the other \(20\) coins have heads up. Can you separate the coins into two piles to guarantee both piles have equal number of coins that are heads up? You cannot determine a coin's side just by touching it, but you are allowed to turn over any number of coins.
Obligatory TED-Ed video.
Mislabeled bags
Statement
You are given three bags of fruits. One has apples in it, one has oranges in it, and one has a mix of apples and oranges in it. Each bag has a label on it (apple, orange or mixed). Unfortunately, your manager tells you that all bags are mislabeled.
Find the correct label of each bag by taking out the minimum number of fruits. You can take out any number of fruits from each bag.
I legitimately remember solving this when I was 10. Does that mean I only need to be smarter than a 10-year-old to pass a quant interview? That's somewhat reassuring.
Take out \(1\) fruit from the bag labeled as mixed. If it's an apple, we know this is the all-apples bag, and if it's an orange, we know this is the all-oranges bag. Knowing the correct identity of one bag is enough for us to identify the remaining bags as well.
Wise men
Statement
A sultan has captured \(50\) wise men. There is a glass inside the room, which is currently bottom-side-up.
Each minute, he calls one of the wise men into the room. Then, they can either turn the glass over or do nothing. The wise men will be called randomly.
At any point, one of the wise men can claim that all wise men have been inside the room at least once. If his claim is correct, everyone goes free. But if not, everyone dies.
The wise men are allowed to communicate only once before they are imprisoned in separate rooms. Design a strategy that lets the wise men go free.
Label the wise men \(M_1, M_2, \ldots, M_{50}\). We'll elect \(M_1\) to be the leader.
For \(i > 1\), when \(M_i\) is called into the room:
- If the glass is bottom-side-down, he does nothing.
- If the glass is bottom-side-up and he has not turned the glass over, he turns it over.
- If the glass is bottom-side-up and he has previously turned the glass over, he does nothing.
When \(M_1\) is called into the room:
- If the glass is bottom-side-up, he does nothing.
- If the glass is bottom-side-down, he turns it over.
Eventually, \(M_1\) will turn the glass over \(49\) times. At that point, he can make the claim, and everyone will go free.
Clock pieces
Statement
A clock with numbers \(1\) to \(12\) fell off the wall and broke into three pieces. The sums of the numbers on each piece are equal. What are the numbers on each piece? Assume the pieces don't have weird shapes.
Uhhh…
So each piece has sum \(26\). A little trial and error gives us the following pieces: \(\{11, 12, 1, 2\}\), \(\{5, 6, 7, 8\}\), and \(\{3, 4, 9, 10\}\). Yeah, they're not consecutive, but if you actually draw it out, the shapes are quite reasonable.
Missing integers
Statement
Suppose we have \(98\) distinct integers from \(1\) to \(100\). What is a good way to find the \(2\) missing integers?
Use a hash table.
So, when can I get started?
Counterfeit coins I
Statement
There are \(10\) bags with \(100\) identical coins in each bag. In all but \(1\) of the bags, each coin weighs \(10\) grams. All the coins in the counterfeit bag weigh either \(9\) or \(11\) grams.
You have an exact digital scale. Find the counterfeit bag in only \(1\) weighing.
Take \(1\) coin from the first bag, \(2\) coins from the second bag, \(3\) coins from the third bag, and so on. Pretending these are all real coins, we can determine their total weight. Take the absolute difference between this and the scale's actual reading to determine which bag is counterfeit.
Glass balls
Statement
You are holding \(2\) glass balls in a \(100\)-floor building. When an (unbroken) ball is thrown out of the window, if the floor number is less than \(X\), the ball won't break. Otherwise, it will.
Determine \(X\) while minimizing the number of drops needed in the worst case.
Let \(n\) be the minimum number of drops needed in the worst case. Define:
We drop the first glass ball at floor \(a_1\), then floor \(a_2\), and so on, until it breaks.
Let \(a_i\) be the first floor where the glass ball breaks. Since it survived floor \(a_{i - 1}\), we can now use the second glass ball to sequentially check all floors from \(a_{i - 1} + 1\) to \(a_i - 1\), inclusive. The way we set these numbers up ensures that at most \(n\) drops are needed, no matter which \(i\) it is.
All we need to do now is to find an \(n\) that guarantees we cover all floors. In other words, just find the smallest \(n\) such that \(a_n \geq 100\). So \(n = 14\) is sufficient and optimal.
Note that the above strategy works as-is when there are exactly \(105\) floors. For the original problem, if you need to drop the glass ball from a nonexistent floor, just stand on a very high ladder on the top of the building and drop the ball from there instead. Or, you know, just cap it at \(100\) floors. That works too.
Matching socks
I've set a harder version of this problem on Codeforces before.
Handshakes
Statement
You are invited to a welcome party with \(25\) other team members. Each person shakes hands with some (or none) of the other people at the party.
Can you say with certainty that there are at least \(2\) people present who shook hands with exactly the same number of people?
Essentially, given a simple graph with \(26\) nodes, can we guarantee that there exist \(2\) nodes with the same degree?
Yep. Suppose each node had a unique degree between \(0\) and \(25\) inclusive. There are \(26\) nodes in total, so each number from \(0\) to \(25\) is used exactly once. But the sum of these is \(325\), which is odd. This contradicts the handshake lemma (heh).
Update: Upon paraphrasing the original statement, I accidentally omitted the fact that everyone already shook hands with you, which trivializes the problem even further. Meh, this version is cooler anyway.
Have we met before?
Statement
Show that, if there are \(6\) people at a party, then either at least \(3\) people met each other before the party, or at least \(3\) people were strangers before the party.
Oops, it's Ramsey's theorem. \(R(3, 3) = 6\). Suck it.
Ants on a square
Statement
There are \(51\) ants on a square with side length of \(1\). If you have a glass with a radius of \(\frac{1}{7}\), can you always put your glass at some position on the square that encompasses at least \(3\) ants?
Divide the square into a \(5 \times 5\) grid of cells. Each ant belongs to exactly one such cell (if there's an ant on the border, you can gently nudge it). By the pigeonhole principle, there exists a cell with \(3\) ants. By Pythagoras, a circle of radius \(\frac{1}{7}\) can just about encompass the entire cell, so we are done.
Counterfeit coins II
Statement
There are \(5\) bags with \(100\) coins in each bag. A coin can weigh \(9\) grams, \(10\) grams or \(11\) grams. Each bag contains coins of equal weight, but you do not know which type of coins a bag contains.
You have an exact digital scale. How many times do you need to use the scale to determine which type of coin each bag contains?
Same idea as before; only \(1\) weighing needed.
Take \(1\) coin from the first bag, \(3\) coins from the second bag, \(9\) coins from the third bag, \(27\) coins from the fourth bag, and \(81\) coins from the fifth bag. Pretend that all the coins weigh \(9\) grams and determine what their total weight would be. Then, just interpret the difference between this and the actual reading as a ternary number.
Prisoner problem
Obligatory TED-Ed video.
Division by 9
Statement
Given an arbitrary integer, come up with a rule to decide whether it is divisible by 9 and prove it.
…What??? I learned this when I was 8???
Chameleon colors
Statement
A remote island has \(13\) red chameleons, \(15\) green chameleons and \(17\) blue chameleons. Each time \(2\) chameleons with different colors meet, they change their colors to the remaining one. For example, if a green chameleon meets a red chameleon, they both change their color to blue. Is it ever possible for all chameleons to become the same color?
Observe that at any point, one color's count is \(0\) modulo \(3\), another is \(1\) modulo \(3\), and the remaining one is \(2\) modulo \(3\). There are \(45\) chameleons in total; it is impossible to achieve the desired counts of \(45\), \(0\), and \(0\).
Coin split problem
Statement
You have a pile of \(1000\) coins. Initially, your total score is \(0\).
In one operation, you choose a pile with at least \(2\) coins and split it into two piles. If there are \(x\) coins in the first pile and \(y\) coins in the second pile, your total score increases by \(x \cdot y\).
Repeat the process until each coin is in a separate pile. What is the maximum total score you can obtain?
The original statement kind of spoils the fun, so I've added a slight layer of obfuscation.
In fact, no matter what you do, your total score is always the same.
For each operation where you split a pile into two piles of sizes \(x\) and \(y\), you can really think of \(x \cdot y\) as representing the number of pairs of coins where one coin is taken from each pile.
Then, for each pair of coins, say \(C_1\) and \(C_2\), consider the first (and only) time they get separated. That pair will contribute exactly once to the overall total score. But this is true for any pair, so the answer is simply the number of pairs of coins in total, which is \(499\,500\).
Chocolate bar problem
Statement
A chocolate bar consists of \(48\) pieces arranged in a grid of \(6\) rows and \(8\) columns. In one operation, you choose one rectangle and break it into two smaller rectangles. You may only break a rectangle along the grid lines.
What is the minimum number of operations required to break the chocolate bar into \(48\) separate pieces?
Again, no matter what you do, you will always need the same number of operations.
This one is even more straightforward: each operation increases the total number of rectangles by exactly \(1\), so exactly \(47\) operations are required.
Race track
Statement
You are on a one-way circular race track. There are several gas cans placed at different positions on the track; the total amount of gas in these cans is enough for your car to travel exactly one complete lap.
Your car's gas tank is initially empty; assume it has unlimited capacity. You can start your car at any position on the track, and you can pick up gas cans along the way to fill up the tank.
Is it always possible to choose a starting point on the track so that your car can travel one complete lap?
Let's do a trial run first. Fill your car's tank with a lap's worth of gas and begin your journey from an arbitrary position, picking up gas cans along the way as you go. We'll keep track of how much gas is left in the tank throughout the lap.
After the trial run is complete and everything is reset, find the position where you had the least amount of gas left, and begin the real journey there. You can be sure that you won't run out of gas.
Irrational number
Statement
Prove that \(\sqrt{2}\) is irrational.
I know Hippasus did over 2000 years ago and, well, let's just say it didn't really work out for him. Pass.
Rainbow hats
Statement
\(7\) prisoners have the chance to be set free tomorrow. The executioner will put a hat on each prisoner's head. Each hat is in one of the \(7\) colors of the rainbow; the hat colors are assigned at the executioner's discretion. Each prisoner can see the hat colors of the other \(6\) prisoners, but not his own. They cannot communicate with others in any form.
Each prisoner writes down what he thinks his own hat color is. If at least \(1\) prisoner correctly guesses the color of his hat, they will all be set free. Otherwise, they will all be executed.
Can the prisoners come up with a strategy that guarantees freedom?
Yes. Label the colors from \(0\) to \(6\), and the prisoners from \(0\) to \(6\).
Prisoner \(i\) assumes the sum of all the prisoners' hat colors (including his own) is \(i\) modulo \(7\), and writes down what his hat color would have to be for that assumption to be true. Exactly one of the prisoners' assumptions will actually be true, so ggwp.
Chapter 3 – Calculus and Linear Algebra
Oh thank goodness, we're done with the brain teasers.
Limits and Derivatives
Statement
What is the derivative of \(y = \ln(x)^{\ln(x)}\)?
Let \(w = \ln(x)\) and \(z = \ln(y) = w \cdot \ln(w)\), so \(y = e^z\). Then:
Statement
Without calculating the numerical results, which is larger, \(e^\pi\) or \(\pi^e\)?
I remember seeing this on TikTok; apparently you're supposed to do this in your head. Insane.
Note that \(\ln(x)\) is increasing for \(x > 0\), so it suffices to compare their logarithms instead:
Let \(g(x) = \frac{x}{\ln(x)}\). We wish to compare \(g(\pi)\) and \(g(e)\).
Let's try computing \(g^\prime(x)\) first and see what we get:
Thus, \(g^\prime(x) > 0\) for \(x > e\), so \(g(x)\) is increasing for \(x > e\). Therefore, \(g(\pi) > g(e)\), which means \(\boxed{e^{\pi} > \pi^{e}}\).
Statement
What is the limit of \(\frac{e^x}{x^2}\) as \(x \to \infty\)?
Just whack L'Hôpital:
Statement
What is the limit of \(x^2 \ln(x)\) as \(x \to 0^+\)?
Express \(x^2 \ln(x)\) as \(\frac{\ln(x)}{x^{-2}}\) and whack L'Hôpital again:
Integrals
Statement
What is the integral of \(\ln(x)\)?
Whack integration by parts. Let \(u = x\), \(v = \ln(x)\). Then:
Statement
What is the integral of \(\sec(x)\) from \(x = 0\) to \(x = \frac{\pi}{6}\)?
I genuinely had a stroke solving this.
We'll use integration by substitution. Let \(u = \sin(x)\). Then:
Therefore:
I don't wanna talk about it.
Statement
Two infinitely long cylinders, each with radius \(1\), are perpendicular to each other and intersect at their centers. What is the volume of the intersection?
Literally NO ONE ASKED–
Label the cylinders \(C_1\) and \(C_2\) and let them intersect at the origin, \((0, 0, 0)\). Also let \(C_1\) be parallel to the \(x\)-axis and \(C_2\) be parallel to the \(y\)-axis.
Thus, the equations for \(C_1\) and \(C_2\) are:
Consider the two-dimensional slice of their intersection at some specific \(z\) level. The corresponding \(x\) and \(y\) coordinates must satisfy:
So the area of this slice is exactly \(4(1 - z^2)\).
Integrating from \(z = -1\) to \(z = 1\) gives us:
Statement
The snow started falling some time before noon at a constant rate. A snow plow was sent at noon to clear the road. The plow removes snow at a constant volume per minute. By \(1\) PM, it had moved \(2\) miles, and by \(2\) PM, it had moved \(3\) miles. When did the snow begin to fall?
Let \(f(t)\) be the height of the uncleared snow \(t\) hours after noon. The snow falls at a constant rate, so \(f(t) = a + bt\) for some unknown constants \(a\) and \(b\).
Now let \(g(t)\) be the distance the snow plow has traveled \(t\) hours after noon. We know \(g(0) = 0\), \(g(1) = 2\), and \(g(2) = 3\). What else can we say?
Obligatory calculus whacking ensues. Let \(\Delta t\) represent a very small difference in time. We can approximate what the snow plow removes as a cuboid with length \(g(t + \Delta t) - g(t)\), height \(f(t)\), and width \(w\), where \(w\) is a constant (it's just the width of the road). The volume of this cuboid is:
Since the plow removes the same volume of snow over a fixed time period, there must exist a constant \(X\) such that for all \(t \geq 0\):
Therefore:
Now \(g(0) = 0\), which means:
Next, we have \(g(1) = 2\) and \(g(2) = 3\), so:
Lastly, \(a > 0\), because you can't have negative snow, and \(b > 0\), because you can't have snow rising into the sky, which means \(\frac{a}{b} > 0\).
Thus, \(\frac{a}{b} = \frac{\sqrt{5} - 1}{2}\), so the snow started falling that many hours before noon, at around \(\boxed{\text{11:23 AM}}\).
Wonderful problem.
Statement
If \(X \sim N(0, 1)\), what is \(\mathbb{E}[X\, |\, X > 0]\)?
Yeah sure, why not:
We'll compute the indefinite integral first. Let \(u = \frac{-x^2}{2}\). Then:
Plug that back into the previous equation:
Fun fact: in the First Edition, or at least in the digital copy that I have been pirating using for convenience, the answer was off by a factor of \(2\). But I just checked my (PHYSICAL and LEGAL) copy of the Second Edition, and the error has indeed been fixed.
Partial Derivatives and Multiple Integrals
Statement
Calculate \(\displaystyle \int_{0}^{\infty} e^{\frac{-x^2}{2}}\,dx\).
Fortunately, the pdf of the normal distribution is still fresh in my mind.
We know that \(\displaystyle \int_{-\infty}^{\infty} \frac{e^{\frac{-x^2}{2}}}{\sqrt{2 \pi}}\,dx = 1\). The bell curve is symmetric, so \(\displaystyle \int_{0}^{\infty} \frac{e^{\frac{-x^2}{2}}}{\sqrt{2 \pi}}\,dx = \frac{1}{2}\).
Thus:
Important Calculus Methods
Statement
What is \(i^i\)?
Obligatory Stand-up Maths video. Don't worry, we'll go through it together.
First, Euler's formula tells us that:
Thus, we dubiously conclude that:
Therefore:
Just don't think about the infinitely many other answers we could've had instead.
Statement
Prove that \((1 + x)^n \geq 1 + nx\) for all real \(x > -1\) and for all integers \(n \geq 1\).
This is a much weaker form of Bernoulli's inequality, where \(n\) is restricted to the positive integers. We'll proceed by induction.
The base case \(n = 1\) is trivially true. Now suppose the hypothesis holds for \(n = k\). Then:
and we are done.
Statement
Compute \(\sqrt{37}\) to \(3\) decimal places.
I deviously pull out the calculator that I smuggled in and punch in the numbers.
The interviewer falls to their knees.
…
Let's use the Babylonian method, starting with \(6\):
One more iteration for good measure:
I promise I did this by hand.
Statement
Can you explain some root-finding algorithms to solve \(f(x) = 0\)? Assume \(f(x)\) is a differentiable function.
No, I won't. Thank you for your time.
Statement
What is the distance from the origin to the plane \(2x + 3y + 4z = 12\)?
I know you can just whack the distance-to-plane formula, but that feels like cheating, and I'd rather re-derive it.
Let \(A\) be the projection of the origin \(O\) onto the plane. Note that \(\overline{OA}\) is parallel to the normal vector of the plane, \((2, 3, 4)\), so:
for some real \(t\).
But \(A\) is on the plane, so:
Ordinary Differential Equations
Statement
Solve the ODE \(y^{\prime} + 6xy = 0\), given that \(y(0) = 1\).
We have:
We are given that \(y = 1\) for \(x = 0\), so \(C = 0\).
Therefore:
Statement
Solve the ODE \(y^{\prime} = \frac{x - y}{x + y}\).
Let \(u = x + y\). Then:
Statement
Solve the ODE \(y^{\prime} + \frac{y}{x} = \frac{1}{x^2}\) where \(x > 0\), given that \(y(1) = 1\).
We have:
We are given that \(y = 1\) for \(x = 1\), so \(C = 1\), which means:
Statement
Solve the ODE \(y^{\prime\prime} + y^{\prime} + y = 0\).
Let \(r_1\) and \(r_2\) be the roots of the equation:
Observe that \(y = e^{r_1 \cdot x}\) and \(y = e^{r_2 \cdot x}\) are both solutions to the ODE.
Unfortunately, \(r_1\) and \(r_2\) are complex:
Complex numbers are not real, so we'd like to find a way around this.
Let \(\alpha = \frac{-1}{2}\) and \(\beta = \frac{\sqrt{3}}{2}\), so \(r_1 = \alpha + \beta i\) and \(r_2 = \alpha - \beta i\).
Then, by Euler's formula:
Now let \(\displaystyle y_1 = \frac{e^{r_1 \cdot x} + e^{r_2 \cdot x}}{2}\) and \(\displaystyle y_2 = \frac{e^{r_1 \cdot x} - e^{r_2 \cdot x}}{2 i}\).
Note that \(y_1\) and \(y_2\) are also solutions to the ODE.
Furthermore, from \((1)\) and \((2)\), we can derive that:
Finally, any linear combination of \(y_1\) and \(y_2\) is a solution to the ODE, and in fact, it can be proven that all solutions to the ODE are linear combinations of \(y_1\) and \(y_2\).
Therefore, the general solution for the ODE is:
Statement
Solve the ODE \(y^{\prime\prime} + y^{\prime} + y = 1\).
Let \(z = y - 1\). Note that \(z^{\prime} = y^{\prime}\) and \(z^{\prime\prime} = y^{\prime\prime}\).
Thus, \(z\) satisfies \(z^{\prime\prime} + z^{\prime} + z = 0\), and… oh.
Statement
Solve the ODE \(y^{\prime\prime} + y^{\prime} + y = x\).
You get the idea.
Linear Algebra
Statement
There are three random variables \(X\), \(Y\), and \(Z\). The correlation between \(X\) and \(Y\) is \(0.8\), and the correlation between \(X\) and \(Z\) is also \(0.8\). What is the maximum and minimum correlation between \(Y\) and \(Z\)?
First, without loss of generality, we'll normalize \(X\), \(Y\), and \(Z\) so that they all have mean \(0\) and variance \(1\), which means:
Thus, we want to find the maximum and minimum of \(\mathbb{E}[YZ]\).
Maximizing \(\mathbb{E}[YZ]\) is trivial: just let \(Z = Y\), then \(\mathbb{E}[YZ] = \mathbb{E}[Z^2] = 1\). We cannot do better than this, since \(\mathbb{E}[YZ] = \text{corr}(Y, Z) \leq 1\).
To find the minimum value of \(\mathbb{E}[YZ]\), we will magically and miraculously1 consider the random variable \(T = X - 0.625Y - 0.625Z\).
Note that \(\text{Var}(T) \geq 0\), so \(\mathbb{E}[T^2] - (\mathbb{E}[T])^2 \geq 0\). But \(\mathbb{E}[T] = 0\), which means \(\mathbb{E}[T^2] \geq 0\).
Now, let's expand \(\mathbb{E}[T^2]\):
Therefore,
We can prove this bound is tight. Again, using magic, consider \(Z = 1.6X - Y\).
Clearly \(\mathbb{E}[Z] = 0\); next we show \(Z\) also satisfies \(\mathbb{E}[Z^2] = 1\) and \(\mathbb{E}[XZ] = 0.8\) :
So what is the value of \(\mathbb{E}[YZ]\)? Great question:
Done.
Statement
How would you design an algorithm for linear least squares regression?
Hoo boy, I really had to brush up on my basic linear algebra for this one.
Let \(A \in \mathbb{R}^{m \times n}\) be a matrix (\(m > n\)) and \(b \in \mathbb{R}^{m}\) be a target vector. We wish to find a vector \(x \in \mathbb{R}^{n}\) such that \(A x\) is as "close" to \(b\) as possible. Specifically, we wish to minimize:
over all vectors \(x \in \mathbb{R}^{n}\).
Let \(\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\) be the columns of \(A\), so \(A = [\mathbf{v}_1\,\mathbf{v}_2\,\ldots\,\mathbf{v}_n]\). To prevent any future headaches, we'll assume these columns are linearly independent (if they aren't, your model has redundant variables!).
Then, letting2 \(x = [c_1\,c_2\,\ldots\,c_n]^T\), we have:
Thus, the range of \(A\) (i.e., the set \(\{A x : x \in \mathbb{R}^n\}\)) is just the span of \(\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\}\).
Now, for \(w \in \text{span}(\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\})\), the value of \(\|w - b\|^2\) is minimized when \(w\) is the projection of \(b\) onto the range of \(A\). In other words, \((w - b)\) must be perpendicular to \(\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\), which means:
or, more succinctly:
Therefore, we wish to find an \(x\) such that:
Next, we're gonna do what's called a pro gamer move. The Gram–Schmidt process allows us to represent the range of \(A\) as a basis \(\{\mathbf{u}_1, \mathbf{u}_2, \ldots, \mathbf{u}_n\}\), where all the vectors are unit vectors and are orthogonal (perpendicular) to each other. In fact, we can take things further and use this process to express \(A\) itself as:
where \(\mathbf{v}_i = \mathbf{u}_1 r_{1,i} + \mathbf{u}_2 r_{2,i} + \ldots + \mathbf{u}_i r_{i,i}\) and \(r_{i,i} \neq 0\) for all \(1 \leq i \leq n\).
Let \(Q \in \mathbb{R}^{m \times n}\) be the matrix on the left and \(R \in \mathbb{R}^{n \times n}\) be the matrix on the right.
Substituting into \((1)\), we get:
The above transformation makes use of two facts:
- \(Q^TQ\) equals the identity matrix, since all columns in \(Q\) are unit vectors and are orthogonal to each other.
- \(R^T\) is invertible, since it's a triangular matrix and all diagonal entries are nonzero.
Now, we're pretty much done. Computing \(Q^T b\) is easy, as it's just a matrix multiplied by a vector. Solving the resulting equation is also easy: since \(R\) is upper triangular, we can just use back substitution.
Statement
Find the eigenvalues and eigenvectors of \(A = \begin{bmatrix}2 & 1 \\ 1 & 2 \end{bmatrix}\).
Oh yeah, this is more my speed:
Eigenvectors for \(\lambda = 1\):
Eigenvectors for \(\lambda = 3\):
Statement
There are three random variables \(X\), \(Y\), and \(Z\). The correlation between \(X\) and \(Y\) is \(0.8\), and the correlation between \(X\) and \(Z\) is also \(0.8\). What is the maximum and minimum correlation between \(Y\) and \(Z\)?
Hey wait a minute!
Statement
You are given a random number generator that generates samples from \(N(0, 1)\), and a constant \(\rho\) (\(-1 \leq \rho \leq 1\)). How can you generate two random variables \(X\) and \(Y\) such that \(X, Y \sim N(0, 1)\) and the correlation between \(X\) and \(Y\) is \(\rho\)?
Let \(\alpha = \rho\) and \(\beta = \sqrt{1 - \rho^2}\). Use the random number generator to independently generate \(X \sim N(0, 1)\) and \(Z \sim N(0, 1)\), then let \(Y = \alpha X + \beta Z\).
First note that \(Y\) is a linear combination of independent random variables that are normally distributed, so \(Y\) itself is also normally distributed. In particular, its mean is \(0\) and its variance is \(\alpha^2 + \beta^2 = 1\), so \(Y \sim N(0, 1)\).
The correlation between \(X\) and \(Y\) is:
and we are done.
Chapter 4 – Probability Theory
Coin toss game
Statement
Andy and Benny are playing a coin toss game. Andy has \(n + 1\) fair coins and Benny has \(n\) fair coins. What is the probability that Andy will have more heads than Benny if both flip all their coins?
Andy puts one of his coins in his pocket and flips his remaining \(n\) fair coins first. Then, Benny flips all his \(n\) fair coins.
By symmetry, the probability that Andy has flipped strictly more heads than Benny is exactly equal to the probability that Andy has flipped strictly fewer heads. If Andy has more heads, then flipping the coin in his pocket won't make a difference; he'll still have more heads than Benny. Likewise, if he has fewer heads, then flipping the coin in his pocket won't make a difference either; at most he can only tie with Benny.
What about if they have the same number of heads? Then the final coin really does make a difference, and Andy has a \(\frac{1}{2}\) probability of coming out on top.
Combining these cases, the probability that Andy has more heads than Benny is exactly \(\boxed{\frac{1}{2}}\).
Card game
Statement
A casino offers a simple card game involving a standard deck of \(52\) cards. Cards are valued in the order: \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\), \(10\), \(J\), \(Q\), \(K\), \(A\).
At the start, the deck is randomly shuffled. You pick a card from the deck and the dealer picks another one from the remaining cards. What is the probability that your card has a strictly higher value?
Again, by symmetry, the probability that your card has a strictly higher value is exactly equal to the probability that your card has a strictly lower value. Hence, we only need to focus on the probability that both cards have the same value.
After you pick your card, \(3\) of the remaining \(51\) cards have the same value as yours, so the probability that both cards have the same value is just \(\frac{3}{51}\), or \(\frac{1}{17}\).
Thus, the probability that your card has a strictly higher value is:
Drunk passenger
Statement
A line of \(100\) airline passengers are waiting to board a plane. Each passenger is holding a ticket for one of the \(100\) seats on that flight.
The first person in line is drunk, so they will randomly pick a seat out of all possible seats instead of their assigned one. All the other passengers are sober, so they will go to their assigned seat unless it is already occupied; in that case, they will randomly choose an unoccupied seat instead.
You are the last person in line. What is the probability that you end up in your assigned seat?
I've heard of this before, but I don't remember the slick way to solve it. So here's my not-so-slick approach instead.
Let \(P_n\) be the answer for \(n\) airline passengers (\(n \geq 2\)), so we're looking for \(P_{100}\).
The drunk passenger (we'll call him Andy) has a \(\frac{1}{n}\) probability of picking his own seat. If that happens, then hey, crisis averted, everyone will end up in their assigned seat. On the other hand, Andy also has a \(\frac{1}{n}\) probability of picking your seat. If that happens, then too bad, you are definitely not ending up in your assigned seat.
Next, consider when Andy picks a seat that is neither his nor yours; say he picks Benny's seat. Let \(k\) be the number of remaining passengers when Benny boards the plane, including Benny himself (so \(2 \leq k < n\)). Then, we can pretend that Benny's assigned seat was actually Andy's originally assigned seat, and make Benny the drunk one instead (sorry, Benny). Now the problem simply reduces to \(P_k\).
Therefore, for all \(n \geq 2\), we have:
We can see that, actually, \(P_n = \frac{1}{2}\) for all \(n \geq 2\), so the answer to the original problem is just:
N points on a circle
Statement
Pick \(N\) independent and uniformly random points \(P_1, P_2, \ldots, P_N\) on the circumference of a circle (\(N \geq 2\)). What is the probability that they all lie within a semicircle?
We can assume no two points are diametrically opposite, as those cases contribute an infinitely thin probability-slice-thing anyway.
Note that all points lie within the same semicircle if and only if there exists a point \(P_i\) such that, after drawing the diameter through \(P_i\) and dividing the circle into two halves, all points (excluding \(P_i\)) lie in the same half. Because we can, we'll call such a point a yummy point.
Further observe that, out of all \(N\) points, either exactly \(2\) of them are yummy, or none of them are. Therefore, the probability that all \(N\) points lie within a semicircle is equal to the expected number of points that are yummy, divided by \(2\).
Now, for each \(i\), we consider the probability that \(P_i\) is yummy. Consider some other point \(P_j\) where \(j \neq i\). Then, the remaining \(N - 2\) points must lie in the same half as \(P_j\). Thus, the probability that \(P_i\) is yummy is:
Summing up over all points \(P_i\) and dividing by \(2\), we reach the final answer of:
Poker hands
Statement
Consider a game of poker involving a standard deck of \(52\) cards. Each player gets a hand of \(5\) cards.
What is the probability of getting a four of a kind (\(4\) of the \(5\) cards have the same rank)?
What is the probability of getting a full house (\(3\) cards of one rank and \(2\) cards of another rank)?
What is the probability of getting a two pair (\(2\) cards of one rank and \(2\) cards of another rank)?
See Wikipedia. Cheers.
Hopping rabbit
Statement
A rabbit sits at the bottom of a staircase with \(n\) stairs. The rabbit can hop up \(1\) or \(2\) stairs at a time. How many different ways are there for the rabbit to reach the top of the stairs?
Epic LeetCode problem.
Screwy pirates 2
Statement
\(11\) pirates decide to protect their treasure box with locks. To open the treasure box, all locks need to be opened.
Each lock can be opened by more than one key, but each key can only open one lock. Keys are to be created and distributed among the pirates.
The pirates want to design a system where at least \(6\) pirates are needed to open the treasure box. Additionally, any \(6\) pirates can open the treasure box.
What is the minimum number of locks needed in such a system? How many keys would each pirate carry?
The first step is to ensure that any \(6\) pirates can open the treasure box. So for each lock on the treasure box, we should distribute its keys to exactly \(6\) of the \(11\) pirates. Any fewer than that, and we'd have a subset of \(6\) pirates that can't open the treasure box. Any more than that, and we'd be making our system less secure, as we'll see shortly.
Next, we need to ensure that any subset of \(5\) pirates cannot open the treasure box. So each subset of \(5\) pirates must be discriminated by at least one lock.
Further note that each lock can only discriminate at most one subset of \(5\) pirates, since its keys are distributed to exactly \(6\) pirates. Therefore, the minimum number of locks needed is simply the number of subsets of \(5\) pirates, which is:
A pirate won't receive the key for a lock if they belong to the subset of pirates the lock discriminates. Hence, the number of locks a pirate cannot open is the number of subsets of \(5\) pirates that include said pirate, which is:
So each pirate carries \(462 - 210 = \boxed{252}\) keys.
Chess tournament
Statement
A chess tournament has \(2^n\) players with different skill levels. It is organized as a single-elimination tournament: only the winners of each round proceed to the next. The match-ups in each round (except for the final) are decided at random. Assume that when two players meet in a game, the player with the higher skill level always wins.
What is the probability that the two players with the highest skill level meet in the final?
Assign each player one of two colors: white if said player is competing under the first finalist's subtree, and black if said player is competing under the second finalist's subtree. Note that the color assignments are uniformly distributed.
The probability that the two players with the highest skill level meet in the final is then the probability that they are assigned different colors.
The total number of color assignments is:
The number of color assignments where the two players are assigned different colors is:
So the desired probability is:
Application letters
Statement
You're sending job applications to \(5\) firms. You have \(5\) envelopes and \(5\) cover letters personalized to each of these firms. Your young child randomly put letters into envelopes without realizing that the letters were personalized. What is the probability that all \(5\) letters are in the wrong envelopes?
First of all, keep the letters away from your child's reach. But anyway, we are looking for the number of derangements of size \(5\), which turns out to be \(44\). So the probability that all \(5\) letters are in the wrong envelopes is:
Birthday problem
Obligatory Wikipedia article and TED-Ed video.
100th digit
Statement
What is the \(100\)-th digit of \((1 + \sqrt{2})^{3000}\) after the decimal point?
Observe that, for any even integer \(n \geq 0\):
Let \(x = 1\) and \(y = \sqrt{2}\). Then, via binomial expansion, all terms in the left power are of the form \(\binom{n}{k}x^{n-k}y^k\), and all terms in the right power are of the form \(\binom{n}{k}x^{n-k}(-y)^k\). For even \(k\), both terms are integers. For odd \(k\), these terms cancel out. This proves our result.
Why do we care about this? Well, note that \((1 - \sqrt{2})^{3000}\) is positive and very small, so \(\left(1 + \sqrt{2}\right)^{3000}\) must be very slightly less than a positive integer. Thus, the \(100\)-th digit after the decimal point must be \(\boxed{9}\).
Okay, but just so we don't get rejected by the interviewer:
Cubic of integer
Statement
Let \(x\) be a random integer between \(1\) and \(10^{12}\) inclusive. What is the probability that \(x^3\) ends in \(11\)?
Sigh.
Trying all residue classes modulo \(100\) (by computer, not by hand, you heathen) reveals that only one of them gives a remainder of \(11\) when cubed, so the answer is \(\boxed{\frac{1}{100}}\).
Boys and girls
Statement
A company is holding a dinner for employees with at least one son. Cindy, a mother with two children, is invited. What is the probability that both children are boys?
Philosophical language issues aside, what we really care about is:
Statement
Your new colleague Darcy has two children. If you see her walking with one of her children and that child is a boy, what is the probability that both her children are boys?
Again, philosophical language issues aside, what we really care about is:
Now note that:
So the desired probability is:
Here, our derivation implicitly assumes that which child Darcy chooses to walk with is independent of whether they are a boy or a girl. This is fine and probably accurate for real life, but if, say, Darcy prefers to walk with girls rather than boys, we'd get a different result.
All heads?
I was lenient with the blatant non-binary erasure in the last one, because that's how it's usually presented anyway. But the original statement for this one was hella sexist and I'm not here to endorse a decades-old societal norm, especially when there's a much more intuitive formulation that avoids it entirely.
Statement
A game is played with a fair coin. In each round, you repeatedly flip the coin and stop once it lands on heads.
As you play more and more rounds, what happens to the proportion of heads you see overall?
Let \(n\) be the number of rounds you've played so far, and \(X_i\) be the number of coin flips in the \(i\)-th round. Then, the proportion of heads you've seen so far is:
Treating \(X_1, X_2, \ldots, X_n\) as observations of the same random variable \(X\), the above proportion is precisely the reciprocal of the sample mean, \(\frac{1}{\overline{X}_n}\).
As \(n\) approaches infinity, \(\overline{X}_n\) approaches \(\mathbb{E}[X] = 2\), so the proportion of heads you see overall approaches \(\frac{1}{2}\).
In fact, treating the coin flips as-is and ignoring how they're partitioned into different rounds, you would expect the proportion of heads to approach \(\frac{1}{2}\) anyway. Oops.
Unfair coin
Statement
You are given \(1000\) coins. \(1\) coin has heads on both sides. The remaining \(999\) are fair coins. You randomly choose a coin and flip it \(10\) times. It shows head every single time.
What is the probability that the coin you chose was the unfair one?
One-liner:
Fair probability from an unfair coin
See Wikipedia.
Dart game
Statement
Andy throws two darts at a dartboard, aiming for the center. The second dart is further from the center than the first. If Andy throws a third dart (still aiming for the center), what is the probability that the third dart is further from the center than the first? Assume Andy's skill level remains constant.
Label the darts \(D_1\), \(D_2\), and \(D_3\), respectively, and order them by increasing distance to the center. Of the \(3! = 6\) possible orderings, \(3\) of them have \(D_1\) before \(D_2\), and \(2\) of them have \(D_1\) before \(D_2\) and \(D_1\) before \(D_3\).
So the probability that the third dart is further from the center than the first is \(\boxed{\frac{2}{3}}\).
Birthday line
Statement
At a movie theater, a whimsical manager announces that she will give a free ticket to the first person in line whose birthday is the same as anyone who has already bought a ticket. You can choose where you want to be in the line. You don't know anyone else's birthday.
Assume all birthdays are uniformly distributed, and there are \(365\) days in a year. Which position in line gives you the highest chance of getting the free ticket?
Suppose you are the \(n\)-th person in line (\(n \geq 2\)). Then, in order for you to get the free ticket, everyone in front of you must have distinct birthdays, and your birthday must match one of theirs. So the probability that you get the free ticket is:
Now note that:
Thus:
The smallest \(n\) for which \(n^2 - n \geq 365\) is \(n = \boxed{20}\), which is indeed our answer.
Dice order
Statement
We throw \(3\) dice one at a time. What is the probability that we get \(3\) strictly increasing values?
One-liner:
Monty Hall problem
Amoeba population
Statement
There is \(1\) amoeba in a pond. After \(1\) minute, the amoeba either dies, stays the same, splits into \(2\), or splits into \(3\), each occurring with equal probability. Its offspring, if it has any, behave under the same rules, independent of other amoebas.
What is the probability that the amoebas die out?
Let \(p\) be the probability that the amoebas die out, given that there is currently \(1\) amoeba.
After \(1\) minute, one of the following occurs:
- The amoeba dies. Then the probability of extinction is \(1\).
- The amoeba stays the same. Then the probability of extinction is \(p\).
- The amoeba splits into \(2\). Treating each of the offspring as an independent population, the probability that both go extinct is \(p^2\).
- The amoeba splits into \(3\). Similarly, the probability of extinction is \(p^3\).
Putting everything together, we get:
Clearly \(p = 1\) is a root of the above equation, but disturbingly, there is another positive root: \(p = \sqrt{2} - 1\). So which one is it?
Let's try again. Define \(q_n\) to be the probability that, starting from \(1\) amoeba, the amoebas have not gone extinct after \(n\) minutes, so \(q_0 = 1\).
Then, we can do something like before to derive:
Let \(f(x) = \frac{1}{4}(x^3 - 4x^2 + 6x)\), so \(q_{n + 1} = f(q_n)\). Note that:
so \(f(x)\) is increasing.
Now let \(\alpha = 2 - \sqrt{2}\). Observe that if \(q_n > \alpha\), then \(q_{n + 1} = f(q_n) > f(\alpha) = \alpha\). But \(q_0 = 1 > \alpha\), so \(q_n > \alpha\) for all \(n\). Thus, this sequence cannot converge to \(0\), which means \(p \neq 1\). Therefore, the correct root is \(p = \boxed{\sqrt{2} - 1}\).
Update: The book doesn't even prove that \(p\) cannot be \(1\)!! What a scam!!
Candies in a jar
Statement
You are randomly taking out candies one by one from a jar that has \(10\) red candies, \(20\) blue candies, and \(30\) green candies. What is the probability that there is at least \(1\) blue candy and \(1\) green candy left in the jar when you have taken out all the red candies?
Let's say you continue taking candies until there are none left in the jar. Then, for the final candy, the probability that it's blue is \(\frac{20}{10 + 20 + 30} = \frac{1}{3}\), and the probability that it's green is \(\frac{30}{10 + 20 + 30} = \frac{1}{2}\). Clearly we don't need to care about the case where the final candy is red.
Now suppose the final candy was blue, and consider the last candy before that which was not blue. Then, conditioned on it being either red or green, the probability that it's green is \(\frac{30}{10 + 30} = \frac{3}{4}\). So this case contributes a probability of \(\frac{1}{3} \cdot \frac{3}{4} = \frac{1}{4}\).
Similarly, if the final candy was green, we'd get a probability of \(\frac{1}{2} \cdot \frac{2}{3} = \frac{1}{3}\). So the answer is:
Coin toss game
Statement
Andy and Benny take turns tossing a fair coin, with Andy going first. The sequence of heads and tails is recorded. If there is a head immediately followed by a tail, the game ends and the person who just tossed the tail wins. What is the probability that Andy wins?
Let \(P(x, y)\) be the probability that Andy wins, given that the game is not over yet, the current player is \(x \in \{A, B\}\), and the most recent outcome was \(y \in \{H, T\}\). The answer to the problem is thus \(\frac{1}{2}[P(B, H) + P(B, T)]\).
We have:
Solving this system of equations gives us:
So the answer is:
Russian roulette series
Statement
A single bullet is put into a \(6\)-chamber revolver. The cylinder is randomly spun so that each chamber is equally likely to be in the firing position. Two players take turns pulling the trigger without re-spinning the cylinder. The person who gets killed loses.
Should you play as the first player or the second player? What is your probability of losing?
I'm sort of not really in the mood to talk about death.
\(6\) is even, so both players have the same probability of losing, \(\boxed{\frac{1}{2}}\).
Statement
Now, let's change the rule slightly. We will spin the cylinder again after each turn.
Should you play as the first player or the second player? What is your probability of losing?
Ugh. Let \(p\) be the probability the first player loses. Then \(p = \frac{1}{6} + \frac{5}{6}(1 - p)\), since after the first turn, we can effectively assume the players have switched roles.
Solving this gives \(p = \frac{6}{11}\), so you have slightly better odds as the second player, losing with probability \(\boxed{\frac{5}{11}}\).
Statement
Instead of \(1\) bullet, now \(2\) bullets are randomly put into the revolver. Your opponent went first and survived the initial trigger pull. You are given the option to either spin the cylinder or do nothing. What should you do?
Can we not?
If you don't spin it, the probability of losing on your next turn is \(\boxed{\frac{2}{5}}\), since the previous chamber was safe. Otherwise, the probability of losing on your next turn is \(\boxed{\frac{1}{3}}\). Clearly you should spin it.
Statement
What if the \(2\) bullets are randomly put in \(2\) consecutive positions? If your opponent survived the first turn, should you spin the cylinder?
…
It's \(\boxed{\frac{1}{4}}\) vs. \(\boxed{\frac{1}{3}}\). Don't spin it.
Aces
Well, I'm glad there's no more of that.
Statement
\(52\) cards are randomly distributed to \(4\) players, with each player getting \(13\) cards. What is the probability that each of them has an ace?
Since the order in which we distribute the cards doesn't matter, we may as well distribute the \(4\) aces at the start. So suppose the first ace goes to Andy. Then:
- The probability the second ace goes to someone else (say, Benny) is \(\frac{51 - 12}{51} = \frac{13}{17}\).
- The probability the third ace goes to a new person (say, Cindy) is \(\frac{50 - 12 - 12}{50} = \frac{13}{25}\).
- The probability the fourth ace goes to a new person (say, Darcy) is \(\frac{49 - 12 - 12 - 12}{49} = \frac{13}{49}\).
So the answer is:
-
On a serious note, these numbers come from reverse engineering the correlation matrix, which must be positive semidefinite (whatever that means). ↩
-
I used to be grossed out by this "lazy" transpose shorthand, but now I think it's totally understandable. ↩