# Symmetry & Induction I will now go over 4 very common tricks. It's not always clear which one to use from the get-go - because often more of them can crack a brainteaser. So treat them as a toolbox, not a map. You can throw a few of them at any problem and see what sticks. --- ## Fix First When you have a few moving parts and interaction between them seems complex, fix one of the elements / iterations and see how others behave. Then go back and consider all the possibilities for the element / iteration you fixed. This one is very general - but it's worth trying if the problem seems overly complex and you're not sure where to start. Often this works well when it doesn't matter which element / iteration you chose to fix first. So e.g. in problems involving coin-flips, it often doesn't matter if you assume first flip is H or T - the situation is symmetric. Sometimes in math / physics textbooks they say 'without loss of generality, we'll assume X is Y' - because the actual choice doesn't matter - we can easily substitute any other choice. 'Fix First' is the brainteasers' equivalent of this. Let's see this in action: <div style="display: flex; justify-content: space-between; align-items: baseline;"> <h2>Interview Question</h2> <span style="font-size: var(--font-s); font-style: italic; color: #333;">Goldman Sachs</span> </div> --- You have a circular table, and you randomly place 3 legs on its circumference. What's the probability the table doesn't fall? <div> <button class="toggle-solution">Show Solution <i class="fa-solid fa-chevron-down"></i></button> <div class="solution"> For the table not to fall, the center of the circle must be inside the triangle formed by the three legs. To see why, imagine different setups: if the circle’s center is outside the triangle, all three legs end up on one side of the circle, and the table falls.<br><br>The interaction between legs seems complex: position of one leg impacts the possible positions of another. And wherever we fix the first leg, the problem remains the same - as the circle is symmetrical. So let's try to fix one leg and vary the position of the second leg to find where the third leg must go to keep the table stable. Fix the first leg at any point (call it A in the image below). Since the table is circular, the choice of A doesn’t matter. For the second leg, we only need to consider its position between points A and D. This is because the circle is symmetric, and placing the leg anywhere beyond D is like flipping the circle around the y-axis.<br><br>Now, once the second leg is placed, there is a specific area (the grey zone in the image) where the third leg can go without the table falling. Outside this area, all legs end up on one side of the circle, and the table falls. If the second leg is close to point A, the grey area is small. If it’s near point D, the grey area is almost half the circle. As the second leg moves randomly, the grey area ranges from 0 (when the second leg is at A) to 1/2 the circle (when the second leg is at D). On average, this safe zone is 1/4 of the circle. If the third leg is randomly placed around the circle, the chance it lands in the safe zone is 1/4.<br><br><img src="/static/images/q1img1.png" alt="q1img1" style="max-width: 100%;"> </div> </div> ## Symmetry Sometimes, it's not evident how the problem would change if the question asked for one binary outcome instead of the other. So for example even instead of odd / heads instead of tails / one player instead of the other... In such cases, take advantage of this symmetry: either see how the scenario I'm given is different from a symmetrical one, or see what probabilities are equal given this symmetry. **When to Use?** Ask yourself the question: would this problem change if they asked me for heads instead of tails / even instead of odd / one player instead of the other etc. If not, you might have a symmetrical setup. <div style="display: flex; justify-content: space-between; align-items: baseline;"> <h2>Interview Question</h2> <span style="font-size: var(--font-s); font-style: italic; color: #333;">Jane Street</span> </div> --- You roll a fair coin 9 times. What's the chance of getting an even number of heads? <div> <button class="toggle-solution">Show Solution <i class="fa-solid fa-chevron-down"></i></button> <div class="solution"> First thing to notice in a question like this is it seems like a symmetrical question. Meaning, it's not obvious how the problem would change if they asked us for number of tails instead of heads, or if they asked in how many ways you can get an even number of heads as opposed to odd. Often, when you see something like this - you can take advantage of the symmetry to shortcut the calculations.<br><br>To start with, let's see if anything would be different if they asked us for tails instead of heads? Well no, heads and tails are equally likely for a fair coin, so there's no difference between counting heads vs tails, apart from how you label them. Then we can conclude: $$P(\text{even H})=P(\text{even T})$$ Next, notice that to have an even number of heads, we must have an odd number of tails. This is because the sum of them has to be 9, so $k$ heads yields $9-k$ tails. if k is even $9-k$ is odd and the other way around. Try with a few examples to convince yourself. We therefore conclude that $$P(\text{even H})=P(\text{odd T})$$ $$P(\text{even T})=P(\text{odd H})$$ Lastly, notice that you can either get even or odd number of heads, so $$P(\text{even H})+P(\text{odd H})=1$$ Now, using the first expression we can substitute $P(\text{even H})=P(\text{even T})$: $$P(\text{even T})+ P(\text{odd H})=1$$ Then, using the second expression we know $P(\text{even T})=P(\text{odd H})$ so our expression becomes: $$2P(\text{odd H})=1$$ And therefore $P(\text{even H})=P(\text{odd H})=\frac{1}{2}$. To verify this, you can try to manually compute all the possibilities. Namely, to have an even number of heads in 9 flips, you can either have 0, 2, 4, 6 or 8 heads. For each of these, the number of ways for them to occur is the number of ways to pick $k$ elements out of 9 and label them H, i.e. $\binom{9}{k}$. Now for each of the flips we can only have H or T, so that in total there's $2^9$ possible arrangements. Then, the probability of getting $k$ heads is the number of arrangements with $k$ heads by the number of all possible outcomes, i.e. $\frac{\binom{9}{k}}{2^9}$. Now we can simply calculate and add up the probabilities for all possible $k$: $$k=0H:\,\binom{9}{0}=1$$ $$k=2H:\,\binom{9}{2}=36$$ $$k=4H:\,\binom{9}{4}=126$$ $$k=6H:\,\binom{9}{6}=84$$ $$k=8H:\,\binom{9}{8}=9$$ Adding all of them up, we get 256 possible scenarios with even H, or $2^8$. The probability is then $P(\text{even H})=\frac{2^8}{2^9}=\frac{1}{2}$, as we previously deduced. </div> </div> Now the following two tricks are **very useful**. They appear over and over again. They will crack open **a lot** of brainteasers. Whenever there are non-intuitive interactions, complex dynamic or situation changes between iterations, try one of the following two - they work very well. ## Forwards Induction Forward induction works as follows: - first ask: would this problem simplify with $n=1$ or small $n$ - where $n$ is number of iterations / participants. - if so, start with this - understand the dynamic. Gradually add participants / iterations until you notice the pattern. - extrapolate the pattern to the question you were asked. **When to Use?** Often this helps when situation changes between iterations (e.g. probabilities change), or there's a **large but finite** number of iterations / participants. There's usually too many possible outcomes to list manually. <div style="display: flex; justify-content: space-between; align-items: baseline;"> <h2>Interview Question</h2> <span style="font-size: var(--font-s); font-style: italic; color: #333;">Goldman Sachs</span> </div> --- You have 10 coins. probability of getting head for the first coin is 1/3, second 1/5, third, 1/7 and so on. What is the probability of getting odd number of heads? <div> <button class="toggle-solution">Show Solution <i class="fa-solid fa-chevron-down"></i></button> <div class="solution"> You are given seemingly complex dynamic (lot of distinct scenarios that need to be evaluated separately) and are asked for the result when there's 10 coins. This should give you a cue to try and see what happens if you had a small number of coins instead, and see if you can recognise the pattern.<br><br>With one coin, you only get odd number of heads if you have only one head. The chance is $\frac{1}{3}$ for the first coin so your answer is $p_1=\frac{1}{3}$. With two coins, we also get an odd number only if one of them is a H. So we can have TH with probability $\frac{2}{3}\frac{1}{5}$ or HT with probability $\frac{1}{3}\frac{4}{5}$. The total chance is therefore $$p_2 =\frac{2}{3}\frac{1}{5}+\frac{1}{3}\frac{4}{5}=\frac{2}{5}$$ With 3 coins, we can either have 1H or all 3H, with probability: $$p_3 = \frac{2}{3}\frac{4}{5}\frac{1}{7} + \frac{2}{3}\frac{1}{5}\frac{6}{7} + \frac{1}{3}\frac{4}{5}\frac{6}{7} + \frac{1}{3}\frac{1}{5}\frac{1}{7} = \frac{3}{7}$$ We can notice a pattern of how it evolves from n-1 to n. It seems that: $$p_n = p_{n-1}\frac{2n}{2n+1} + (1-p_{n-1})\frac{1}{2n+1}$$ Easiest way to solve this is to guess a solution and see if it holds up under induction. Looking at the solutions we have so far, $p_1=\frac{1}{3}$, $p_2 = \frac{2}{5}$, $p_3=\frac{3}{7}$ - it looks like $p_n = \frac{n}{2n+1}$. We know this is true for $p_1$, so let's see if we can show that it's true for $n$ if true for $n-1$. Assuming it holds for $n-1$, then $p_{n-1}=\frac{n-1}{2n-1}$. Given the relation we found between $p_{n-1}$ and $p_n$, we substitute: $$p_n = \frac{2n}{2n+1}\frac{n-1}{2n-1} + \frac{1}{2n+1}\frac{n}{2n-1}=$$ $$\frac{n(2n-1)}{(2n-1)(2n+1)}=\frac{n}{2n+1}$$ This is exactly what we wanted to show: the form $p_n=\frac{n}{2n+1}$ holds for 0, and if it holds for $n-1$ it holds for $n$. By induction, the form is correct. To get the answer for $n=10$, simply substitute $p_{10} = \frac{10}{21}$. </div> </div> ## Backwards Induction Very similar to forwards induction, just working backwards. This is a very powerful technique. It works as follows: - first ask: would this problem simplify in its last step $n$ / if we knew the solution for a problem of size $n-1$? - if so, solve the last step first / assume you have the solution until $n-1$ and solve for $n$. - Express previous step in terms of the final step. - Work your way back to the start. **When to Use?** Similarly to forward induction, this tends to work best when you have many (finite) iterations / too many possible outcomes to list out. To know when to use *forward* vs *backward* - ask whether the first or last step is easier / more trivial. It's usually one or the other. <div style="display: flex; justify-content: space-between; align-items: baseline;"> <h2>Interview Question</h2> <span style="font-size: var(--font-s); font-style: italic; color: #333;">Goldman Sachs</span> </div> --- You have n cars all going at random speeds. If a faster car is before the slower car, it will slow down to its speed. If the slower is before faster, nothing happens. Whats the expected number of clusters of cars you see in the end? <div> <button class="toggle-solution">Show Solution <i class="fa-solid fa-chevron-down"></i></button> <div class="solution"> You're asked for expected number, and it's pretty impossible to manually count all cases. The trick in this kind of problem is to use induction: solve it for a small number, assume you know the solution for n and see how the solution changes for n+1.<br><br>Start off with one car - obviously, there's only one cluster. Denoting the expected number of clusters for n cars $S_n$, $S_1$ = 1.<br><br>Now assume we know the solution for n, namely $S_n$ - what happens if we add one more car before the first one? You can add from back or from the front, but we'll add from the back as it makes the logic easier. Firstly note that for any number of cars they are ordered in ascending order of speed - as if faster car comes before a slower one, it slows down to its speed. A slower car behind a faster one simply creates a new cluster. So what happens when we add the extra car from the back (behind the slowest one)? The extra car adds one more cluster if it's slower than all the others, which happens with probability $\frac{1}{n+1}$. Otherwise, the cluster number remains the same.<br><br>We can now set up the cluster number evolution as follows: $S_{n+1} = S_n + \frac{1}{n+1}$. So now we have a starting point $S_0 = 1$ and a recurrance relation $S_{n+1} = S_n + \frac{1}{n+1}$, which allows us to compute the solution for any n. </div> </div> **Special Case** There's one setup that tends to appear often, where you should *always* use backwards induction. It's when you have a process that **ends when some condition is met**, but this will always happen in **finite iterations**. Reason I emphasise finite iterations is that when process ends on some condition and could go on until infinity, we use markov chains - a totally different method that we will cover later. This set up often looks something like: 'roll a dice and sum up what you get until the sum surpasses X. What's the most likely final roll that dipped above X?'. Let's see an example: <div style="display: flex; justify-content: space-between; align-items: baseline;"> <h2>Interview Question</h2> <span style="font-size: var(--font-s); font-style: italic; color: #333;">Jane Street</span> </div> --- You roll a 4 sided die and sequentially add up the score seen. What is the expected value of the first number you see above 100? <div> <button class="toggle-solution">Show Solution <i class="fa-solid fa-chevron-down"></i></button> <div class="solution"> To find expected value, we need all the possible outcomes and their probabilities. Which numbers can we dip above the sum of 100 with? With 101, 102, 103 and 104. Why not 105? Because the biggest roll we can get is 4, so to reach 105 the sum must have been at least 101 on the previous roll - and therefore 105 cannot be the first number we see above 100.<br><br>Now let's handle the probabilities, by focusing on the last step. We can reach 101 as the first number above 100 by rolling a 1 if we were previously at 100, with 2 if we were at 99, 3 if we were at 98 or 4 if we were at 97 - 4 possible scenarios. Notice the condition: we must previously be at a sum up to 100, and have this last roll dip above 100. Similarly, we can dip to 102 with a 2 if previously at 100, a 3 if previously at 99 or 4 if previously at 98 - 3 possible scenarios. We get to 103 only with a 3 if previously at 100, or 4 if previously at 99. And lastly we get 104 as the first number above 100 only if we had 100 before and we roll a 4.<br><br>It is safe to assume that probabilities of being at 97, 98, 99 and 100 are all equally likely to be the last sum before dipping above 100. They are indeed close enough, and it's prohibitive to compute exact probabilities on the interviews, so simply assume each of them has the same probability $p$.<br><br>Further, we know probability of rolling any value 1-4 is $\frac{1}{4}$. Therefore, the probability of dipping above any of the scenarios we mentioned (e.g. having 99 then rolling a 3) has the probability $p \cdot \frac{1}{4}$. Now we know that we reach 100 with one of the outlined scenarios, so all their probabilities sum up to 1. We had 4 cases where 101 is the first number above 100, 3 ways where it's 102, 2 ways for 103 and 1 way for 104 - 10 possible scenarios in total. Therefore, $10\cdot p \cdot \frac{1}{4}=1$. In turn, $p=\frac{2}{5}$, and any scenario has probability $\frac{1}{4}\cdot \frac{2}{5}=\frac{1}{10}$.<br><br>Now, since 101 can happen in 4 ways, all of which have probability $\frac{1}{10}$, then 101 is the first number to dip above 100 with probability $\frac{4}{10}$. It's 102 with probability $\frac{3}{10}$, 103 with probability $\frac{2}{10}$ and 104 with probability $\frac{1}{10}$. The expected first number can then be obtained as $$\frac{4}{10}101 + \frac{3}{10}102 + \frac{2}{10}103 + \frac{1}{10}104=102$$ </div> </div> ## Executive Summary We've covered a number of tricks: - **Fix First:** fix one iteration / element and see how the others behave. Then go back and consider its possible states. Use when problem has more moving parts with complex interactions, and choice of the element you fix is irrelevant. - **Symmetry:** look for symmetry in problems. Either see how your case is different from a symmetrical one, or see what probabilities are equal given the symmetry. Try this when it's not obvious how the problem would change if asked for H instead of T / even instead of odd / one player instead of the other... Often works with binary outcomes. - **Forwards Induction:** solve the problem for a small $n$. Keep increasing $n$ until you spot the pattern. Apply the pattern to the $n$ you were asked for. $n$ can be iterations / participants / elements... Use this when there's too many outcomes to list / many (finite) iterations / complex interactions - and the *problem is simple for a small number*. - **Backwards Induction:** focus on the last step $n$ / assume you solved for $n-1$ and solve for $n$. Then, work backwards - solving previous steps until the start. Use when there's too many outcomes to list / many (finite) iterations / complex interactions - and the *problem is simple in the last step*.