https://www.puzzledquant.com/problems/clgfh6upo001kla08fjmzul4l

We want to construct a structure made as follows: imagine that two long cylindrical pillars each with radius 1 intersect at right angles and their centers also intersect. What is the volume of this intersection?

If you cut the intersection by a horizontal plane at distance z from center, the cut will be a square with side-length 2*sqrt( 1-z^2). Integrate to get volume 16/3.\nAnother way is to imagine the largest possible sphere inscribed at the center of intersection. The sphere should have a radius of 1. At each cut perpendicular to the z-axis, the circle from the sphere is inscribed in the square from the intersection as well, So Area of cut-circle = ($\pi$/4)*Area of cut-square. This is true for all z, hence Volume of sphere = ($\pi$/4)*Volume of Intersection, this also gives 16/3

https://www.puzzledquant.com/problems/clgfh6jn10006la08imbmm0ky

On pressing a button, a random number is generated uniformly between $0$ \u0026 $1$. You keep on generating these numbers until their sum exceeds $1$. What is the expected number of times you need to press the button?

Probability of more than $n$ throws is equivalent to saying $X_1+..+X_n \u003c=1$, this is the volume of $n$ dimensional symplex from origin, its volume is $\frac{1}{n!}$ and can be proved by induction.\n This result can be used to calculate expected number of button presses,\n $\sum( \frac{1}{n!} * n ) = \sum \frac{1}{(n-1)!} = e^1$.\nOtherwise, set up a (lag)differential equation for $f(x)$, the expected number of draws needed for the sum to exceed $x$.\n For $x=0$,$f(x)=1$. For $x\u003e0$, suppose a draw gave number $t$, then $f(x)= 1 + \int_{t=0}^x f(x-t)dt$, which is same as\n $f(x) = 1 + \int_{t=0}^x f(t)dt$\n Differentiate wrt $x$, we get $f'(x) = 0 + f'(x)$. This has the solution $f(x)=e^x$ and $x=1$ gives $e$.\nTo take derivative, we used leibniz integral rule:\n $\frac{d}{dx} ( \int_{a(x)}^{b(x)} f(t) dt = f(b(x))*b'(x) - f(a(x))*a'(x) = f(x)*1 - f(x)*0 = f(x)$

https://www.puzzledquant.com/problems/clgfh6h43000ala08lo8diig6

You have $100$ noodles in your soup bowl. You are told to take two ends of some noodles (each end on any noodle has the same probability of being chosen) in your bowl and connect them. You continue until there are no free ends. Find the expression for the expected number of loops.\n What is the expression to get the probability of making one large loop which includes every noodle? Instead of 100, calculate for 4 noodles

First calculate expected number of loops:Denote $X_i$ = identity variable, which takes value 1 every time a (long) noodle becomes a loop by connecting to its end, (if its own end is connected to some other noodle, then that other noodle's end will be considered). Thus, number of loops = $X_1 +...+ X_{100}$, thus, expected number of loops = $E[X_1] + ... + E[X_{100}]$.\n This will give answer\n = $\frac{1}{2N-1} + \frac{1}{2N-3} + ... + \frac{1}{3} + 1 $, where N = 100.\n This formula can also be proved using induction. Calculating Probability of single large loop: If you followed last result, this one is simple, this time all the identity variables are zero except last one. Thus probability is \n$[1 - \frac{1}{2N-1}]*[ 1 - \frac{1}{2N-3}]* ... *[1-\frac{1}{3}]$ = $\prod_{i=2}^N [ \frac{2i-2}{2i-1}]$

https://www.puzzledquant.com/problems/clgfh6flt0002la08ddoln5b2

What is the expected distance of any point on Earth and the north pole? Take Earth radius 1.\nClarification: Shortest distance cuts through the sphere, instead of lying on surface.\nFurther thinking: Is this question same as choosing two random points on unit sphere and asking their expected distance?

$$2*\sin(\frac{x}{2})$ is the distance of north pole from a point on the ring at angle $x$ from the $z$ axis. So,\n $\int_0^{\pi} (2*\pi*\sin(x)*2*\sin(\frac{x}{2}) dx)$ and divide by the total area which is $4\pi$.\nAnswer: 4/3. \nAnother approach is to imagine a horizontal ring of $dy$ thickness at distance $y$ from $N$ (north pole). Area of ring = $2\pi dy$. Probability of choosing point on this ring = $\frac{dy}{2}$. Distance of $N$ \u0026 a point on ring = $\sqrt{2y}$. Exp length = $\int_{y=0}^2 \frac{\sqrt{2y}}{2} dy = \frac{4}{3}$\n Yes, taking two random points on surface of sphere and asking their expected distance is same as this very question.

https://www.puzzledquant.com/problems/clhudggrm001gmm086qrv9yeu

A gambler begins with an initial fortune of $i$ dollars. Each time he plays, he has the possibility of winning $1$ dollar with a probability of $p$ (where $0 \u003c p \u003c 1$) or losing $1$ dollar with a probability of $q = 1 - p$. The gambler will only stop playing if he either accumulates $N$ dollars or loses all of his money. What is the likelihood that he will end up with $N$ dollars? Compute for $p = 1/3$, $i=7$ and $N=10$

Let $P$ be the probability that the gambler's fortune will reach $N$ instead of $0$, starting from any initial state $i$ $(0 \u003c i \u003c N)$. The next state is either $i+1$ with probability $p$ or $i-1$ with probability $q = 1 - p$. So we have the equation:\n$P_i = pP{i+1} + qP_{i-1} \rightarrow P_{i+1} - P_i = \dfrac{q}{p}(P_i - P_{i-1}) = \left(\dfrac{q}{p}\right)^2(P_{i-1}- P_{i-2}) = \left(\dfrac{q}{p}\right)^i(P_1 - P_0)$\nWe also have the boundary probabilities $P(0) = 0$ and $P(N) = 1$. \nUsing the above equation, we can successively evaluate $P_i$ as an expression of $P_1$:\n$P_1 = pP_2 + qP_0$\n$P_2 = \frac{1}{p}P_1 = \left(1 + \dfrac{q}{p}\right)P_1$\n$P_3 =\left(1 + \dfrac{q}{p} + \left(\dfrac{q}{p}\right)^2\right)P_1$\n....\n$P_i = \left(1 + \dfrac{q}{p} + \left(\dfrac{q}{p}\right)^2 ... \left(\dfrac{q}{p}\right)^{i-1}\right)P_1$\nUsing the boundary probabilities, we can solve for $P_N$ and get:\n$P_N = 1 = \left(1 + \dfrac{q}{p} + \left(\dfrac{q}{p}\right)^2... \left(\dfrac{q}{p} \right)^{N-1}\right)$\n $P_N = \dfrac{1-(q/p)^N}{1- q/p}P_1 $ ; if $ \frac{q}{p}!= 1 $ OR $ P_N = NP_1 $ ; if $\frac{q}{p}=1$ \n Solving these equations we get the value of $P_1$, which gives the value of $P_i$ :\n $P_i = \dfrac{1 - (q/p)^i}{1 - (q/p)^N}$ ; if q/p !=1 \n $P_i = \dfrac{i}{N}$ ; if q/p =1

https://www.puzzledquant.com/problems/clhudgqr3002imm08hw983at9

Imagine two tubes, both with a radius of $1$, crossing each other perfectly at the center. What is the total amount of space that is shared between the two tubes?

To find the shared space between two tubes with a radius of $1$, we can use integration to calculate the volume. Assume one cyliner to be along x-axis and another to be along y-axis. We are looking along z axis i.e we can see two cylinders making '$+$' sign by crossing each other. \n The formula for $3D$ volume is $V = \int A(z)dz$, where $A(z)$ is the cross-sectional area of the solid cut by a plane perpendicular to the $z$-axis at coordinate $z$. To find the expression for $A(z)$, we can cut the intersection by a horizontal plane $x-y$ plane , which will result in a square with side-length $\sqrt{(2r)^2 - (2z)^2}$.\n Using symmetry, we can calculate the total volume as\n $2 \int_0^r [(2r)^2 - (2z)^2] dz$ = $8 \left[ r^2z - z^3/3\right]_0^r $= $\frac{16}{3}r^3$ =$\frac{16}{3}$.\n Another approach is to imagine a sphere inscribed inside both cylinders, which also intersects with the cylinders. The sphere has a radius of $r$, and at each cut perpendicular to the $z$-axis, the circle from the sphere is inscribed in the square from the intersection.So $A_{circle} = \frac{\pi}{4} A_{square}$ (square has side $2r$ and circle has radius $r$) and this is true for all values of $z$.\n $V_{sphere} = \frac{4}{3}\pi (r)^3 = \frac{\pi}{4}V_{intersection}$$\rightarrow V_{intersection} $= $\frac{16}{3}$.

https://www.puzzledquant.com/problems/clhudgreo002kmm08ht81csnn

On a distant island, there are three kinds of chameleons: $13$ are red, $15$ are green, and $17$ are blue. When two chameleons of different colors encounter each other, they change their color to the third color. For instance, if a green chameleon and a red chameleon meet, they both become blue. Can all the chameleons ever be the same color?

To have all chameleons become the same color, there must be a stage where two colors have the same number. This is because the combination before the final stage must be $(1,1,x)$. For two chameleons of different colors to have the same number, their module of $3$ must be the same. Starting with $15$ green ($3x$), $13$ red($3y+1$), and $17$ blue ($3z+2$) chameleons, when two chameleons of different colors meet, there are three possible scenarios. \n - $(3x, 3y+1, 3z+2) \rightarrow (3x'+2, 3y, 3z' +1)$ | $ G+R -\u003e 2B$ \n - $(3x, 3y+1, 3z+2) \rightarrow (3x+2, 3y, 3z+1)$ | $ R+B -\u003e 2G$\n - $(3x, 3y+1, 3z+2) \rightarrow (3x'+2, 3y', 3z+1)$ | $ G+B-\u003e 2R$\nIn each scenario, the pattern is preserved and we will never get two colors to have the same module of $3$. Therefore, we cannot make two colors have the same number, and the chameleons cannot become the same color. For all chameleons to become one color, at least one pair’s difference must be a multiple of $3$.

https://www.puzzledquant.com/problems/clj338ssd0000mf08x63ie7lx

Choose a person randomly on the street $𝑋$. Let $𝑁$ denote the random variable representing the number of people that you select randomly from the street before you find someone who's taller than $𝑋$. What is $𝐸[𝑁]$

The answer might surprise you so pay attention.\nAssume that heights have a PDF $𝑓$ and CDF $𝐹$.\n Given that the height of the first person is $𝑥_0$, using the CDF - we will get the probability of each other person (assuming iid) to be shorter is than $x_0$. This will be a constant, let’s call it $y = F(x_0)$. Hence probability of each other person taller than $x_0 = 1-y$\nThe number of people that should be measured before we find someone taller is geometric, so \n$𝐸( 𝑁 | 𝑋=𝑥_0 ) = \frac{1}{1−y}$\n Using Law of Total Expectation, we get $𝐸(𝑁) = 𝐸( 𝐸(𝑁|𝑋) )$\n$𝐸(𝐸(𝑁|𝑋))= \int_{−\infty}^\infty \frac{𝑓(𝑥)𝑑𝑥}{1−F(x)}$\n$E(E(N|X))=−ln(1−F(x))|_{-\infty}^{\infty}= \infty$\nTherefore we get $E(N) = E(E(N|X)) = \infty$\nNote that the limits will be reduced to (0,\infty) as we assume the height $X$ to be positive number. \n To put it another way, suppose $X$ has a uniform distribution over $(0,1)$. The calculation is similar to the previous one, but using simpler functions, and the outcome is identical. This assumption is 'allowed' because there is no assumption about the distribution of $X$ in the question, therefore we can assume that it should not matter, and in this case - we can test a basic distribution to acquire intuition.

https://www.puzzledquant.com/problems/cllnyeqvq0000ml086cb4qvms

You are chef for a day. There are 1024 different dishes you can make, but you need to pick 10 for the dinner menu. You've emailed the 3775 attendees a list of all the dishes and asked them to rank all the dishes in order of their preference (ranks go all the way from 1,2,3 … to …1024)\nNow, you're trying to make a list of 10 dishes, let's call it List L. This list should have a special quality: if there's a dish 'd' that's not on List L, and you compare 'd' to the dishes on List L in a vote, then at least half of the people should like one of the dishes on List L more than 'd'. Different people might prefer different dishes.\nThe big question is: Can you always make a list like that?

Short answer : It is always possible\nLong answer:\nIt is possible even there are $2^n$ dishes and you want to find a list of $n$ dishes: we prove this by induction on $n$. It's pretty obvious when $n=1$.\nAssume, then it holds for $n-1$ . When there are $2^n$ dishes, imagine holding a tournament, where every pair of dishes faces off, and the winner is the one whom more participants prefer. There will be no ties as there are an odd number of participants, so there will be $2^n \choose 2$ victories total.\nThis means that some dish must have had atleast $2^{n - 1} - 1$ victories, because if everyone had less than this, the total number of victories would be at most $2^n * (2^{n - 1} - 2)$, which is less than $2^n \choose 2$.\nNow simply, select a dish with $2^{n - 1} -1$ victories, remove that dish, along $2^{n - 1} - 1$ of the dinners it beats.\nWhat remains are $2^{n-1}$ dinners; by induction, we can find a list of length $n - 1$ which works for these remaining dishes, then adding this dish described by this method to our menu recursively creates a list of length $n$ which works for all $2^n$ dishes.

https://www.puzzledquant.com/problems/clwye8lde0000ev3ohu46vb2b

A stick of unit length is randomly broken into three pieces. Assuming each break follows a uniform distribution along the stick, what is the probability that the three segments can form a triangle?

Let $x$ be the first break and $y$ be the second break such that $x \u003c y$. Thus, the lengths of the three segments are $x$, $y - x$, and $1 - y$. As you recall from geometry, in order for three side lengths to form a triangle, each side length must be less than the sum of the other two side lengths. We can rewrite this as: $x \u003c (y - x) + (1 - y) \Rightarrow x \u003c \frac{1}{2}$ $y - x \u003c x + (1 - y) \Rightarrow y \u003c x + \frac{1}{2}$ $1 - y \u003c x + (y - x) \Rightarrow y \u003e \frac{1}{2}$. These constraints (including $x \u003c y$) cover $\frac{1}{4}$ of the sample space of $x, y \in [0, 1]$, which can be seen visually. Note that the $x \u003c y$ constraint only accounts for half of the possibilities since $x$ is equally likely to be greater than or less than $y$. The final answer is $2 \times \frac{1}{8} = \frac{1}{4}$.

https://www.puzzledquant.com/problems/clwye8low0000c8w4tzumgsss

Nicole is throwing two darts at a dartboard of radius $R$. Let $R1$ be the distance from the center to where Nicole's first dart lands. It is known that the distance from the center of the dartboard that the first dart lands is uniformly distributed. Once Nicole throws her first dart, it is known that she always throws her second dart a further distance away from the center than the first dart, and its location is uniformly distribution throughout the region that is further distance away than the first dart. Find the probability that her second dart is at least $\frac{R}{2}$ distance away from the center. The answer is in the form $\frac{a + \ln(b)}{c}$, where the fraction is fully reduced. Find $a + b + c$.

Let $R_1$ and $R_2$ be the radii of the two throws Nicole has. We want $\mathbb{P}\left[\frac{R_2}{R} \geq \frac{1}{2}\right]$. We condition on the radius of the first throw, $R_1$. We have that $R_1 \sim \text{Unif}(0, R)$ from the question. Thus, we have that $\mathbb{P}\left[R_2 \u003e \frac{R}{2}\right] = \int_{0}^{R} \mathbb{P}\left[\frac{R_2}{R} \geq \frac{1}{2} \,\middle|\, R_1 = r\right] f_{R_1}(r)dr$. We already know the PDF of $R_1$, so no more work is needed there. For the first probability, we need to split into two cases. The first is if $R_1 \u003e \frac{R}{2}$. Since from the question we know that Nicole throws her dart further away from the first one, the probability is 1 in this case, as the first dart is already at least $\frac{R}{2}$ away from the center. The second case is when $0 \u003c R_1 \u003c \frac{R}{2}$. In this case, the second dart lands uniformly throughout the region further away than the first dart. Thus, if $R_1 = r \u003c \frac{R}{2}$, the probability it lies in the annulus larger than $\frac{R}{2}$ in distance is given by taking the ratios of areas. We have that the area of the region larger than $\frac{R}{2}$ in distance is given by $\pi \left(\frac{R^2}{4} - r^2\right) = \frac{3\pi R^2}{4}$. Thus, the total area of the region is $\pi(R^2 - r^2)$. Thus, the conditional probability for this case is $\frac{3}{4} \times \frac{R^2}{R^2-r^2}$. We now split up the probability. We have that it is $\int_{0}^{\frac{R}{2}} \left(\frac{3}{4} \times \frac{R^2}{R^2-r^2}\right) \frac{1}{R}dr + \int_{\frac{R}{2}}^{R} \frac{1}{R}dr$ You can evaluate this expression here using methods from Calc II (Trig sub) to get that the final answer is $\frac{4 + 3\ln(3)}{8} = \frac{4 + \ln(27)}{8}$ by properties of logarithms. Therefore, $4 + 27 + 8 = 39$.

https://www.puzzledquant.com/problems/clwye8m3c0000kckx13s0dpao

A random angle $\theta_1 \sim \text{Unif}(0, 2\pi)$ is selected. Then, the arc of the unit circle that sweeps out $\theta_1$ radians is marked red going counterclockwise starting from $(1, 0)$. Two other angles $\theta_2, \alpha \sim \text{Unif}(0, 2\pi)$ IID are also selected. Afterwards, an arc of length $\theta_2$ radians starting from the point that is $\alpha$ radians counterclockwise of $(1, 0)$ is swept out and colored blue. Find the probability that the blue and red regions are disjoint.

For convenience, let's scale everything so that we are talking about proportions of the circle instead of radians. As a result, we are looking at $\text{Unif}(0, 1)$ random variables instead of $\text{Unif}(0, 2\pi)$. We can do this because we are just scaling our units. Let's first think about the conditions needed to have no overlap. First, we know that $\theta_1 \u003c \alpha$. This is because we know that we are going to sweep out an arc starting CCW from $\alpha$, so for the starting point of this second arc to not interfere with the first, we must have that condition. In addition, we need $\theta_2 \u003c 1 - \alpha$ (recall we are working in proportions here). This is because $\theta_1 \u003c \alpha$, we have proportion $1 - \alpha$ of the circle left before interfering with the original segment. Therefore, we want $\mathbb{P}[\theta_1 \u003c \alpha, \theta_2 \u003c 1 - \alpha]$. We see that both of these statements have $\alpha$ in them, so let's condition on $\alpha$ to remove that element of randomness. This yields that $\mathbb{P}[\theta_1 \u003c \alpha, \theta_2 \u003c 1 - \alpha \,|\, \alpha = x]f_{\alpha}(x)dx$. We integrate on $(0, 1)$ because of our scaling factor. Now, if we know $\alpha = x$, then the first term becomes $\mathbb{P}[\theta_1 \u003c x, \theta_2 \u003c 1 - x] = \mathbb{P}[\theta_1 \u003c x]\mathbb{P}[\theta_2 \u003c 1 - x] = x(1 - x)$ by the uniform distribution of the values on $(0, 1)$. Therefore, our probability of interest is $\int_{0}^{1} x - x^2 \, dx = \frac{1}{6}$.

https://www.puzzledquant.com/problems/clwye8mg80002upar0gabo33n

How many ways can you tile a $3 \times 8$ grid with $1 \times 2$ and $2 \times 1$ tiles?

We are going to solve this for more general $n$. Let $t(n)$ be the number of ways of tiling a $3 \times n$ board with these tiles. Consider tiling the first spots all the way at the left. There are three options: \textbf{Case 1:} You place $3 \times 1$ tiles in each of the rows. In this case, there are $t(n - 2)$ possible ways to tile the remaining grid, as you have eliminated the first two columns. \textbf{Case 2:} You place a $1 \times 2$ tile in the first row and then a $2 \times 1$ tile in the first column bottom two rows OR a $2 \times 1$ tile in first column top two rows and a $1 \times 2$ tile in the bottom row. In both cases here, you end up with a grid that has a corner piece missing. We can just consider one of the two arrangements above and multiply by $2$, as they both yield a grid that has one corner missing. Let the number of ways to tile the grid with one corner missing and $n$ columns be $s(n)$. Consider tiling the first column of the grid where the corner is missing. You have two cases: \textbf{Case 2a:} Place a $2 \times 1$ tile in the first column. In this case, you get a grid with no missing corner and $n - 1$ columns, so there are $t(n - 1)$ ways to tile the remaining grid. \textbf{Case 2b:} Place three $1 \times 2$ tiles in each of the rows. You get another grid with $n - 2$ columns and a missing corner, so there are $s(n - 2)$ ways to tile the remaining grid. Combining these together, we get that $s(n) = t(n - 1) + s(n - 2)$ and $t(n) = t(n - 2) + 2s(n - 1)$. The boundary conditions are that $t(0) = 1$ (empty grid), $t(1) = 0$ (no way to tile one column grid), $s(0) = 0$ (can't be a missing corner), and $s(1) = 1$ (just a single $2 \times 1$ tile). We are looking for $t(8)$ in this problem. Using this recurrence, one gets $t(8) = 153$ after some considerable effort.

https://www.puzzledquant.com/problems/clwye8mr20000p1b9yezoozde

Aaron picks an integer $k \in \{1, \ldots, 52\}$. Then, he draws the first $k$ cards from a standard, shuffled $52$-card deck. Aaron wins a prize if the last card he draws is an ace and if there exists exactly one ace in the remaining $52 - k$ cards. What $k$ should Aaron pick?

Consider an ordering of 52 cards. In order for Aaron to win a prize, (1) the $k$-th card must be an ace, (2) there must be exactly two aces in the first $k - 1$ cards, and (3) there must be exactly one ace in the last $52 - k$ cards. Treating all cards as distinguishable, we find the following function of $k$ that describes the probability that Aaron wins a prize. $\mathbb{P}(\text{Aaron wins}) = \frac{ \binom{k-1}{2} \binom{52-k}{1} 4!48!}{52!} = \frac{12 \cdot 48! \cdot (52 - k)(k - 1)(k - 2)}{52!}$ We arrive at the above expression as follows: (1) choose two cards to assign as aces from the first $k - 1$ cards, (2) assign the $k$-th card as an ace, (3) choose one card to assign as an ace from last $52 - k$ cards, and finally, (3) there are $4!$ ways to order the four distinguishable aces among the four allotted ace slots. Now, we have a simple optimization problem: $k_{\text{optimal}} = \arg\max_{k \in \{1,\ldots,52\}} \left\{ \mathbb{P}(\text{Aaron wins}) \right\} = \arg\max_{k \in \{1,\ldots,52\}} \left\{ \frac{12 \cdot 48! \cdot (52 - k)(k - 1)(k - 2)}{52!} \right\}$ Let's take the derivative of $\mathbb{P}(\text{Aaron wins})$ with respect to $k$, set it to $0$, and solve for $k$. $\frac{d}{dk} \left( 12 \cdot 48! \cdot (52 - k)(k - 1)(k - 2) \right) = 0$ Diving out the constants and simplifying, we find $\frac{d}{dk} \left( -k^3 + 55k^2 - 158k + 104 \right) = 0$ $\Rightarrow 3k^2 - 110k + 158 = 0$ Solving for $k$, we find $k = \frac{55}{3} \pm \sqrt{\frac{2551}{3}}$ Note that $k$ cannot equal $\frac{55}{3} + \sqrt{\frac{2551}{3}}$ as $k$ must be an integer, and $35 \u003c k \u003c 36$. Testing both $k = 35$ and $k = 36$, we find that $k = 35$ achieves the greatest probability for Aaron to win a prize.

https://www.puzzledquant.com/problems/clwye8n190001c8w4j5a7vywg

Two players, say $A$ and $B$, play the following game: Both players have $100$ marbles and may put anywhere between $1$ and $100$ marbles in the box each. This decision is not revealed to the other player. Then, they draw $2$ marbles with replacement between trials. If the marble belongs to $A$, then assuming that $A$ put $a$ marbles in the box, $A$ is paid $100 - a$ monetary units from a third party. Similarly if the marble belongs to $B$, then assuming $B$ put $b$ marbles in the box, $B$ is paid $100 - b$ monetary units from a third party. Assume both players play optimally. Find the expected total payout of player $A$.

We can first make some simplifications to the game. Firstly, if the strategy is optimal, then if this game were to be repeated many times, they would not change their strategy. Therefore, the optimal strategy for the game where there are $2$ consecutive marble draws is the same as the optimal strategy for the game with one draw. Then, we just multiply the expected profit by $2$ to represent the two draws. Furthermore, as this game is symmetric for the two players, their optimal strategy will be the same. This point will be important later. Let $A(a, b)$ be the expected profit that $A$ obtains with player $A$ putting in $a$ balls and $B$ putting in $b$ balls. Namely, for the one draw game, $A(a, b) = \frac{a}{a + b} \cdot (100 - a)$ As player $a$ draws his ball with probability $\frac{a}{a + b}$ and $100 - a$ is the payout. Let's fix $b$ and find the $a$ that is the best response to this $b$. In other words, given $b$, what $a$ optimizes $A(a, b)$? To do this, we take the partial derivative of $A(a, b)$ in $a$ and treat $a$ as continuous for now. We will then account for discreteness at the end. This yields that $\frac{\partial}{\partial a} A(a, b) = \frac{a^2 + 2ba - 100b}{(a + b)^2} = 0 \iff a^2 + 2ba - 100b = 0$ Solving the above with the quadratic equation yields that $a^* = \frac{-2b \pm \sqrt{4b^2 + 400b}}{2}$. However, the $-$ root results in a negative value, so $a^* = \sqrt{b^2 + 100b} - b$ is the best response for player $A$ if player $B$ puts $b$ marbles in. Similarly, as this game is symmetric, the optimal response for player $B$ if player $A$ puts $a$ marbles in is $b^* = \sqrt{a^2 - 100a - a}$. To find the optimal strategy for each player, this means that we need to find the combo $(a^*, b^*)$ such that neither of the players can do better by adjusting their strategy. We already are aware from before that $a^* = b^*$ by the symmetry of the game. Therefore, to solve for this, we just substitute in $b$ as $b^* = a^*$ in the first equation. This yields we can say that $a^* = \sqrt{ (a^*)^2 + 100a^* - a^*} \implies 4(a^*)^2 = (a^*)^2 + 100a^* \implies a^* = 0, \frac{100}{3}$ As $0$ is not possible, we conclude that $a^* = b^* = \frac{100}{3}$ is the optimal strategy. However, this is not actually possible, as our marbles must be an integer value. Therefore, we should test $(33, 33)$ and $(34, 34)$ to see if they are Nash equilibria. For $(33, 33)$, the expected payout for one draw for each player is $\frac{67}{2}$. One can check that by varying $a$ and keeping $b$ fixed at $33$, player $A$ can't do any better. Therefore, $(33, 33)$ is a Nash equilibrium. For $(34, 34)$, the expected payout is $33$. However, one can also verify that the expected payout for $(33, 34)$ is also $33$. However, this can't be an equilibrium, as $b$ should change to $33$ marbles to yield higher expected payout. Thus, while $(34, 34)$ is also a Nash equilibrium, $(33, 33)$ is preferable because of the higher expected payout. This means that the optimal strategy is for both players to place $33$ marbles and have a total expected payout of $\frac{67}{2} = 67$.

https://www.puzzledquant.com/problems/clwye8ned0000siuz42ab19mm

Suppose that $X_1, \ldots, X_7 \sim \text{Unif}(0, 1)$. Find the PDF of $Y = X_1 X_2 \ldots X_7$. The answer is in the form $f(x) = \left( -\log(x) \right)^a \frac{1}{b} I_{(0,1)}(x)$ for integers $a$ and $b$. Find $a + b$.

We solve this for general $n$ and then plug in at the end. The trick here is to take the logarithm of both sides and note that if $X \sim \text{Unif}(0, 1)$, then $ -\log(X) \sim \text{Exp}(1)$. The reason we want to take the logarithm is because of the fact that the logarithm will turn a product into a sum. Therefore, we have that $\log(Y) = \log(X_1 \cdot \ldots \cdot X_n) = \log(X_1) + \ldots + \log(X_n)$ Multiplying each side by $-1$, $-\log(Y) = (-\log(X_1)) + (-\log(X_2)) + \ldots + (-\log(X_n))$ Note that since each of the $X_i$ are independent, the sequence of $-\log(X_i)$ are also independent. Since each one is $\text{Exp}(1)$ distributed, then we have that the RHS is the sum of $n$ IID $\text{Exp}(1)$ random variables. Therefore, the RHS is $\text{Gamma}(n, 1)$ distributed. We have that $-\log(Y) = G$, where $G \sim \text{Gamma}(n, 1)$. In other words, the distribution of $Y$ is therefore that $Y = e^{-G}$, where $G \sim \text{Gamma}(n, 1)$. We don't have the CDF of $G$ in explicit form, so we use fragmentation. Since $Y = f(G) = e^{-G}$, the inverse is just $h^{-1}(y) = -\log(y)$, so that $ (h^{-1}(g))' = \frac{1}{g} $. Therefore, the PDF of $Y$ is $f_Y(y) = \left(-\log(y)\right)^{n-1} e^{-\log(y)} \cdot \frac{1}{y} \cdot \frac{1}{\Gamma(n)} I_{(0,\infty)}(-\log(y))$ The indicator says that $0 \u003c -\log(y) \u003c \infty$, which $ \log(y) \u003c 0 $, or that $ 0 \u003c y \u003c 1 $. Therefore, $f_Y(y) = \frac{(-\log(y))^{n-1}}{\Gamma(n)} I_{(0,1)}(y).$ Plugging in $n = 7$, we have that $a = 6$ and $b = \Gamma(7) = 6! = 720$. This means $a + b = 726$.

https://www.puzzledquant.com/problems/clwye8nu00002c8w4hfm72yoa

Suppose we deal out cards from a standard deck. Find the expected number of cards after the first $2$ and before the first ace given that the first $2$ appears before the first ace.

We want to find the expected cards after the first $2$ that we obtain the first ace. Therefore, our first task is to figure out how many cards that aren't ranked $A$ or $2$ on average. We have $8$ dividers, which are precisely all of the rank $A$ and $2$ cards. These dividers split our deck up into $9$ regions. There are $44$ cards left that are not ranked $A$ or $2$, so as we have that the regions have equal size in expectation, the expected length of each region is $\frac{44}{9}$. Now, we need to find the expected number of regions that appear between the first $2$ and ace. We now do first ace again on the dividers. We know that one of the $2$s showed up already, so we only have $7$ dividers left. We want to find the expected number of $2$s before the first ace, so the aces are our dividers now. The $4$ aces divide up our subset into $5$ regions. We have $3$ $2$s left, so there are on average $\frac{3}{5}$ $2$s per region. However, we already know that one $2$ appeared, so we must add $1$ to the number of regions that there will be. Therefore, our expected number of regions is $\frac{8}{5}$. However, we also need to account for the dividers, as we did not count for them previously when computing $\frac{44}{9}$. The average number of dividers that appear after the first $2$ is $\frac{3}{5}$, so we just add that in above. Putting this all together, the expected number of cards between them is $\frac{44}{9} - \frac{8}{5} + \frac{3}{5} = \frac{35}{9}$.

https://www.puzzledquant.com/problems/clwye8o5g0000ehsq93wzupl5

Ty, Guy, and Psy are all flipping fair coins until they respectively obtain their first heads. Let $T$, $G$, and $P$ represent the number of flips needed for Ty, Guy, and Psy, respectively. Find $\mathbb{P}[T \leq G \leq P]$.

We know that $T$, $G$, $P \sim \text{Geom}\left(\frac{1}{2}\right)$ IID, as they are looking for the distribution of the first heads. As these are independent, we can multiply the individual PMFs to get the joint PMF, so the joint PMF is $\mathbb{P}[T = t, G = g, P = p] = \left(\frac{1}{2}\right)^t \left(\frac{1}{2}\right)^g \left(\frac{1}{2}\right)^p$ for $t, g, p = 1, 2, \ldots$. We now need to get a region of summation for this probability. Let's let $t$ be free, so we sum $t$ from 1 to $\infty$. Then, we know $G \geq T$, so we sum over $g = t$ to $\infty$. After that, we know $P \geq G$, so we sum inner most from $p = g$ to $\infty$. Therefore, our sum is $\sum_{t=1}^{\infty} \sum_{g=t}^{\infty} \sum_{p=g}^{\infty} \left(\frac{1}{2}\right)^t \left(\frac{1}{2}\right)^g \left(\frac{1}{2}\right)^p.$ As the innermost summation only concerns $p$, we ignore the rest for now. $\sum_{p=g}^{\infty} \frac{1}{2^p} = \frac{1}{2^g} \frac{1}{1 - \frac{1}{2}} = \frac{1}{2^{g-1}}.$ Now, our summation is $\sum_{t=1}^{\infty} \sum_{g=t}^{\infty} \frac{1}{2^t} \frac{1}{2^{2g-1}}.$ Ignoring the first term, as our sum only concerns $g$, $\sum_{g=t}^{\infty} \frac{1}{4^{g}} = \frac{1}{4^{t}} \frac{1}{1 - \frac{1}{4}} = \frac{4}{3.4^{t}}.$ Now, our final summation is $\frac{8}{3} \sum_{t=1}^{\infty} \frac{1}{8^t}$ after shoving all the constants to the front. The last sum is simply $\frac{\frac{1}{8}}{1-\frac{1}{8}} = \frac{1}{7},$ so our solution is $\frac{8}{21}.$

https://www.puzzledquant.com/problems/clwye8ork0000rbb16r1ybmzy

Subsets $A$ and $B$ are chosen uniformly at random from the collections of all subsets of a set $X$ of cardinality $5$. What is the probability that $A$ is a subset of $B$?

Each element of $X$ is likely to be in any of the four sets: $A \setminus B$, $B \setminus A$, $A \cap B$, $X \setminus (A \cup B)$. In order for $A$ to be a subset of $B$, $A \setminus B$ must be empty. In other words, every element of $X$ would have to be in any of the other three sets of the four sets. Thus, the probability that $A$ is a subset of $B$ is $\left( \frac{3}{4} \right)^5 = \frac{243}{1024} \approx 0.24$.

https://www.puzzledquant.com/problems/clwye8p2s0001siuzcwcxgqyo

You have $5$ pairs of gloves that each have a distinct number $1$ to $5$. The $10$ gloves are randomly paired up. Find the probability that the gloves are paired up such that the values of any pair differ by at most $1$.

We are going to solve the more general case with $n$ pairs of gloves labelled $1$ to $n$. Note that there are $\frac{(2n)!}{2^n \cdot n!}$ ways to pair up the $2n$ gloves, as there are $(2n)!$ total arrangements, $n!$ ways to re-label the pairs, and then $2$ ways to switch around the order in each pair. Let $g_n$ be the number of arrangements that satisfy our condition. Consider the two gloves labelled $n$, say $n1$ and $n2$. Decide the partner for $n1$ first. We either have that $n2$ is paired with $n1$, in which case, we go back to the same problem but with $n - 1$ pairs of gloves instead of $n$. Otherwise, $n1$ is paired with one of the gloves labelled $n - 1$, of which there are $2$ ways to pick that glove. Afterwards, we know that $n2$ is paired with the other glove labelled $n - 1$, and that becomes fixed. Then, this goes back to the same problem but with $n - 2$ pairs of gloves instead. Therefore, we get the recurrence relation $g_n = g_{n-1} + 2g_{n-2}$ Remember that the $2$ in front of $g_{n-2}$ represents the fact that we have $2$ options of the glove labelled $n - 1$ to match with $n1$ in that sub-case. We now need some initial conditions. Note that $g_1 = 1$, as there is clearly only one pair. Furthermore, we have $g_2 = 3$, as we can pick the partner for any one of the gloves in $3$ ways, and that fixes the other pair immediately. The characteristic equation of this recurrence relation is $r^2 - r - 2 = 0$, of which the solutions are $r = 2, -1$. Therefore, $g_n = c_0 \cdot 2^n + c_1 \cdot (-1)^n$. Plugging in the initial conditions yields that $1 = 2c_0 - c_1$ and $3 = 4c_0 + c_1$. Solving these yields that $c_0 = \frac{2}{3}$ and $c_1 = \frac{1}{3}$. Therefore, $g_n = \frac{2^{n+1} + (-1)^n}{3}$ Therefore, the probability of this event occurring with $n$ pairs is given by $p_n = \frac{g_n}{\frac{(2n)!}{2^n \cdot n!}} = \frac{(2^{n+1} + (-1)^n) \cdot 2^n \cdot n!}{3(2n)!}$ Substituting in $n = 5$, we get that $p_5 = \frac{1}{45}$.

https://www.puzzledquant.com/problems/clgfh6k1g0008la08x16hdx8j

You are initially located at origin in the $x$-axis. You start a random walk with equal probability of moving left or right one step at a time. Find the expression to get the probability that you will reach point $a$ before reaching point $-b$. \n What is the expected number of steps to reach either $a$ or $-b$ ($a,b$ are natural numbers)? Calculate for $a=3 \u0026 b=4$.

If you try markov chain approach, this question will never end! For this problem, we will use Martingales.\nLet $N$ = number of steps to reach any of $a$ or $-b$. Let $S_N$ = $X_1+...+X_N$. Suppose $P_a$ = probability of touching $a$ before $-b$, and $P_b$ = the opposite. We use the fact that both $S_N$ and $S_{N^2-N}$ are martingales, thus:\n $0 = E[S_N] = a*P_a + (-b)*P_b$ \nThis gives $P_a = \frac{b}{a+b}$.\nSimilarly,\n $0 = E[S_{N^2-N}] = P_a*a^2 + P_b*b^2 - E[N]$.\nThis gives $E[N] = ab$

https://www.puzzledquant.com/problems/clxc0gonu000uojku45nc3emu

You are given a fair 20-sided die and 100 actions in a game. The die starts with upface 1. The two options you can perform are to roll and to take. Performing a roll re-rolls the current upface of the die. Performing a take allows you to cash out the current upface of the die. Note that the game does not end when you perform a take. However, you must roll the die again before doing another take. Your strategy is to accept any number that is at least some threshold $n$. This $n$ must be decided in advance and is fixed for the entire game. Assuming rational play in selecting $n$, find your expected payout.

To get a baseline to compare to, suppose we just roll and take in an alternating fashion. We will be able to perform this $50$ times (as each is one action) and the expected value per roll is $10.5$, so our expected payout would be $50 \cdot 10.5 = 525$ with this strategy. Now, let's write the expected payoff as a function of $n$. If we accept any value at least $n$, then the expected value we roll given we accept is $\frac{20 + n}{2}$. There are $21 - n$ values that are at least value $n$, so the probability on each roll that we obtain a value at least $n$ is $\frac{21 - n}{20}$. As this probability is constant between rolls, the expected number of terms of obtain a value at least $n$ is $\frac{20}{21 - n}$. However, we now must claim it after we obtain a roll satisfying this threshold, so the expected number of turns needed to roll and claim the money is $\frac{20}{21 - n} + 1$. Therefore, on average, we are able to roll and claim the money $\frac{100}{\frac{20}{21 - n} + 1}$ times in the game, as it takes us that many turns on average to roll and claim and we have $100$ total turns. Lastly, this implies our expected payout is $f(n) = \frac{100}{\frac{20}{21 - n} + 1} \cdot \frac{20 + n}{2}$, as we multiply the expected number of times we are paid by the expected payout per time. To find the $n$ maximizing this, one can treat $f$ as continuous and use the derivative of it to find the optimal $n$. The details of taking the derivative messy and not enlightening, so the steps are excluded. However, after using the basic rules and simplifying, $f'(n) = \frac{50}{(n - 41)^2} \cdot (n^2 - 82n + 461) = 0$ The roots of the polynomial are $n_{1,2} = 41 \pm 2\sqrt{305}$. The root adding $2\sqrt{305}$ is larger than $20$, so $n^* = 41 - 2\sqrt{305}$ must be the maximizer. As $17 \u003c \sqrt{305} \u003c 18$ and our optimal $n$ must be an integer, we can test $n = 5, 6, 7$ to see which gives us the largest expected payout. Plugging all three of these in reveals $n = 6$ maximizes $f(n)$ with payout $\frac{3900}{7}$.

https://www.puzzledquant.com/problems/clgfh6ld0000ala0898klbbjg

On a 2D plane, an aircraft hovers above sea, trying to catch a submarine moving with a constant velocity under the sea. The submarine is completely invisible, but using a human radar only once, the aircraft knows the exact location of submarine under the sea. The direction of submarine is unknown, but constant. The aircraft can move at twice the speed of submarine. As soon as the aircraft is just vertically above the submarine, Aircraft can magnetically pick it up. Can the aircraft catch the submarine? If yes, also figure out the time it would take, if no, prove why?\nPS: This scene is from X-men: First Class. Good x-men are in the aircraft called blackbird, human radar is Banshee, Magnet is Magneto. Bad x-men are in submarine, with Sebastian Shaw is about to cause a war, better catch him soon!

Let speed of plane be $2s$, submarine: $s$, original distance $d$ \nLocus of submarine after time $t$ is circle of radius $s*t$ centered at original location of submarine. Thus the plane moves $\frac{2}{3}$ distance towards submarine, and then spirals out by increasing radius with speed $s$. The submarine is caught after one round. \nFor General case, with speeds $p$ \u003e $s$, Let $O_p$, $O_s$ be the initial positions of the plane and the submarine, resp. For time $t_0 = \frac{d}{(s+p)}$, the plane will move towards $O_s$ in the $O_p O_s$ direction. After that, with $O_s$ as the origin, the plane will maintain a constant velocity of $s$ along the radial direction. Thus, at an angle $\theta$ from $O_pO_s$, tangential displacement in time $dt$ is\n $\sqrt{p^2-s^2}*dt = r*d\theta = s*t*d\theta =\u003e \frac{dt}{t} = \frac{s}{\sqrt{p^2-s^2}*d\theta}$.\n Integrating $t$ from $t_0$ to $t_f$, and $\theta$ from $0$ to $2*\pi$, we get $t_f = t_0*e^{2*\pi*s/\sqrt{p^2-s^2}} = [\frac{d}{s+p}]*e^{2*\pi*s/\sqrt{p^2-s^2}}$.\nNote that the plane can be vertically above the submarine any time between $t_0$ and $t_f$, depending on the direction $\theta$ of the velocity of the submarine wrt $O_pO_s$, thus making $t_f$ the worst case time.

https://www.puzzledquant.com/problems/clgfh6m35000ela08ke04exb3

You are given $32$ coins which look identical. But actually some of them are pure gold coins (hence are heavy) and the rest are aluminium coins with thin gold plating (light). You are given one beam balance with two pans. What is the number of weighing required to separate the gold from fake coins? (all gold coins have equal weights \u0026 all fake coins too have the same weight)

It takes about ${\log^2 N}$ operations\nDivide the set of $2^k$ with $d$ heavy coins into two sets, each with $2^{k-1}$ coins with $floor(d/2)$ heavy coins. If we can do this, we can determine the number of heavy coins in $O({\log^2 n})$ operations.Dividing the set can be done in $O(\log n)$.\n So, $T(n) = T(n/2) + O(\log n)$\n$T(n) = O(\log^2 n)$\n To be exact, this is $\frac{k*(k+1)}{2}$, where $k = \log N$\n(*Sub-Algorithm)Divide the set into two sets $A$ and $B$ of equal number of coins. Let $A$ greater than B and to make both side of equal weight, I need to shift few coins from $A$ to $B$ and equal number of coins from $B$ to $A$. So divide $A$ into $A_1$ and $A_2$, and $B$ into $B_1$ and $B_2$. Move $A_2$ from $A$ into $B$ and $B_1$ from $B$ into $A$ now if $(A_1,B_1)$ is greater than $(B_2,A_2)$ then I have not moved enough coins from $A$ into $B$ so as to make $B$ part heavy enough hence you divide $A_1$ into $A_{11}$,$A_{12}$ and move $A_{12}$ in $B$ side similarly you move $B_{21}$ into $A$ side on the other hand if $(A_1,B_1)$ is less than $(A_2,B_2)$ I have more than enough coins from $A$ into $B$ hence move $B_{12}$ back into $B$ and $A_{21}$ back into $A$ now measure again. Do it so on...\nNote that we are doing this in $O(\log n)$ as each time the number of coins we are moving is reduced by half. So, In $O(\log n)$, we are done. To prove that solution always exists, we do it by induction:difference in the number of heavy coin after $k^{th}$ iteration cannot be more than $2^{n-1-k}$. So, after ${n-1}^{th}$ iteration, it can be more that $1$ coin. Hence, done.

https://www.puzzledquant.com/problems/clhudgax8000smm08fc0ukkge

Bond $A$ has a $50\%$ chance of defaulting next year while Bond $B$ has a $30\%$ chance of defaulting. What is the range of probability that at least one bond defaults and what is the range of their correlation?

Note that we don't have any information if the event of Bond $A$ and $B$ defaulting are independent or not. To determine the probability range for at least one bond defaulting, we can assume that whenever Bond A defaults, Bond B does not default, and whenever Bond B defaults, Bond A does not default. Thus, the maximum probability that at least one bond defaults is $50\% + 30\% = 80\%$. On the other hand, assuming that whenever Bond A defaults, Bond B also defaults gives us the minimum probability of $50\%$.\nTo calculate the correlation range, let $I_A$ and $I_B$ be the indicators for the event that Bond A/B defaults next year, and $\rho$ be their correlation. We have $E[I_A] = 0.5$, $E[I_B] = 0.3$, $\text{var}(I_A) = p_{A}(1 - p_{A}) = 0.25$, and $\text{var}(I_B) = p_B(1 - p_B)=0.21$.\n Using the formula $P(A \text{ or } B \text{ defaults}) = E[I_A] + E[I_B] - E[I_A I_B]$\n$ = E[I_A] +E[I_B] - (E[I_A]E[I_B] + \text{cov}(I_A I_B))$\n$ = 0.5 + 0.5 - 0.5*0.3 - \rho \frac{\sqrt{0.21}}{2} = 0.65 - \rho \frac{\sqrt{0.21}}{2} $\n For max probability of default, $0.65 - \rho \frac{\sqrt{0.21}}{2} = 0.8 ; \rho = -\sqrt\frac{3}{7}$\n For min probability of default $0.65 - \rho \frac{\sqrt{0.21}}{2} = 0.5 ; \rho = \sqrt{\frac{3}{7}}$\n Note that we can simply take correlation range as +1 or -1 as correlation can't take those values. The correlation range of $\left[-\sqrt{\frac{3}{7}}, \sqrt{\frac{3}{7}}\right]$.

https://www.puzzledquant.com/problems/clhudg7cr000emm0846jqycfx

A man had too much to drink and is standing on a bridge that is $100$ meters long. He is currently at the $17^{th}$ meter but has a tendency to either move forward or backward one meter with a $50\%$ chance for each step he takes. What are the chances that he will make it to the end of the bridge (the $100^{th}$ meter) before he returns to the beginning (the $0^{th}$ meter)?\n Additional problem for the more curious ones: how many steps is he expected to take to reach either end of the bridge?

To solve this problem, we can use a martingale argument. Let's set the current position to $0$, and the problem becomes a symmetric random walk that stops at either $83$ or $-17$. We know that both $S_n$ and $S_n^2 - n$ are martingales, where $S$ is the position of the man, $S_n^2$ is the position of the man squared, and $n$ is the number of steps taken. Since a martingale stopped at a stopping time is a martingale, $S_N$ and $S_N^2 - N$ (where $S_N$ is the sum of the random variables $X_i$ for $i \in \{1,2,..N\}$, with $N$ being the stopping time) are martingales as well. \nLet $p$ be the probability that the man stops at $83$, $p'$ be the probability that he stops at $-17$ ($p' = 1 - p$), and $N$ be the stopping time. Then we have:\n$E[S_N] = p * 83 + (1 - p) * (-17) = 100p - 17 = S_0 = 0$ $\rightarrow p = 0.17$ \n $E[S_N^2 - N] = p * 83^2 + (1 - p) * (-17)^2 - E[N] = S_0^2 - 0 = 0$ $\rightarrow$ $ E[N] = 1411$ \nTherefore, the probability that the man will make it to the end of the bridge before returning to the beginning is 0.17, and the expected number of steps he takes to reach either the beginning or the end of the bridge is $1411$. \n As generalisation for two points $\alpha$ and $-\beta$, $p_{\alpha} =\frac{ \beta}{\alpha + \beta}$, and $E[N] = \alpha \beta$

https://www.puzzledquant.com/problems/clhudg6f4000amm08qd3vmyai

At a theater ticket office, there are $2n$ people waiting to buy tickets. $n$ of them have only $5$ bills, while the other $n$ people have only $10$ bills. Unfortunately, the ticket seller has no change to start with. Each person wants to buy one $5$ ticket. What are the chances that everyone can successfully buy their ticket without having to change places, if there are a 12 people in line (n = 6) ?

The problem is to find the probability that $2n$ people, $n$ with $5$ bills and $n$ with $10$ bills, can all buy a $5$ ticket without having to change places in line.\n We assign $+1$ to people with $5$ bills and $-1$ to people with $10$ bills. Let $(a,b)$ represents after $a$ steps the walk ends at $b$. We consider the process as a random walk, starting at $(0,0)$ and ending at $(2n,0)$ after $2n$ steps. We need to choose $n$ steps as $+1$, so there are $\binom{2n}{n}$ possible paths. We are interested in the paths that have the property $b\u003e=0$, $0\u003ca\u003c2n$. \nIt's easier to calculate the number of complement paths that reach $b=-1$, $0\u003ca\u003c2n$ at least once. We use a tool called the reflection principle, in which we take reflection of a path along y= -1, after it hits b = -1, for the first time. So now all the paths which reached $b=-1$ at any time, will reach ($2n,-2$) as end point. For a path to reach $(2n,-2)$, there are $(n-1)$ steps of $+1$ and $(n+1)$ steps of $-1$. So there are $\binom{2n}{n-1}$ paths that have the property $b=-1$, $0\u003ca\u003c2n$, given that the path reaches $(2n,0)$. The number of paths that have the property $b\u003e=0$, $0\u003ca\u003c2n$ is\n $\binom{2n}{n} - \binom{2n}{n-1} = \binom{2n}{n} - \frac{n}{n+1}\binom{2n}{n} = \frac{1}{n+1}\binom{2n}{n}$\n Hence, the probability that all people will be able to buy their tickets without having to change positions is $\frac{1}{n+1}$. This solution uses the reflection principle and the concept of paths in a walk.

https://www.puzzledquant.com/problems/clhudg4zs0004mm08funzs35g

In the World Series finals, the Boston Red Sox and the Colorado Rockies are facing each other. The championship goes to the team is the first to win four out of the maximum seven games. You want to bet on the Red Sox and have $100$ dollars to place a double-or-nothing wager on each game. Unfortunately, you can only bet on each individual game, not the series as a whole. How much should you bet on each game so that if the Red Sox wins the whole series, you win exactly $100$ dollars, and if Red Sox loses, you lose exactly $100$ dollars?

To determine the amount to bet on each game, we need to start with the final stage and work backwards. Let $(i,j)$ represent the state where the Red Sox has won $i$ games and the Rockies has won $j$ games, and let $f(i,j)$ be our net payoff at state $(i,j)$. We need to decide on a strategy so that whenever the series is over, our final net payoff is either $+100$ or $-100$.\n Final stage payoffs are $+100$ for states $\{(4,0),(4,1),(4,2),(4,3)\}$ and $-100$ for states $\{(0,4),(1,4),(2,4),(3,4)\}$.\n For each state $(i,j)$, if we bet $y$ on the Red Sox for the next game, we will have $f(i,j)+y$ if the Red Sox wins and the state goes to $(i+1,j)$, or $f(i,j)-y$ if the Red Sox loses and the state goes to $(i,j+1)$. Using this, we can fill in the net payoffs at every possible state. Using the equations:\n $f(i,j+1) = f(i,j)-y$\n$f(i+1,j) = f(i,j)+y$\n So, $f(i,j) = \frac{f(i+1,j)+f(i,j+1)}{2}$\n We can also calculate the bet we need to place at each state using the equation $y=\frac{f(i+1,j)-f(i,j+1)}{2}$, which is essentially our strategy.\n This is a dynamic programming problem, where we work backwards from the final stage to determine the optimal strategy. The problem can be represented as a binomial tree, where the underlying asset either increases or decreases after each step, and the bet we place each time is the delta in dynamic hedging. This approach can be used to solve both European and American options numerically.

https://www.puzzledquant.com/problems/clhros6lj0010mv08azuren9s

Rolling a non-fair die has a greater probability of rolling doubles than rolling a fair die. Is this statement true?

The probability of rolling doubles with a fair $n$-sided die is $\frac{1}{n}$. To prove that a non-fair die has a greater probability of rolling doubles, suppose we have a `fixed` $n$-sided die with probabilities $p_1, ..., p_n$ of rolling sides 1 through $n$ respectively.\n The probability of rolling doubles with this die is $p_1^2 + ... + p_n^2$. We want to show that this is greater than $\frac{1}{n}$.\n Let $e_i = p_i - \frac{1}{n}$ for $i = 1, ..., n$. Then $p_1^2 + ... + p_n^2 = (e_1 + \frac{1}{n})^2 + ... + (e_n + \frac{1}{n})^2 = (e_1^2 + ... + e_n^2) + 2(e_1 + ... + e_n) + \frac{1}{n} \u003e \frac{1}{n}$, as $(e_1 + ... + e_n) = 0$. Therefore, a non-fair die has a greater probability of rolling doubles than a fair die.

https://www.puzzledquant.com/problems/clhros624000ymv08941z69mq

On average, how many times must a fair, $n$-sided die be rolled and summed before the sum reaches at least $n$? Compute for n = 4

We define $E(m)$ to be the expected number of rolls until the sum is at least $n$, starting with a sum of $m$. Then we have:\n$E(n) = 0$\n$E(n-1) = 1$\n$E(n-2) = 1 + \frac{1}{n}E(n-1) = 1 + \frac{1}{n}$\n$E(n-3) = 1 + \frac{1}{n}E(n-2) + \frac{1}{n}E(n-1) = 1 + \frac{2}{n} + \frac{1}{n^2}$\n... \n Thus by induction, we have $E(n − k) = \sum_{i=0}^{k-1} \frac{{k−1}\choose i} {n^i} \text{ for } 1 \leq k$.\n Thus,\n$E(0) = \sum_{i=0}^{n-1} \frac{{n-1}\choose i }{n^i} = \left(1 + \frac{1}{n}\right)^{n-1}$\n As $n\rightarrow \inf , E(0) \approx e $

https://www.puzzledquant.com/problems/clhros36x000mmv08h4ygt3hf

On average, how many rolls would it take to get two of the same face when rolling a fair die?\nFor example, if the run of rolls is $12545$ or $636$, how many rolls would it take?

Let $X$ be the number of rolls required to get two of the same face. We can calculate $P(X = x)$ for $2 \leq x \leq 7$ by enumerating the possibilities.\nIn the $X = 2$ case, we need a run of two consecutive rolls of the same number. There are 6 possible values for the first roll, and only one value for the second roll that will make a pair, so there are 6 possible runs. Therefore, $P(X = 2) = \frac{1}{6}$.\nIn the $X = 3$ case, we need a run of three consecutive rolls that contains a pair. There are 6 possible values for the first roll, 5 possible values for the second roll (excluding the first roll value), and 2 possible values for the third roll (either the first roll value or the second roll value). However, there are two possible orders for the pair (ABA or BAA), so we multiply by 2. Therefore, $P(X = 3) = \frac{5}{18}$.\nSimilarly, we can calculate $P(X = 4)$, $P(X = 5)$, $P(X = 6)$, and $P(X = 7)$ using similar reasoning. The probabilities are shown below:\n$P(X = 2) = \frac{1}{6}$\n$P(X = 3) = \frac{5}{18}$\n$P(X = 4) = \frac{5}{18}$\n$P(X = 5) = \frac{5}{27}$\n$P(X = 6) = \frac{25}{324}$\n$P(X = 7) = \frac{5}{324}$\nTo find the expected number of rolls, we can sum up the product of each possible number of rolls and its corresponding probability. Therefore, the expected number of rolls is:\n$E(X) = 2(\frac{1}{6}) + 3(\frac{5}{18}) + 4(\frac{5}{18}) + 5(\frac{5}{27}) + 6(\frac{25}{324}) + 7(\frac{5}{324})$$= \frac{1223}{324}$$\approx 3.77$

https://www.puzzledquant.com/problems/clhros1eb000emv08yhc4flue

On average, how many rolls of a pair of $6$-sided dice are necessary for all sides to appear at least once?

To solve this problem, we can view the rolling of the dice as a Markov process and define the states based on the number of sides that have appeared so far. We start in State 0 and aim to end up in State 6, reaching some or all of States 1, 2, 3, 4, and 5 along the way.On the very first roll, we will move from State 0 to either State 1 or State 2.\n We move to State 1 with probability $\frac{6} {36}$ , since this happens exactly if we roll “doubles”. Otherwise, we move to State 2, so we move to State 2 from State 0 with probability $\frac{30} {36}$ .\n We can determine the transition probabilities by creating a transition matrix and solving for the expected number of rolls using the formula $(I-Q)^{-1}$, where Q is the matrix of transition probabilities and I is the identity matrix. Summing the first row we find the expected number of rolls until all six sides have appeared gives $n = 7.599$.

https://www.puzzledquant.com/problems/clhrorznd0006mv08x2vvz8q3

On average, how many times must a 6-sided die be rolled until there are two rolls in a row that differ by 1 or no more than 1?\n For example, if the first roll is a $2$, the second roll must be a $1$ or $3$, or if the first roll is a $6$, the second roll must be a $5$. What if we roll until there are two rolls in a row that differ by no more than $1$ (so we stop at a repeated roll, too)?

To find the expected number of rolls until there are two rolls in a row that differ by 1 or no more than 1, we can use the following approach:\nLet $E$ be the expected number of rolls. Let $E_i$ be the expected number of rolls after rolling an $i$ (not following a roll of $i - 1$ or $i + 1$). Then we have\n$E = 1 + (\frac{1}{6})(E_1 + E_2 + E_3 + E_4 + E_5 + E_6)$.\nBy symmetry, we know that $E_1 = E_6$, $E_2 = E_5$ and $E_3 = E_4$, so \n$E = 1 + (\frac{2}{6})(E_1 + E_2 + E_3)$\n We can express $E_1$ as\n$E_1 = 1 + (\frac{2}{6})E_1 + (\frac{1}{6})E_2 + (\frac{2}{6})E_3$\nsince there will definitely be an additional roll, there is a $(\frac{1}{6})$ chance that this will be the last roll (i.e., we roll a 2) and the five other possibilities are equally likely. Similarly,\n$E_2 = 1 + (\frac{1}{6})E_1 + (\frac{2}{6})E_2 + (\frac{1}{6})E_3$\n$E_3 = 1 + (\frac{2}{6})E_1 + (\frac{1}{6})E_2 + (\frac{1}{6})E_3$\n This gives us a system of three linear equations in three unknowns. Solving, we find $E_1 = \frac{70}{17}$, $E_2 = \frac{58}{17}$, and $E_3 = \frac{60}{17}$, and so $E = \frac{239}{51} = 4.686....$\nIf we stop when we have a repeated roll, too, the situation is similar.

https://www.puzzledquant.com/problems/clhrexr820004l6084op57epb

Johnny and you were playing a game. Johnny was standing $10$m away from the centre of a circular tree with a radius of $1$m, while you were standing on the opposite side of the tree, also $10$m away from the centre. The game was that if you could reach the tree without being seen, you would win, but if Johnny could see you without his line of sight being blocked by the tree, he would win.\n What was the minimum constant speed you had to run at to win the game, if Johnny was running at $5$m/s?

Suppose we run in a straight line towards the tree with speed $k$, then after $t$ seconds we will be $10-kt$ metres from the tree.\n\nDrawing a tangent from our position to the tree, we establish that Johnny must run $\frac{20-kt}{10-kt}$ metres. Therefore we can evade Johnny only if $5t(10-kt) \u003c 20-kt$.\n\nThis occurs when the quadratic equation has no real solution for $t$. This happens when the discriminant $(50+k)^2 - 400k$ is negative. \n\nHence minimum speed is $50(3- 2\sqrt{2})$.

https://www.puzzledquant.com/problems/clhrexqs30002l608jui31ony

Rabbit's Chance of Making One Leftwards Jump

A rabbit started at stone $1$ in a row of $7$ stones, labelled $1$ to $7$ from left to right. On each turn, the rabbit hopped to a new stone that it hadn't visited yet. What is the probability that the rabbit made exactly one leftwards jump after visiting all the stones?

The probability that the rabbit made exactly one leftwards jump after visiting all the stones is $\frac{57}{720}$ or $\frac{19}{240}$.\n This can be calculated by counting the number of possible sequences for the rabbit. There are $6! = 720$ possible sequences for the rabbit.\n To calculate the number of sequences that correspond to exactly one leftwards jump, we need to count the number of ways of partitioning $[2, 3, 4, 5, 6, 7]$ into two groups $A$ and $B$. The rabbit hops from stone $1$ to all the stones in group $A$ from left to right, followed by all the stones in group $B$ from left to right. If $B$ is empty or a suffix of $[2, 3, 4, 5, 6, 7]$, then the rabbit makes no leftwards jump so we excluded these cases. There are $2^6 = 64$ ways of choosing $B$ and after taking away the exceptions, we reach the answer $\frac{2^6 - 7}{6!} = \frac{57}{720}$.

https://www.puzzledquant.com/problems/clhudgg8s001emm08lfxy5oab

A basketball player decided to practice his free throws. He has exactly $100$ shots to make and will score one point if the ball passes through the hoop and zero point if it doesn't. On his first try, he makes a basket, but unfortunately, he missed the next one. However, for each throw, the probability of him scoring depends on the fraction of throws he has already made. For example, if he has made $\frac{23}{40}$ baskets after making 40 shots, the probability of him making a basket on his $41^{st}$ shot is $\frac{23}{40}$. Now, the question is, what is the probability that he makes exactly $50$ baskets after taking all 100 shots (including the first two)?

We need to find the probability that she makes exactly $50$ baskets after taking all $100$ shots. Let $(n,k)$, $1\u003ck\u003cn$, be the event that the player scores $k$ baskets after $n$ throws and $P_{n,k} = P((n,k))$.\n We can use an induction approach starting with $n=3$. The third throw has $\frac{1}{2}$ probability of scoring. So we have $P_{3,1}=\frac{1}{2}$ and $P_{3,2}=\frac{1}{2}$.\n For the case when $n=4$, we apply the law of total probability. $P_{4,1} = P((4,1)| (3,1)) P_{3,1} + P((4,1)| (3,2)) P_{3,2} = \frac{2}{3}\cdot \frac{1}{2} + 0 \cdot \frac{1}{2} = \frac{1}{3}$\n$P_{4,2} = P((4,2)| (3,1)) P_{3,1} + P_((4,2)| (3,2)) P_{3,2} = \frac{1}{3}\cdot \frac{1}{2} + \frac{1}{3} \cdot \frac{1}{2} = \frac{1}{3}$\n $P_{4,3} = P((4,3)| (3,1)) P_{3,1} + P_((4,3)| (3,2)) P_{3,2} = 0\cdot \frac{1}{2} + \frac{2}{3} \cdot \frac{1}{2} = \frac{1}{3}$\n The results indicate that $P_{n,k} = \frac{1}{n-1}$, $k = 1,2,\dots,n-1$, and give the hint that the law of total probability can be used in the induction step.\n Assume $P_{n,k} = \frac{1}{n-1}$,\n $P_{n+1,k} = P(miss| (n,k))P_{n,k} + P(score | (n,k-1))P_{n,k-1} = \frac{n-k}{n}\cdot \frac{1}{n-1} + \frac{k-1}{n}\cdot\frac{1}{n-1} = \frac{1}{n} $\n Hence, $P((100,50)) = \frac{1}{99}$

https://www.puzzledquant.com/problems/clgfh6scd0018la08vjt74al0

A countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces away from the beginning of the line, and each prisoner can see all the hats in front of him, and none of the hats behind. Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot. As before, the prisoners have a chance to meet beforehand, but unlike before, once in line, no prisoner can hear what the other prisoners say. The question is, is there a way to ensure that only finitely many prisoners are killed?

It uses Axiom of choice in a special way. Before night of execution, prisoners will create some equivalent classes among the set of all possible infinitely long binary strings.\n Let us say two infinite strings s1 and s2 are related, if they differ at finitely many places, and are same otherwise. This creates the equivalence relation. Thus they create all equivalence class. From each class, we mark one representative string. Now, a person pi looks ahead, and instantly knows his equivalent class \u0026 recalls the representative string S. When his turn comes, he speaks the ith digit of S as his guess. Since S and actual (current) string only differ upto a finite (say N) number of position. Thus only atmost N people may die using this technique.Now, first person will count number of places S differs from current string, and answer it in modulo 2. Based on answer of first person, second person can deduce his hat color. now the third person can deduce his color and so on. Except possibly for the first person, everyone will guess correctly.

https://www.puzzledquant.com/problems/clgfh6r3t0012la083xs9a066

In a room stand $n$ armed and angry people. At each chime of a clock, everyone simultaneously spins around and shoots a random other person. The persons shot fall dead and the survivors spin and shoot again at the next chime. Eventually, either everyone is dead or there is a single survivor.As $n$ grows, what is the limiting probabality that there will be a survivor?

https://www.puzzledquant.com/problems/clgfh6ooh000qla08h7g6ok06

Can you pack 53 bricks of dimensions $1$x$1$x$4$ into a $6$x$6$x$6$ box? The faces of the bricks are parallel to the faces of the box

The solution employs the pigeon hole principle. Divide the volume of $6$x$6$x$6$ box into $2$x$2$x$2$ mini cubes. Imagine each of these mini cubes is either fully red or fully blue such that it forms a 3D checkerboard pattern on the box. This will restrict $14$-$13$ restriction on cube colors, say $14$ blue and $13$ red. Now, putting bricks into box, parallel to faces, each brick will be half blue and half red, so $52$ bricks fill all the red cubes and there is no way to place a $53rd$ brick.

https://www.puzzledquant.com/problems/clgfh6o3l000ola08ygac9sta

Imagine you're driving on a circular race track with no gas in your car's tank. You notice that there are $N$ gas cans scattered at different points on the track, and the total amount of gas in these cans is exactly enough to complete one full lap. Is it possible to choose a starting position on the track where you can pick up all the gas cans and complete the circle without running out of gas?\n If the answer is yes, think of an algorithm to find the point. If it's a no, prove why it isn't possible?

Imagine having a big tank with enough gas for a round trip and enough room for going through the motions of emptying every gas station on your way. Start at any station and mind to record the amount of gasoline on reaching gas stations on your way around. At the end of the trip, when you pull into the station of departure with the original amount of gas, check your list. The station marked with the least number is the one where you want to start on an empty tank.\n Another Solution: We assume that the circle has a circumference of $1$. For $N=1$, we can start at the gas can. For $N=2$, we can start at gas can $1$ if $x_1\geq y_1$, where $x_1$ and $y_1$ are the distances the car can travel from gas can $1$ and gas can $2$, respectively. Otherwise, we start at gas can $2$. For $N=n+1$, we can combine gas cans $i$ and $i+1$, where $x_i$ and $x_{i+1}$ are the distances the car can travel from gas cans $i$ and $i+1$, respectively, if $x_i\geq y_i$ for some $i$. This reduces the problem to $N=n$, which we have already shown to be solvable. Therefore, we can always choose a starting position on the track to complete the entire circle for any $N$. Alternatively, we can start at the gas can corresponding to the lowest measurement of the amount of gas in the tank after driving a full circle with another car with enough gas to finish the circle.

https://www.puzzledquant.com/problems/clgfh6nb8000kla08vuwgyib2

A group of $5$ people want to keep their secret document in a safe. They want to make sure that in future, only a majority (\u003e=3) can open the safe. So they want to put some locks on the safe, each of the locks have to be opened to access the safe. Each lock can have multiple keys; but each key only opens one lock. How many locks are required at the minimum?

For each group of 2 people, there must be a lock which none of them have a key to. But the key of such a lock will be given to the remaining $3$ people of group. Thus, we must have atleast $5\choose2$ = $10$ Locks.\n Each lock has 3 keys, which is given to unique 3-member subgroup. So each member should have $\frac{10*3}{5}$ = $6$ keys.

https://www.puzzledquant.com/problems/clgfh6mz5000ila08dpvlefv5

$$10$ undercover agents have been found in don's lair. Less than half of them are terrorists and the rest are anti-terrorists. The nature of their job is so secret that there is no proof what so ever to testify who is who. Although each of them knows who was actual terrorist and who was anti because they worked in teams. A query consists of asking person $i$ if person $j$ is Anti. Anti will always speak truth but a terrorist may lie to confuse you. The goal is to find out one anti in fewest queries.\n How many queries would you need ?

Note that this question cannot be solved with any algorithm if terrorists are more than or equal to anti, because terrorists can plan to always lie. Taking only $N-1$ queries, we will try to find a chain of persons $(i_1,i_2,i_3....i_m)$ such that each $ij$ is queried about $i(j+1)$ and answer is correct.\n Note that if such chain contains an anti then last person in the chain would be anti. So query person $1$ about $2$. If answer is yes query person $2$ about $3$, continue till answer is correct.\n Suppose at some point person $i$ when queried about person $j$ says wrong, in that case remove person $i$ and $j$ from the chain, and continue query process by querying predecessor of $i$ about successor of $j$. Here note that when we remove person $i$ and $j$ from the chain at-least one of them must be faulty. Here, for each person except the first one, we are querying once. Hence $N-1$ comparison in worst case.

https://www.puzzledquant.com/problems/clgfh6mi8000gla08f23z30n1

Two immensely intelligent players, $A$ \u0026 $B$, engage in a game, the rules of which are as follows. For some natural number $N$, the board consists of numbers from $1$ to $N$. Each player takes turns to strike off a (new) number from the board. But, to make sure $N$ does't affect who wins, there is an added rule. Once you strike of a number, you also have to strike off all its divisors in that same chance, irrespective of whether any of those divisors were already marked. The player to strike off the last number on the board wins. Can $A$ construct a winning strategy?

Thanks to Pelican in comments for this solution.\nThe guy who plays first wins. Suppose A is playing first, if he has a winning strategy then done. Else, remove 1. Since A does not have a winning strategy B has a strategy no matter what A picks in his first move. Say if B was supposed to pick x next, but if A had picked x first then even 1 would have gone off and A would have effectively played out B's winning strategy hence making him the winner (a contradiction). Hence the person who picks first wins.

https://www.puzzledquant.com/problems/clgfh6lpo000cla082imxvjyp

A spy is located on a one-dimensional line. At time $0$, the spy is at location $A$. With each time interval, the spy moves $B$ units to the right (if $B$ is negative, the spy is moving left). $A$ and $B$ are fixed integers, but they are unknown to you. You are to catch the spy.\n The means by which you can attempt to do that is: at each time interval (starting at time $0$), you can choose a location on the line and ask whether or not the spy is currently at that location. That is, you will ask a question like "Is the spy currently at location $27$?" and you will get a $yes/no$ answer. Is it possible to find the spy? If yes, how?

Integer 2-tuples ($x,y$) are countable, there exists a function $f:N \rightarrow N*N$ such that $f$ covers all integer 2-tuples.\n Let $f(n)=(f_1(n),f_2(n))$. The algorithm will be to check for location $f_1(n)+n*f_2(n)$ at time instant $n$. Given $A$ and $B$, there exists $n_0$ such that $f(n0)=(f1(n0),f2(n0))=(A,B)$, and thus at time instant $n_0$ we will be checking for location $f_1(n_0)+n_0*f_2(n_0)$ which is $A+B*n_0$ -- the actual location of the spy.

https://www.puzzledquant.com/problems/clhudgdg90012mm0848ih1ise

You've just invested in stock $A$ and want to protect yourself from potential losses by shorting stock $B$. You're wondering how many shares of $B$ you should short to reduce the risk of your overall investment. Assuming that stock $A$'s return variance is $\sigma_A^2$, and stock $B$'s is $\sigma_B^2$; plus the correlation coefficient between them is $p$, what's the minimum number of shares of $B$ you should short to minimize the variance of your hedged position? Consider correlation coefficient between stocks $\rho =0.1$, $\sigma_A = 0.2 , \sigma_B = 0.4$

To protect your investment in stock A from potential losses, you can short stock B. To minimise the risk, you need to determine the number of shares of B to short.\n Let's assume that you short $h$ shares of B. The variance of the portfolio return is given by $var(r_A -hr_B) = \sigma_A^2 - 2\rho\sigma_A\sigma_Bh + h^2\sigma_B^2$. To minimize the variance of the hedged position, we need to find the best hedge ratio. We can do this by taking the first-order partial derivative with respect to $h$ and setting it to zero. This gives us $\rho = h\frac{\sigma_B}{\sigma_A}$. Solving for $h$, we get $h = \rho\frac{\sigma_A}{\sigma_B}$\n To confirm that this is the minimum, we can check the second-order partial derivative, which is $2\sigma_B^2 \u003e 0$. Therefore, when you short $h = \rho\frac{\sigma_A}{\sigma_B}$ shares of stock B, your hedge portfolio will have the minimum variance. This concept is called portfolio hedging using correlation coefficients and partial derivatives.

https://www.puzzledquant.com/problems/clhudgebi0016mm08lb15josj

You're at a bus station waiting for the next bus to arrive. The buses show up sporadically following a Poisson process, which means that they arrive with an average of $10$ minutes in between each other. Assuming that the buses have been running for quite some time, and you end up arriving at the bus station at a random moment, on average, how many minutes have passed since the last bus departed from the station?

The problem asks us to find the expected waiting time for the next bus and the average time since the last bus departed from the station. We can model the arrival of buses using a Poisson process with an average arrival rate of 10 minutes. \n$f(t) = \lambda e^{-\lambda t} ; t\geq 0$\n The expected arrival time of exponential distribution is $\frac{1}{\lambda}$ and the variance is $\frac{1}{\lambda^2}$. The time interval between two consecutive buses follows an exponential distribution with a mean of $10$ minutes. Exponential distribution has memorylessness property i.e $P( \tau \u003es+t | \tau \u003es) = P(\tau \u003e t)$, where $\tau$ is the random variable for arrival time. The memoryless property of the exponential distribution tells us that the expected waiting time for the next bus is also $10$ minutes, regardless of how long we have already waited. \nTo find the average time since the last bus departed, we can use the same exponential distribution with a mean of $10$ minutes. This is because the memoryless property still holds when we look back in time. Therefore, on average, the last bus arrived $10$ minutes ago as well.

https://www.puzzledquant.com/problems/https://www.puzzledquant.com/problems/clhros10d000cmv08nu448j0z

On average, how many times do you need to roll a $6$-sided die until all sides have appeared at least once? \n

This is just a variation of the coupon collector problem.\n The expected number of rolls needed to roll a 6-sided die until all sides have appeared at least once is $14.7$ rolls, as explained in the solution. For an $n$-sided die, the expected number of rolls needed is given by the formula:$$1 + \frac{n}{n-1} + \frac{n}{n-2} + ... + \frac{n}{2} + \frac{n}{1}$$This can be simplified as:$$n \times \left(\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n}\right)$$which is the $n$th harmonic number. For large $n$, the $n$th harmonic number is approximately equal to the natural logarithm of $n$, so the expected number of rolls needed for an $n$-sided die is approximately $n \log n$.

https://www.puzzledquant.com/problems/clhudgnlg0026mm0855e3uejt

Once the pirate team had divided their loot peacefully, their group became bigger with total of $11$. However, they needed a secure way to protect their hard-earned treasure. They decided to put all their loot in a safe, but being a democratic group, they agreed that the safe should only be opened by a majority of them, which means more than $5$ pirates. For this reason, they hired a locksmith to put locks on the safe. To access the treasure, all locks must be opened, and each lock can only be opened with one key. The locksmith can provide multiple keys to each pirate.\n Can you determine the minimum number of locks needed and the number of keys each pirate should carry to open all locks?

To solve this, we randomly select $5$ pirates from the $11$-member group. There must be a lock that none of them has the key to. However, any of the other $6$ pirates must have the key to this lock since any $6$ pirates can open all locks. In other words, we must have a “special” lock to which none of the $5$ selected pirates has a key and the other $6$ pirates all have keys. Such $5$-pirate groups are randomly selected. So for each combination of $5$ pirates, there must be such a “special” lock. \nLet's denote the number of locks needed as $L$ and the number of keys each pirate should carry as $K$. Since there is one lock of every combination of $5$ pirates.\n $L = \binom{11}{5}$. Solving this equation, we get $L = 462$.\nEach lock has 6 keys, which are given to a unique 6-member subgroup. Therefore, the number of keys each pirate should carry is:\n$K = \frac{L \times 6}{11} = \frac{462 \times 6}{11} = 252$\n

https://www.puzzledquant.com/problems/clhudgk00001smm08jg2ed4zw

At a movie theater you are waiting in line and the manager suddenly announces a whimsical giveaway. She will give a free ticket to the first person in line whose birthday matches with someone who has already bought a ticket. You have the opportunity to choose any position in line. However, you do not know anyone else's birthday and all birthdays are evenly distributed throughout the year (assuming $365$ days in a year). Which position in line will give you the best chance of getting the free ticket?

Assuming that all birthdays are evenly distributed throughout the year, we can calculate the probability of getting the free ticket for any position in the line. Let $p(n)$ be the probability of getting the free ticket if you are the $n^{th}$ person in line. To calculate $p(n)$, we need to find the probability that the first $n-1$ people in line have different birthdays and your birthday matches with one of those $n-1$ people. This can be calculated as $p(n) = \frac{365}{365} \times \frac{364}{365} \times ... \times \frac{365-n+2}{365} \times \frac{n-1}{365}$. \nTo find the best position in the line, we need to find the value of $n$ for which $p(n)$ is maximum. It can be shown that $p(n)$ increases with $n$ when $n$ is small, but eventually decreases as $n$ increases. Therefore, we need to find the value of $n$ for which $p(n)$ is maximum and greater than $p(n-1)$ and $p(n+1)$.\n $p(n)\u003ep(n+1) = n^2 - n- 365 \u003e0 $\n$p(n)\u003ep(n-1) = n^2-3n-363\u003c0$ \n Solving these equations give $n=20$\nUsing mathematical calculations, we can find that $p(n)$ is maximum when $n=20$, and $p(20)$ is greater than $p(19)$ and $p(21)$. Therefore, you should choose to be the $20^{th}$ person in line to have the best chance of getting the free ticket.

https://www.puzzledquant.com/problems/clhudgism001omm08l99h67oy

A small pond has a single amoeba living inside it. This particular amoeba has a unique ability, where every minute it can either die, stay alive, split into two, or split into three, each with an equal probability. The offspring produced by this amoeba will also have the same behavior, and will act independently of other amoebas. What is the likelihood that this amoeba population will eventually die out?

We can use the law of total probability conditioned on what happens to the amoeba one minute later. Let $P(E)$ be the probability that the amoeba population will die out. For the original amoeba, there are four possible mutually exclusive events each with probability $\frac{1}{4}$.\n Let $F_1$ be the event the amoeba dies, $F_2$ be the event that it stays the same, $F_3$ be the event that it splits into two, and $F_4$ be the event that it splits into three. For event $F_1$, $P(E|F_1)=1$ since no amoeba is left. For $F_2$, $P(E|F_2)= P(E)$ since the state is the same as the beginning. For $F_3$, there are two amoebas; either behaves the same as the original one. The total amoeba population will die only if both amoebas die out. Since they are independent, the probability that they both will die out is $P(E)\cdot P(E)$. Similarly, we have $P(F_4) = P(E)^3$. We can plug in all the numbers and the equation becomes\n$P(E) = P(E|F_1)P(F_1) + P(E|F_2)P(F_2) + P(E|F_3)P(F_3) + P(E|F_4)P(F_4)$\n $P(E)= \frac{1}{4}\cdot 1+\frac{1}{4}\cdot P(E)+\frac{1}{4}\cdot P(E)^2 +\frac{1}{4}\cdot P(E)^3$\n Solving this equation with the restriction $0 \u003c P(E) \u003c 1$, we get $P(E) = \sqrt(2)-1 = 0.414$. Therefore, the likelihood that this amoeba population will eventually die out is $0.414$

https://www.puzzledquant.com/problems/clhudgi9n001mmm08znlrlo42

Two friends named $A$ and $B$ are playing a coin-tossing game. They take turns tossing a fair coin. If the sequence of heads and tails forms a $HT$ subsequence, the game ends and the player who tosses the tail wins. $A$ goes first, followed by $B$, and the game continues in this pattern. What is the chance of $A$ winning the game?

Let $P(A)$ be the probability that A wins, then the probability that B wins is $P(B) = 1 - P(A)$. We can condition $P(A)$ on A's first toss, which has a $\frac{1}{2}$ probability of $H$ and $\frac{1}{2}$ probability of $T$. \nIf A's first toss is $T$, then B becomes the first to toss, and $P(A|T) = P(B) = 1 - P(A)$. If A's first toss ends in $H$, let's further condition on B's first toss. B has a $\frac{1}{2}$ probability of getting $T$, in which case A loses. For the $\frac{1}{2}$ probability that B gets $H$, B becomes the first one to toss an $H$, and A has $(1 - P(A|H))$ probability of winning. So $P(A|H) = \frac{1}{2} * 0 + \frac{1}{2} * (1 - P(A|H)) \rightarrow P(A|H) = \frac{1}{3}$. \nCombining all the available information, we have $P(A) = \frac{1}{2} * \frac{1}{3} + \frac{1}{2} * (1 - P(A)) \rightarrow P(A) = \frac{4}{9}$. This means that A has a $\frac{4}{9}$ probability of winning the game. This result is reasonable since A cannot win in his first toss.

https://www.puzzledquant.com/problems/clhudgh9w001imm08b4s0sqy6

In a game, $52$ cards are randomly distributed among $4$ players, with each player receiving $13$ cards. What is the likelihood that each player will receive an ace?

The problem is to find the probability that each of the 4 players in a game of cards receives an ace. We can solve this problem using standard counting methods. \nFirst, we distribute the $4$ aces among the $4$ players, which can be done in $4!$ ways. Then, we distribute the remaining $48$ cards among the $4$ players, with each player receiving $12$ cards. Now we can make $4$ groups of $12$ cards in $\frac{48!}{12!12!12!12!}$ ways. \nThe total number of ways to distribute the cards, such that every player has an Ace = $4! \cdot \frac{48!}{12!12!12!12!}$. \nTo find the probability that each player receives an ace, we divide the number of ways to distribute the cards such that each player receives an ace by the total number of ways to distribute the cards i.e $\frac{52!}{13!13!13!13!}$.\nTherefore, the probability that each player receives an Ace is $\dfrac{ \frac{48! 4!}{12!12!12!12!}}{\frac{52!}{13!13!13!13!}}$ \nWe can simplify this expression to get: $ p = 1 \times \dfrac{39}{51} \times \dfrac{26}{50} \times \dfrac{13}{49}$\n

https://www.puzzledquant.com/problems/clhudgfa5001amm08wh8z09vu

Two bankers each arrive at the station at some random time between $5:00$ AM and $6:00$ AM (arrival time for either banker is uniformly distributed). They stay exactly five minutes and then leave. What is the probability they will meet on a given day?

To solve the problem of two bankers meeting at the station, we need to calculate the probability of the overlap between their arrival times. Let's assume that banker A arrives $X$ minutes after 5:00 am and banker B arrives $Y$ minutes after 5:00 am. $X$ and $Y$ are independent uniform distributions between 0 and 60. If we plot their arrival times on a graph, we can see that they will meet if and only if the absolute difference between their arrival times is less than 5 minutes. \n We represent this problem on graph with the sample space being a square with opposite corners at $\{(0,0),(60,60)\}$. The two bankers meet if $|X-Y|\leq 5$, hence we shade this region. To calculate the probability of this happening, we need to find the area of the shadowed region in the graph, which represents the possible values of $X$ and $Y$ that satisfy the condition. The rest of the region can be combined to form a square with sides of length 60. \nUsing some basic geometry, we can calculate the area of the shadowed region to be $\left(60+55\right)\times\left(60-55\right) = 575$. The area of the square is $60\times60 = 3600$. Therefore, the probability of the two bankers meeting is the ratio of the area of the shadowed region to the area of the square, which is $\frac{575}{3600} = \frac{23}{144}$

https://www.puzzledquant.com/problems/clhudgcg8000ymm081hxi3960

What is the expected number of cards that need to be turned over in a regular $52$-card deck in order to see the first ace?

To find the expected number of cards needed to be turned over before finding the first ace, we can label the cards as 1, 2, ..., 48, and the aces as $A_1$, $A_2$, $A_3$, $A_4$. Define random variable $X_i = 1$ ; if the $i^{th}$ card is turned over before the four aces, $0$ otherwise. Let $X$ be the total number of cards that need to be turned over in order to see the first ace.\n$X = 1 + \sum_{i=1}^{48} X_i$\n Using Linearity of Expectation\n $E[X] = 1 + \sum_{i=1}^{48} E[X_i]$\n The four aces divide the deck into 5 regions $1 A 2 A 3 A 4 A 5$. We know that the probability of any card $i$ appearing in before the four Aces is $\frac{1}{5}$, since each card is equally likely to be in one of the $5$ regions. Therefore, $E[X_i] = \frac{1}{5}$. This gives us $E[X] = 1 + \sum_{i=1}^{48} E[X_i] = 1 + \frac{48}{5} = 10.6$\nThis problem is a special case of the more general problem of finding the expected position of the first occurrence of a special card in a random ordering of $m$ ordinary cards and $n$ special cards. The formula for the expected position of the first special card is $1 + \frac{m}{n+1}$.

https://www.puzzledquant.com/problems/clhudgoov002amm0891on3bex

Imagine you are drawing $7$ random points on the edge of a circular cake. What is the chance that all of these points will be located within a half of the cake?

We are given $N$ random points on the edge of a circular cake, and we want to find the probability that all of these points will be located within a half of the cake. Let's label the points clockwise as $1$, $2$, ..., $N$ starting from one point. The probability that all the remaining $N-1$ points from $2$ to $N$ are in the clockwise semicircle starting at point $1$ is $\frac{1}{2}$. Similarly, the probability that a clockwise semicircle starting at any point $i$, where $i$ is between $2$ and $N$, contains all the other $N-1$ points is also $\frac{1}{2}$. These events are mutually exclusive, meaning that if we start at point $i$ and encounter all other points within half a circle, we cannot do the same starting from any other point. Therefore, the probability of all $N$ points fitting into a clockwise semicircle starting at any point is $\frac{N}{2^{N-1}}$.\n For more intiution you can think the experiment as first placing point $1$ on the circle and then considering it as the starting point all other points can be placed in the semicircular arc with probability $\frac{1}{2}$. For all the points it becomes ${\frac{1}{2}^{N-1}}$. This is formally : $P$(all points lying in semicircle | start point is $1$)\n Now we use union theorem of probability, i.e. for partitions $a$ of sample space $S$\n $P(x) = \cup_{a \in S} P(x|a)$\n For mutually exclusive partitions,\n $P(x) = \sum P(x|a)$\n Since all partition have the same probability as any point could have been the starting point. The probability sums to $\frac{N}{2^{N-1}}$ \nThis argument can be extended to any arcs that have a length less than half a circle. If the ratio of the arc length to the circumference of the circle is $x$ ($x \u003c\frac{1}{2}$), then the probability of all $N$ points fitting into the arc is $N*\left(\frac{x}{2}\right)^{N-1}$.

https://www.puzzledquant.com/problems/clhudgbvr000wmm08zvc9ukye

You are given $6$ random variables, $X_1$, $X_2$, ... , and $X_6$. Each of these variables has a uniform distribution that ranges from $0$ to $1$. Your task is to determine the probability that the sum of these variables, denoted as $S$, is less than equal to $1$. Can you solve this problem?

To approach this problem, we can start with simpler cases and try to find a pattern. When $n=1$, the probability that $S$ is less than equal to 1 is 1. When $n=2$, the probability that $S$ is less than 1 is the area under the triangle formed by $X_1+X_2 \leq 1$ within the square with side length 1, which is $\frac{1}{2}$. When $n=3$, the probability that $S$ is less than 1 is the volume of the tetrahedron formed by $X_1+X_2+X_3 \leq 1$ within the cube with side length 1, which is $\frac{1}{6}$.\n Based on these observations, we can guess that the solution is $\frac{1}{n!}$. To prove it, we can use induction. Assume that $P(S_n \leq 1)=\frac{1}{n!}$. We need to prove that $P(S_{n+1}\leq 1)=\frac{1}{(n+1)!}$. Here we use probability by conditioning. Conditioned on the value of $X_{n+1}$ we have\n $P(S_{n+1} \leq 1 ) = \int_0^1 f(X_{n+1}) P(S_n \leq 1 - X_{n+1})dX_{n+1}$\n where $f(X_{n+1})$ is the probability density of $X_{n+1}$, so $f(X_{n+1})=1$. To calculate $P(S_n \leq 1 - X_{n+1})$, we shrink every dimension of $n$ dimensional simplex from 1 to $1 - X_{n+1}$. So its volume should be $\frac{(1- X_{n+1})^n}{n!}$ instead of $\frac{1}{n!}$. Plugging in these results we get\n $P(S_{n+1} \leq 1) = \int_0^1 \frac{(1-X_{n+1})^n}{n!}dX_{n+1} = \frac{1}{n!}\left[- \frac{(1 - X_{n+1})^{n+1}}{n+1}\right]_0^1 = \frac{1}{n+1}\times \frac{1}{n!} = \frac{1}{(n+1) !} $

https://www.puzzledquant.com/problems/clhudgad8000qmm086mmsgigc

Let $X_1,X_2,...,X_n$, be IID random variables with uniform distribution between $0$ and $1$.\nWhat are the cumulative distribution function, the probability density function and expected value of $Z =\max(X_1,X_2,...,X_n)$? What are the cumulative distribution function, the probability density function and expected value of $Y = \min(X_1,X_2,...,X_n)$? \n Compute $Z-Y$ for $n=11$

This is a very important result and a number of variations of this problem come up in many placement tests.\nFor a series of independent and identically distributed (IID) random variables with a uniform distribution between $0$ and $1$, we can calculate the necessary functions for $Z$ and $Y$. $Z$ represents the maximum value of the random variables, while $Y$ represents the minimum value. For uniform distribution of random variable $X \in$ $[0,1]$, $ CDF \rightarrow F_X(x) = x$ and PDF$ \rightarrow f_X(x) =1$ \nApplying cumulative distribution function (CDF) and probability density function (PDF) of $X$, we get\n$P(Z_n \leq x) = (P(X \leq x))^n \rightarrow F_{Z_n}(x) = (F_X(x))^n = x^n$\n We obtain the PDF by differentiating $F_{Z_n}(x)$ w.r.t $x$ \n $f_{Z_n}(x) = nx^{n-1}$\n Using formula of expected value $E[X] = \int x P(X=x)dx$\n$E[Z_n] = \int_0^1 f _{Z_n}(x)dx = \int_0^1 nx^ndx = \frac{n}{n+1}[x^n]_0^1 = \frac{n}{n+1}$\n \nTo determine the CDF and PDF of $Y$, we use the fact that $Y = 1 - Z$\n $P(Y_n \geq x) = (P(X \geq x))^n \rightarrow F_{Y_n}(x) = 1 - (1 - F_X(x))^n = 1 - (1 -x)^n$\n$f_{Y_n}(x) = n(1-x)^{n-1}$\n Again using the definition of expectation $E[X] = \int xP(X=x)dx$, we get\n$ E[Y_n] = \int_0^1 nx(1-x)^{n-1}dx = \int_0^1 n(1-y)y^{n-1}dy = [y^n]_0^1 - \frac{n}{n+1}[y^{n+1}]_0^1 = \frac{1}{n+1}$

https://www.puzzledquant.com/problems/clhudg9eo000mmm08opjz067x

$$500$ ants are placed on a $1$-foot string without any order. Assume independent uniform distribution for each ant. Each ant will move randomly towards either end of the string at a constant speed of $1$ foot per minute. The ants will keep moving until they reach the end of the string, and if two ants collide head-on, they will both immediately turn around and continue moving. Assuming that the size of the ants is infinitely small, what is the expected time for all $500$ ants to fall off the string?

We first use the principle that for two ants collision has the same effect as two ants passing through each other, which means collisions have no effect on an ant. Also since there is uniform random distribution of ants and left and right ends are symmetrical, we just consider all ants to be facing left and placed uniformly on the stick (IID events).\n The speed of ants is $1foot/min$ and the question simplifies to calculating the expected length of the farthest ant from the left end. As that is the ant which will fall at last. \n Now we can find the expected value either by integration or using Linearity of expectation. Here we show it by integration method.\n $Z_n = max(X_1 , X_2 .. X_n)$ \n$ P(Z_n \u003c= x) = (P(X_i \u003c= x ))^n = x^n $\n From the CDF, we obtain the pdf by differentiation\n $f_{Z_n}(x) = nx^{n-1}$\n $E[Z_n] = \int_0^1 xf_{Z_n}(x)dx = \int_0^1 nx^ndx = \frac{n}{n+1} [x^{n+1}]_0^1 = \frac{n}{n+1}$\n Hence the Expected value of longest length from the end is $\frac{500}{501}$. Dividing with $1foot/min$ gives the expected value of time till the last ant drops off the stick = $\frac{500}{501}$

https://www.puzzledquant.com/problems/clhudg8ug000kmm08nby1ug0e

Player M has $1$ dollar and player N has $2$ dollars. Each game gives the winner $1 from the other. As a better player, M wins 2/3 of the games. They play until one of them is bankrupt. Whatis the probability that M wins?

In this game, player $M$ and $N$ play until one of them is left without any money. $M$ wins 2 out of 3 games played. At the start, $M$ has $\$1$ and $N$ has $\$2$. The state space can be defined as the combination of the money that player $M$ has ($m$) and the money that player $N$ has ($n$). Since neither $m$ nor $n$ can be negative, the state space can be simplified to $\{m\} = \{0,1, 2,3\}$. The transition matrix and graph can be used to calculate the probability of $M$ winning.\n The initial state is $X = 1$ ($M$ has $\$1$ at the beginning). At state 1, the next state is 0 (M loses a game) with probability $\frac{1}{3}$ and 2 (M wins a game) with probability $\frac{2}{3}$. Similarly, we can get the probabilities for other states. Both state 3 (M wins the whole game) and state 0 (loses the whole game) are absorbing states.\n Using absorption probability equations, we can calculate the probability that $M$ reaches absorbing state 3. Plugging in the transition probabilities, we get $a = \frac{4}{7}$. Therefore, starting from $\$1$, player M has a $\frac{4}{7}$ probability of winning. The concepts used in this solution are Markov chain, state space, transition matrix, transition probabilities, and absorption probability equations.

How to calculate absorption probabilities Using tp matrix ( notion notebook )

https://www.puzzledquant.com/problems/clhudg8e7000imm08yy7e7xrv

Two friends, Alex and Ben, enjoy playing a game of dice. They roll a pair of standard six face die and record the sum. They place a bet on who will get the desired result first. Alex is optimistic and bets that the sum $12$ will appear first. Meanwhile, Ben places his bet on two consecutive $7s$. They continue playing until one of them reaches their winning condition. What is the probability of Alex winning?

We can solve this problem using conditional probability arguments. Let $P(A)$ be the probability that Alex wins. We can condition $P(A)$ on the first throw's sum $F$, which has three possible outcomes $F=12$, $F=7$, and $F !=\{7,12\}$.\n Using simple permutation, we can easily see that $P(F=12)=\frac{1}{36}$, $P(F=7)=\frac{6}{36}$, $P(F!=\{7,12\})=\frac{29}{36}$. Also, $P(A|F=12)=1$ and $P(A|F!=\{7,12\})=P(A)$. To calculate $P(A|F=7)$, we need to further condition on the second throw's total, which again has three possible outcomes: $E=12$, $E=7$, and $E!=\{7,12\}$.\n$P(A) = P(A|F=7)P(F=7) + P(A|F=12)P(F=12) + P(A|F != \{7,12\})P(F!=\{7,12\})$\n$P(A|F=7) = P(A|F=7,E=12)P(E=12|F=7) + P(A|F=7,E=7)P(E=7|F=7) + P(A|F=7,E!=\{7,12\})P(E!=\{7,12\}|F=7)$\nThe second equation relies on the independence of first and second throws. Now we have all the necessary information for $P(A)$. Plugging it into the original equation, we get $P(A)=\frac{7}{13}$.\n Alternatively, we can use a Markov chain approach. We have two absorbing states, $12$ (A wins) and $7-7$ (B wins), at least two transient states, $S$ (starting state) and $7$ (one $7$ occurs, yet no $12$ or $7-7$ occurred). All we need are states $S$, $7$, $7-7$, and $12$. Compute the transition graph and probability to reach state $12$. The transition probability is again derived from conditional probability arguments.

https://www.puzzledquant.com/problems/clhudg7xg000gmm08jfcd42b6

You're playing a coin-tossing game where you flip a fair coin repeatedly until you get either $HHH$ or $THH$ consecutively. What is the probability of getting an $HHH$ subsequence before a $THH$ subsequence?

First let's find the expected number of coin tosses to get either $HHH$ or $THH$. To solve this, we construct a Markov chain with four states: $S$, $H$, $HH$, and $HHH$. The transition probabilities are determined based on the outcomes of the coin tosses (for eg - from $HH$ there is $0.5$ probability to go to $HHH$ and $0.5$ to go to $S$).\n Using the standard equations for the expected time to absorption, we find that the expected number of tosses to get $HHH$ is $14$, and the expected number of tosses to get $THH$ is $8$.\nNow for the main problem, we consider a game where both players can choose their own triplets. We construct a Markov chain with states representing ordered subsequences of either $HHH$ or $THH$. The states would be $\{S,H,T,HH,TH,HHH,THH\}$ and transition probabilities can be easily constructed too. We want to find the probability of reaching the absorbing state $HHH$ from the starting state $S$. Applying the equations for absorption probability, we find that the probability of ending up with the $HHH$ pattern is $\frac{1}{8}$.\n However there was an easier way to compute the result as well, we note that once a tail occurs, we will always get $THH$ before $HHH$. Therefore, if we don't start the coin flipping sequence with $HHH$, we will always have $THH$ before $HHH$. Hence the only way to get $HHH$ is in the first $3$ throws, and this happens with $\frac{1}{8}$ probability.

https://www.puzzledquant.com/problems/clhudg6vx000cmm08kkqcfuoe

Suppose you are playing a game where for every roll of dice and you get paid based on the number it shows . If the dice shows $4$, $5$, or $6$, you get to roll again and add the value to your overall payout. If the dice shows $1$, $2$, or $3$, the game ends and you can't roll again. What is the average amount of money you can expect to win from this game?\n For eg if the first throw is 2, you get paid 2 dollars but can't roll again

To find the average amount of money you can expect to win from this game, we can use the properties of geometric distribution. The stopping time $N$ follows a geometric distribution with $p=\frac{1}{2}$, where $p$ is the probability of stopping. Therefore, the expected stopping time is $E[N]=\frac{1}{p}=2$. For each roll, the expected face value is $E[X]=\frac{7}{2}$.\n To find the total expected payoff, we can use the Wald's equality since the game has clear stopping rules. $E[S_N]=E[X]E[N]$, where $E[S_N]$ is the total expected payoff, $E[X]$ is the expected face value, and $E[N]$ is the expected stopping time. Therefore, $E[S_N]=E[X]E[N]=\frac{7}{2} \times 2 = 7$. Hence, on average, you can expect to win 7 units of money from this game.\n Alternatively we can obtain the same result using Law of total Expectation..

https://www.puzzledquant.com/problems/clhudg5xt0008mm086ya3v0ks

Assume you are flipping a fair coin repeatedly. How many times on average do you need to flip it to get $5$ heads in a row?

To find out how many times on average you need to flip a fair coin to get $n$ heads in a row, we can use the concept of Markov chain and induction approach.\n Let $E$ $[f(n)]$ be the expected number of coin tosses to get $n$ heads in a row. Using the Markov chain approach, we divide the experiment into states , state $i$ defines we have seen $i$ heads in a row. We know state before $(n+1)$ heads in a row must be $n$ heads in a row. Conditioned on state $n$ heads in a row, there is a $\frac{1}{2}$ probability it will go to $(n+1)$ heads in a row (the new toss yields H) and the process stops. There is also a $\frac{1}{2}$ probability that it will go to the starting state 0 (the new toss yields T) and we need another expected $E[f(n+1)]$ tosses to reach $(n+1)$ heads in a row ( i.e. In addition to the existing $E[f(n)]$ steps to reach the state of $n$ heads). So we have\n $E[f(n+1)] = \frac{1}{2}(1+E[f(n)])+\frac{1}{2}(1 + E[f(n)] + E[f(n+1)])$.\n This simplifies to $E[f(n+1)] = 2 E[f(n)] + 2$. This recursion can be solved easily and yields $E[f(n)] = 2^{n+1}-2$. Therefore, on average, you need to flip a fair coin $2^{n+1} - 2$ times to get $5$ heads in a row.

https://www.puzzledquant.com/problems/clhudgbdf000umm088tmngvt4

There are $N$ distinct types of coupons in cereal boxes and each type, independent of prior selections, is equally likely to be in a box. If a child wants to collect a complete set of coupons with at least one of each type, how many coupons (boxes) on average are needed to make such a complete set?\n If the child has collected $n$ coupons, what is the expected number of distinct coupon types? Compute for $N=3$ and $n=3$

$\textbf{A}$) To get a complete set of $N$ different types of coupons, we can define $X_i$ as the number of additional coupons needed to obtain the $i^{th}$ type after $(i-1)$ distinct types have been collected. So, the total number of coupons needed is\n $X = X_1 + X_2 + ... + X_N$\n For any $i$, $(i-1)$ distinct types of coupons have already been collected. The probability of obtaining a new coupon of a different type is $1-\frac{i-1}{N}=\frac{N-i+1}{N}$. Thus, $X_i$ follows a geometric distribution with $p=\frac{N-i+1}{N}$ and $E[X_i]=\frac{N}{N-i+1}$. Therefore, the expected number of boxes needed to open to get at least one of each coupon is\n $E[X] = E[X_1] + E[X_2] + ... + E[X_N] = N(\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{N})$\n$\textbf{B}$) Let $Y$ be the number of distinct types of coupons in the set of $n$ coupons. We can define indicator random variables $I_i$, where $I_i=1$ if at least one coupon of the $i^{th}$ type is in the set of $n$ coupons, and $I_i=0$ otherwise. Then,\n $Y=I_1 + I_2 + ... + I_N$\n The probability that a collected coupon is not the $i^{th}$ coupon type is $\frac{N-1}{N}$. Thus, the probability that none of the $n$ coupons is the $i^{th}$ coupon type is $P(I_i=0) = (\frac{N-1}{N})^n$\n $E[I_i] = P(I_i=1) = 1 - \left(\frac{N-1}{N}\right)^n$.\n $E[Y] = E[I_1] + E[I_2] + ... + E[I_N] = N\left(1 - \left(\frac{N-1}{N}\right)^n\right)$

https://www.puzzledquant.com/problems/clhudg5eh0006mm08nijl1wq8

You can roll a $6$-side dice up to $3$ times. After the first or the second roll, if you get a number x, you can decide either to get $x$ dollars or to choose to continue rolling. But once you decide to continue, you forgo the number you just rolled. If you get to the third roll, you'll just get $x$ dollars if the third number is $x$ and the game stops. What is the game worth and what is your strategy?

The strategy for this game can be found using dynamic programming. We start with the final stage where we have forgone the first two rolls. At this stage, the game becomes a simple dice game with one roll, and the expected payoff is $\frac{7}{2}$.\n Going back one step, if we are at the point after the second roll, we choose to keep the face value if it is larger than $\frac{7}{2}$, i.e., when we get 4, 5, or 6, we stop rolling. When we get 1, 2, or 3, we keep rolling because the expected value in the next stage is more. So the expected payoff before the second roll is \n $E[X_2] = \frac{1}{6}(4+5+6) + \frac{3}{6}(\frac{7}{2})$ = $\frac{17}{4}$\nGoing back one step further, if we are at the point after the first roll, we choose to keep the face value if it is larger than $\frac{17}{4}$, i.e., when we get 5 or 6, we stop rolling. So the expected payoff before the first roll is\n $E[X_1]= \frac{1}{6}(5+6) + \frac{4}{6}(\frac{17}{4})=$ $\frac{14}{3}$\n Therefore, the expected value of the game at the initial stage is $\frac{14}{3}$

https://www.puzzledquant.com/problems/clhudgpm8002emm084cbtjj8j

Two gamblers are playing a coin toss game. Gambler $A$ has $(n +1)$ fair coins; $B$ has $n$ fair coins. What is the probability that $A$ will have more heads than $B$ if both flip all their coins?

A has an extra fair coin compared to B. For a moment forget the $A$'s last coin and Let's consider three possible outcomes:\n -$E_1:$ A's $n$ coins have more heads than B's $n$ coins\n - $E_2:$ A's $n$ coins have equal number of heads as B's $n$ coins\n - $E_3:$ A's $n$ coins have fewer heads than B's $n$ coins.\n By symmetry, the probability of $A$ having more heads is equal to the probability of $B$ having more heads $P(E_1) = P(E_3)$. Let's denote $P(E_1)$ as $x$ and the probability of A and B having equal number of heads $P(E_2)$ as $y$. Since the probability of one of these events happening is 1, we have $2x + y = 1$.\n For the event where $A$ has more heads than $B$ ($E_1$), A will always have more heads than B no matter what A's $(n+1)$th coin's side is. For the event where A and B have equal number of heads, A will have more heads than B if A's $(n+1)$th coin's is Heads : $P( E_2 $ and ${n+1}^{th}$ coin is Head) = $y*\frac{1}{2}$. For the event where A has fewer heads than B, A's $(n+1)$th coin doesn't make a difference. Therefore, the total probability that A has more heads is $x + 0.5y = x + 0.5(1 - 2x) = 0.5$

https://www.puzzledquant.com/problems/clhudgrvc002mmm08ix8b2yuy

Imagine you are presented with 5 bags, each containing 100 coins. The catch is that you do not know what type of coin is in each bag, as each bag may contain coins weighing either $9$ grams, $10$ grams, or $11$ grams. However, you do have access to a digital scale that can accurately measure the weight of the coins. How many times would you need to use the scale to determine the type of coin each bag contains?

To determine the type of coin in each of the 5 bags, we need to use the digital scale. We can start with the simplest version of the problem, which is 1 bag. We only need to weigh one coin to determine the type of coin. For 2 bags, we need to take 3 coins from bag 2 to determine the type of coins in both bags. We can represent the weight of the coins as $-1$, $0$, and $1$ (by removing the mean $10$). If we use 2 coins from bag 2, the final sum for 1 coin from bag 1 and 2 coins from bag 2 ranges from $-3$ to $3$, which is not enough to distinguish between the types of coins. However, if we use 3 coins from bag 2, the sum ranges from $-4$ to $4$, which is enough to cover all 9 possible combinations of coin types.\n Similarly, for 3 bags, we need to use an indicator ranging from $-13$ to $13$, which requires 9 coins from bag 3. We can repeat this logic to determine that we need 27 coins from bag 4 and 81 coins from bag 5.\n Therefore, we need to take $1$, $3$, $9$, $27$, and $81$ coins from bags $1$, $2$, $3$, $4$, and $5$, respectively, to determine the type of coins in each bag using a single weighing.

https://www.puzzledquant.com/problems/clwycuded0007n0fdj32x5nd5

A poker hand consists of five cards from a fair deck of 52 cards. What is the probability that you have a full house (three cards of the same value and another two cards of the same value)?

There are a total of $\binom{52}{5}$ total hand combinations. To count the number of hands that contain a full house, we can look at the triplet and pair separately. The triplet has 13 possible face values and $\binom{4}{3}$ possible suit values. The pair has 12 possible face values and $\binom{4}{2}$ possible suit values. Thus, the probability that you have a full house is: $\frac{13 \times \binom{4}{3} \times 12 \times \binom{4}{2}}{\binom{52}{5}} = \frac{6}{4165}$

https://www.puzzledquant.com/problems/clwycud3i0006n0fdwghcuh43

We place the integers 1 -- 9 (inclusive, no replacement) randomly on a $\( 3 \times 3 \)$ grid. What is the probability each row, column and diagonal add up to an odd number?

There is only one orientation where all the rows, columns, and diagonals add up to odd numbers. This orientation has the even numbers on the corners and the odds filling the rest of the positions. There are $\( 5! \)$ ways to order the odds and $\( 4! \)$ ways to order the evens with $\( 9! \)$ total orderings. Thus our answer is $\[ \frac{5! \cdot 4!}{9!} = \frac{1}{126} \]$

https://www.puzzledquant.com/problems/clwycucr40005n0fd1emtmwge

Suppose that $\ln(X) \sim N(0, 1)$. Find $\text{Var}(X^4)$. Your answer will be in the form of $e^a - e^b$ for positive integers $a$ and $b$. Find $a \neq b$.

Let $Z \sim N(0, 1)$. Then we know that $X = e^Z$, so $\text{Var}(X^4) = \mathbb{E}[X^8] - (\mathbb{E}[X^4])^2$ by the definition of variance. Plugging in $X = e^Z$, we get that $\text{Var}(X^4) = \mathbb{E}[e^{8Z}] - (\mathbb{E}[e^{4Z}])^2$. By definition, we know that for a random variable $X$, the MGF of $X$ is given by $M_X(\theta) = \mathbb{E}[e^{\theta X}]$ for all $\theta$ where the expectation is finite. Therefore, we see that $\text{Var}(X^3) = M_Z(8) - (M_Z(4))^2$ where $M_Z(\theta)$ is the MGF of a standard normal random variable. We know that the MGF of a standard normal is given by $M_Z(\theta) = e^{\frac{1}{2}\theta^2}$. Therefore, plugging in $\theta = 8$ and $\theta = 4$, we get that $\text{Var}(X^4) = e^{32} - e^{16}$, so our answer is $32 + 16 = 48$.

https://www.puzzledquant.com/problems/clwycuce40004n0fdd1q88dwp

Let $X_1, X_2, \dots$ be a sequence of IID random variables with some continuous PDF $f(x)$. Let $N$ be the time at which the sequence stops decreasing i.e. the first value $n$ such that $X_1 \geq X_2 \geq \dots \u003e X_{n-1} \u003c X_n$. Find $\ln(\mathbb{E}[N])$.

Recall for non-negative integer-valued random variables $X$ that $\mathbb{E}[X] = \sum_{k=1}^{\infty} \mathbb{P}[X \geq k]$. We should apply this to $N$. Therefore, $\mathbb{E}[N] = \sum_{k=1}^{\infty} \mathbb{P}[N \geq k]$. All that remains is to find $\mathbb{P}[N \geq k]$. The event $\{N \geq k\}$ means that $X_1 \geq X_2 \geq \dots \geq X_{k-1}$, which occurs with probability $\frac{1}{(k - 1)!}$ since each of the $X_i$ random variables are IID and have continuous distributions. Therefore, $\mathbb{E}[N] = \sum_{k=1}^{\infty} \frac{1}{(k - 1)!} = e$ by shifting the index back 1 and noting that this is the Taylor Expansion for $e^x$ evaluated at $x = 1$. We know $\ln(e) = 1$, so our answer is 1.

https://www.puzzledquant.com/problems/clwycuc0b0003n0fd4480scat

$$n$ points are selected randomly at uniform around a circle. What is the probability that all $n$ points are on the same semicircle for $n = 100$? The answer is in the form $\frac{a}{bc}$ for integers $a, b, c \u003e 0$ with $b$ minimal. Find $a + b + c$.

Suppose we already have the $n$ points selected on the circle. Choose one of those points, let's call it $A$. We draw a line through $A$ and $O$, the center of the circle; this diameter forms two semicircles. To prevent overcounting, we will only consider the semicircle that start from $A$ in the counterclockwise direction. Then, each of the $n - 1$ remaining points has a $\frac{1}{2}$ chance of being within that semicircle. Repeating this for all $n$ points, we find that the solution is simply $\frac{n}{2^{n-1}}$. Plugging in $n = 100$, we find our answer to be $100 + 2 + 99 = 201$.

https://www.puzzledquant.com/problems/clwyctcju0002n0fdiww2nv8a

A rabbit starts at the floor in front of a staircase of 10 stairs. The rabbit can hop up any amount of steps strictly larger than 1 at each movement. In particular, this means that the rabbit can't go up a one stair staircase. How many distinct paths are there from the floor to the top of the staircase (i.e. to the top of the 10th stair)?

Let $h_n$ be the number of distinct paths to the top of a $n$ stair staircase. We can condition on the size of the first jump. The size of the first jump can be anywhere from 2 to $n$, inclusive. If the rabbit hops $k$ stairs on the first step, it must make a unique path through the other $n - k$ stairs. Hence, you could view the problem now as stair $k$ being the floor and the top stair being $n - k$. This means that \begin{align*} h_n \u0026= h_{n-2} + h_{n-3} + h_{n-4} + \dots + h_1 + h_0 \end{align*} However, let's look at the tail term $h_{n-3} + h_{n-4} + \dots + h_1 + h_0$. This is equivalent to the problem where we start on stair 1 (instead of the ground) and need to jump up strictly more than one stair at each jump. This is because stair 3 would now be the first available stair to jump on, and the rabbit can jump to any other stair at least 3. Thus, the tail term there is just $h_{n-1}$, as starting on stair 1, the rabbit needs a path through the other $n - 1$ stairs to the top. Our recurrence relation is now \begin{align*} h_n \u0026= h_{n-1} + h_{n-2} \end{align*} Our initial conditions are that $h_1 = 0$ and $h_2 = 1$, which can just be counted directly. We note now that this is just the Fibonacci sequence shifted by 1 index up, as $F_0 = 0$ and $F_1 = 1$, so we can conclude that $h_n = F_{n-1}$. In particular, this means that $h_{10} = F_9 = 34$.

https://www.puzzledquant.com/problems/clm7banwb0000me08fhf8pqzp

Suppose you have an infinite stock of $\$$a bills and $\$$b bills such that $GCD(a,b)=1$. Find the largest amount of money (integer) that cannot be represented using $\$$a and $\$$b denominations. Compute for $a=5 \u0026 b=7$

Let the max number which cannot be represented using $a$ and $b$ denominations be $x$.Now, notice that we can denote the number $x+a = pa + yb$ , for some $p \u003e= 0$ $\u0026$ $y \u003e=0$\nSince $x$ can’t be represented as : (some positive number) * $a$ + (some positive number)*$b$ , $p = 0$ \n So,\n $x+a=yb$ , for some $y$ \n $x+b=za$ , for some $z$ \n This implies, $a(z+1) = b(y+1)$\n Since $a$ and $b$ are co-prime,\n $z=nb-1$ and $y=na-1$ , where $n$ is an integer \n This gives $x = nab-a-b$\n If $n\u003e1$, let $n=j+k$ , $j\u003e0$ and $k \u003e 0$ \n$x= jab+kab-a-b$ \n $x= a(jb-1) +b(ka-1)$, which cannot be true \n $\therefore$ $n = 1$ \u0026 $x= ab - a - b$

https://www.puzzledquant.com/problems/clhudgq65002gmm08on3xaoq4

Suppose that you are studying a standard normal random variable represented by $X \sim N(0, 1)$. You are curious about the expected value of $X$ given that $X$ is greater than $0$. Can you determine what $E[X | X \u003e0]$ ?

We are given a standard normal random variable $X \sim N(0,1)$ and we want to find the expected value of $X$ given that $X$ is greater than $0$, denoted as $E[X | X \u003e0]$. To solve this, we first need to find the probability density function of $X$,due to the conditional property p.d.f is twice the p.d.f of gaussian i.e. $f(x) = \frac{\sqrt{2}}{\sqrt{\pi}} e^{-\frac{x^2}{2}}$. \nUsing the definition of expected value, we have $E[X | X \u003e0] = \int_{0}^{\infty} x f(x) dx$ \nSubstituting $f(x)$ into the above equation, we get $E[X | X \u003e0] = \int_{0}^{\infty} x \frac{\sqrt{2}}{\sqrt{\pi}}e^{-x^2/2} dx$. \nWe can simplify this integral by using integration by substitution. Letting $u = -\frac{x^2}{2}$, we have $\frac{du}{dx} = -x$ and $dx = -\frac{du}{x}$. Substituting these into the integral, we get $E[X | X \u003e0] = \int_{0}^{- \infty} -\frac{\sqrt{2}}{\sqrt{\pi}} e^u du =\frac{\sqrt{2}}{\sqrt{\pi}} \left[ -e^u\right]_0^{- \infty} = \frac{\sqrt{2}}{\sqrt{\pi}}$ \nTherefore, the expected value of $X$ given that $X$ is greater than $0$ is $\frac{\sqrt{2}}{\sqrt{\pi}}$.

https://www.puzzledquant.com/problems/cllfxypa50000mg08eg6mwh6f

Anton rolls a fair die and records the value he rolls. Afterwards, he continues rolling the die until he obtains a value at least as large as the first roll. Let N be the number of rolls after the first he performs. Find E[N]. Note it is a 6 sided die.

This problem may seem daunting but its fairly easy as we partition the cases.\nIf Anton rolls 1, he gets a number greater than $1$ with a probability of $6/6$ (i.e. 1). \nNow this is a geometric distribution with the desired event coming with the probability $p$.The mean of the geometric distribution is also the expected value of the geometric distribution. The expected value of a random variable, X, can be defined as the weighted average of all values of X. The formula for the mean of a geometric distribution is given as follows: $E[X] = \frac{1}{ p}$\nLet $Y$ be the first roll outcomeSo $E[X | Y = 1] = 6/6 = 1$\nSimilarly\n$E[X | Y = 2] = \frac{6}{5}$and so on.\nFinally using the law of total expectation:\n$E [X]=\sum _{i}{\operatorname {E} (X\mid A_{i})\operatorname {P} (A_{i})}$\n$E[X] = \frac{1}{6} * (\frac{6}{6} + \frac{6}{5} + \frac{6}{4} + \frac{6}{3} + \frac{6}{2} + \frac{6}{1})$\n$E[X] = (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6)$\nE[X] = $\frac{147}{60}$

https://www.puzzledquant.com/problems/cliskuv4x0000mh08y18nxjyv

Given n points on a $2D$ plane, find the equation of the line with maximum number of collinear points. What is the time complexity of your algorithm?

This problem has a lot of possible solutions as it is open-ended. Here is our algorithm to solve this:\n The equation $ax+b = y$ defines a line.\n - Initialize a HashMap with key $(a,b)$ and an integer value\n - For each edge of two points, Compute $a,b$ and increment the integer value associated with $(a,b)$ in the HashMap -\u003e $O(n*n)$\n - Compute the maximum of the values in the HashMap and return the associated key -\u003e $O(n*n)$\nThis algorithm assumes the HashMap can update in $O(1)$ time. Similarly, we can use another data structure, like Binary Search tree updates in $O(\log n)$ time\nTotal time complexity $O(n*n)$

https://www.puzzledquant.com/problems/clik2e7970000la081r8z72su

You are given a chessboard with 8x8 dimensions. Your friend Tim asks you how many ways there are to place coins on the chessboard such that there are even number of coins in each row and in each column. Can you find it out?\nNote: You can place only one coin in each square box.

Let’s break this into smaller problems and try to solve those.\nThere are $2$ ways to fill a $2$x$2$ board, i.e., all boxes filled or empty. The sum of coins in each row is even, and the column is even ($ 0$ or $2$ ).\nTry to do this for $3$x$3$ board; you would have counted $16$ ways to fill the board.\nObserve that for a given $N$x$N$ board, if you consider the top left ($N-1$)x($N-1$) board, then no matter how you fill it. There is a way to fill the rightmost column and bottom row to make the sum of all rows and columns even. For that, count the sum of all rows of ($N-1$)x($N-1$) board, fill the rightmost column to make them even, and now do the same for all $N$ columns. For each placement on the ($N-1$)x($N-1$) board, there is just one unique way to fill the right column and last row.\nTherefore, the answer is the number of ways to fill the (N-1)x(N-1) board. Each cell has two choices; either place a coin or don’t. Hence the total number of ways = $2^{{(N-1)}^2}$\nNumber of ways to fill chessboard = $2^{49}$

https://www.puzzledquant.com/problems/clibop7qi0000l708w35l79x4

You are given a rooted tree with $n$ nodes. On each step, you randomly choose a node and remove the subtree rooted by that node and the node itself; until all of them have been removed (that is, the root has been chosen). Find the expected number of steps in this process. Compute for a complete binary tree with 7 nodes. \n A complete binary tree has with 7 nodes has one root node, 2 child node of the root, and then these two nodes have 2 child node each. Hence a total of 7 nodes.

Every node has an equal probability of being selected. We also know that to remove a particular node, one of its ancestors or the node itself must be chosen.\nSo the number of ancestors of one particular node $i$ = Depth $[i]$\nP($i$ is removed) = $\frac{\text{Depth}[i]}{ \text{Size of the tree}}$\nP($i$ is chosen) = $\frac{1}{\text{size of the tree}}$\nP($i$ is removed | $ i $ is chosen) = 1\nWe use the Bayes theorem: $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$\nHence P($i$ is chosen | $ i $ is removed) = $\frac{1}{\text{Depth}[i]}$\nWe now use Linearity of Expectation to find the expected number of subtree removals.\nDefine indicator variable $X_i =1$ if $i$ node was chosen; $0$ otherwise.\n$X = X_1 + X_2 … + X_n$\n$E[X] = \sum_{i=1}^n E[X_i]$\n$E[X] = \sum_{i=1}^n 1* P(X_i \text{ was chosen } | i \text{ was removed})$\n E[X] = $\sum_{i=1}^n$ $\frac{1}{\text{Depth[i]}}$

https://www.puzzledquant.com/problems/cli8rm5ed0000l508yljlsfeb

Is it possible to estimate the value of $\pi$ using a $n$ sided die?

A sequence of die rolls can generate a uniformly distributed random real number in $[0,1]$ to any desired degree of precision. (For example, consider the die rolls to be a sequence of base-6 digits, where a roll of 6 represents a 0 digit.)\nGenerate two such random numbers,$x$ and $y$, appending digits to each until there are enough digits in both numbers to establish with certainty whether $x^2+y^2\u003c1$ or $x^2+y^2\u003e1$ (Equality occurs with probability $0$ and can be disregarded.) If $x^2+y^2\u003c1$, increment $X_{in}$; otherwise increment $X_{out}$\n After generating a $m$ such throws, we have \n $ \pi \sim 4 \frac{X_{in}}{X_{in}+ X_{out}}$ \n The fundamental concept is same as use in Estimate pi problem. It uses monte carlo approach to find the value of Pi.

https://www.puzzledquant.com/problems/clhudh052000qmu08a6vxfees

You have $12$ identical balls. One of the balls is heavier or lighter than the rest (you don't know which). Using just a balance that can only show you which side of the tray is heavier, can you determine which ball is the defective one with $3$ measurements?

The problem is to identify a lighter or heavier ball from a set of $12$ indistinguishable balls using a balance just three times. We can separate the balls into three groups of four balls each and weigh two groups against each other. If they balance, the defective ball is in the third group. Let's say the third group has balls ${9,10,11,12}$ and we can weigh two balls from this group {$9,10$} against a normal ball and third ball of this group {$11,8$}. If the scales balance, the left out ball $12$ is defective and use the third trial to check if its lighter $L$ or heavier $H$.\n If they don't balance, and scales tilt toward {$9,10$} side then either $9$ or $10$ is $L$ or $11$ is $H$, weigh $9$ with $10$ - \n - If scale tilts towards $9$, $9$ is $L$\n - If they balance $11$ is $H$ \n - Otherwise $10$ is $L$.\n If originally the scales don't balance. Let's say the group {$1,2,3,4$} is $L$ then the {$5,6,7,8$}. In the second try, we weigh ${1,2,5}$ with ${3,6,9}$. \n - If $L$ weigh $1$ against $2$\n - If balanced, weigh $4$ with $8 $\n - Otherwise weigh $3$ with $9$.\n This covers all the possibilities of defective balls and all possible scenarios can be resolved in three measurements. This approach can be used to identify a defective ball among up to $3^3$ balls using no more than three measurements. If we have no information about whether the defective ball is lighter or heavier, we can identify the defective ball among up to $\frac{3^n-3}{2}$ balls using no more than m measurements.

https://www.puzzledquant.com/problems/clhudgwmw000cmu08mv3so2zy

Imagine yourself standing in a room with a blindfold on. You are informed that there are $1000$ coins scattered on the floor. Out of those coins, $980$ have tails facing upwards while the remaining $20$ have heads facing upwards. You are given a task to separate the coins into two piles. Can you ensure that both piles have an equal number of heads facing upwards? However, you are not allowed to touch or feel the coins to determine their sides, but you can flip over as many coins as you want.

We are given $1000$ coins, out of which $980$ have tails facing upwards and $20$ have heads facing upwards. We need to separate the coins into two piles such that both piles have an equal number of heads facing upwards. We cannot touch or feel the coins to determine their sides, but we can flip over as many coins as we want. \n Let's assume that we separate the coins into two piles with $n$ coins in one pile and $1000-n$ coins in the other. Let $m$ be the number of coins in the first pile with heads up, then there must be $20-m$ coins in the second pile with heads up. We also know that there are $n-m$ coins in the first pile with tails up. \nIf we flip all the coins in the first pile, all heads become tails and all tails become heads. As a result, it will have $n-m$ heads and $m$ tails (symmetry). So, to start, we need to make the number of tails in the original first pile equal to the number of heads in the second pile; in other words, to make $n-m=20-m$. \nTherefore, $n=20$ makes the equation hold. If we take $20$ coins at random and turn them all over, the number of heads among these turned-over $20$ coins should be the same as the number of heads among the other $980$ coins.

https://www.puzzledquant.com/problems/clhudgsto0000ml080qe0g5cx

If there are $6$ people at a party (including you), then either at least $3$ people met each other before the party, or at least $3$ people were strangers before the party. Is this true?

To answer this, we can use the generalized Pigeon Hole Principle. Among the remaining $5$ people, either at least $3$ people have met you or at least $3$ people have not met you. We can then explore two scenarios: \nCase 1: At least $3$ people have met you before. If two people in this group have met each other, then you and the pair of people have met each other. If no pair among these people have met each other, then these people did not meet each other. In either sub-case, the conclusion holds. \nCase 2: At least $3$ people have not met you before. If two people in this group have not met each other, then you and the pair of people have not met each other. If all pairs among these people have met each other, then these people have all met each other. Again, in either sub-case, the conclusion holds. \nTherefore, we can prove that either $3$ people have met before the party or at least $3$ people are strangers. The concept used here is the generalized Pigeon Hole Principle.

https://www.puzzledquant.com/problems/cljcmkkdk0000l308zs44utk3

How many points are there on the globe, so that if you walk $1$km South, then $1$km East and then $1$km North, you reach the place where you started?

The North Pole is a clear answer. If a person is at the North Pole and moves $1$ km South, then $1$ km East, and then $1$ km North, he will reach the North Pole again.\n Now consider latitudes on the globe. They have different circumferences ranging from max at the equator to $0$ at the poles. There will be one ring a little above the south pole with a circumference equal to $1$. So take any point on the latitude $1$ km north of that ring. If you start from any point and move $1$ km south, you will reach the latitude with circumference $1$; moving $1$ km east or west will get you to the same point. Now moving $1$ km north will take you to the original starting point. If you think hard enough you would be able to generalise it to various rings with circumference $1/n$ where $n$ is some integer. As you can easily circle around the latitude twice and come back to the starting point or circle around $3,4,5$ times as well.\nSome guys also argue for all the points $1$ km above the South Pole as East is not defined at the South Pole. So, you can’t move anywhere and moving $1$ km north will get you to the starting point but that’s just playing on the definition. You might mention this to show a little creativity.

https://www.puzzledquant.com/problems/https://www.puzzledquant.com/problems/clhros2ah000imv08oyrk7rnc

We rolled $n$ dice and kept the highest one. What is the probability that the highest value is 3 for $n=4$? \n Also ponder about the distribution of highest roll.

Suppose we roll n dice and keep the highest one. We want to find the distribution of values that we can get. \nLet's find the probability that the highest number rolled is k. Among the n dice rolled, all of them must show k or less. The probability of this occurring is given by:$(\frac{k}{6})^n$ However, if k \u003e 1, some of these rolls do not actually have any k's. That is, they are made up of only the numbers 1 through k-1. The probability of this occurring, for any k in {1, 2, ..., n}, is given by:$(k-1)^n - (k-2)^n$\nTherefore, the probability that the highest number rolled is k is given by:\n$P(maximum\ value\ rolled\ is\ k) = (\frac{k}{6})^n - ((\frac{k-1}{6})^n)$\nSo, for example, if 7 dice are rolled, the probability that the highest number to turn up will be 3 is:\n$P(maximum\ value\ rolled\ is\ 3) = (\frac{3}{6})^7 - (\frac{2}{6})^7 ≈ 0.007355$\nThis is the probability mass function for the distribution of the highest value rolled when n dice are rolled.

https://www.puzzledquant.com/problems/clhudg4hp0002mm08pm91hfft

A new card game is available at a casino. It uses a standard deck of $8$ cards, half of which are red and half are black. The dealer will draw cards one by one, without returning them to the deck. You have the power to stop the game at any point. Each time a red card is drawn, you win $1$ dollar, but if a black card is drawn, you lose $1$ dollar. To maximise your expected payoff, what is the best strategy for stopping the game?\n Also, how much would you be willing to pay to play this game?

To maximize the expected payoff, the player needs to decide when to stop the game. We can represent the number of black and red cards left in the deck as $(b, r)$. At each $(b, r)$, the player decides whether to stop or keep playing. If they stop, the payoff is $b-r$. As\n red cards drawn - black cards drawn = black cards left - red cards left = $b-r$\n If they keep playing, there is a probability of $(\frac{b}{b+r})$ that the next card will be black, in which case the state changes to $(b-1, r)$, and a probability of $(\frac{r}{b+r})$ that the next card will be red, in which case the state changes to $(b, r-1)$. The player should stop if the expected payoff of drawing more cards is less than $b-r$. We can use dynamic programming to recursively calculate the expected payoff for all pairs of $b$ and $r$.\n $E[f(b,r)] = max\left(b-r , \frac{b}{b+r}E[f(b-1,r)] + \frac{r}{b+r}E[f(b,r-1)]\right)$\nUsing this equation, we can use bottom up approach with boundary conditions $f(b,0) = b$ $ \forall b \in {1,2..26}$ and $f(0,r)=0$ $ \forall r \in {1,2..26}$. The expected payoff at the beginning of the game i.e $E[f(4,4)] =$ $\$1$.

https://www.puzzledquant.com/problems/clhros74b0012mv08pmddcy2z

Player A and Player B take turns rolling two standard dice, first player A, then player B. If Player A rolls a sum of $6$, A wins. If Player B rolls a sum of $7$, B wins. What is the probability that Player A will be the victor?

A wins if they roll a sum of $6$, while B wins if they roll a sum of $7$. The probability of A winning can be calculated as follows:\n Let $p$ be the probability of rolling a sum of $6$ with two dice ($p = \frac{5}{36}$).\n Let $r$ be the probability of rolling a sum of $7$ with two dice ($r = \frac{1}{6}$).\n A can win in a number of ways, including rolling a $6$ immediately, failing to roll a $6$ and B failing to roll a $7$, then A rolling a $6$, and so on. Each of these outcomes is independent and has a probability of $(1-p)^k*(1-r)^k*p$, where $k$ is the number of times that both players fail to win before A wins. We can add up these probabilities to find the total probability of A winning, which is given by the formula:$$\sum_{k=0}^{\infty} (1-p)^k*(1-r)^kp = \frac{p}{1-(1-p)(1-r)} = \frac{p}{p+r-pr}$$Substituting the values of $p$ and $r$, we get:$$\frac{p}{p+r-pr} = \frac{\frac{5}{36}}{\frac{5}{36} + \frac{1}{6} - \frac{5}{36}*\frac{1}{6}} = \frac{30}{61} = 0.4918032...$$Therefore, the probability of A winning is approximately $0.4918032$, which means that the game slightly favors player B.

https://www.puzzledquant.com/problems/clhros2s0000kmv08kjh6oqo8

Suppose we can roll a 6-sided die up to $n$ times. At any point we can stop, and that roll becomes our score. Our goal is to get the highest possible score, on average. Using the most optimal strategy, what is the max expected value of our score for $n=3$?

To find the optimal strategy, we can use dynamic programming to compute the expected value of our score with $n$ rolls left. Let $f(n)$ be the expected value of our score with $n$ rolls left. Then, we have the recursion:$$f(n) = \frac{1}{s} \left[ f(n-1) \cdot (s-1) + X \right]$$where $X$ is the maximum value we can roll on one die, which is $s$. If we have one roll left, our expected score is $\frac{s+1}{2}$. Using this recursion, we can compute $f(n)$ for each $n$ up to our maximum number of rolls.For a 6-sided die, we can summarize the optimal strategy as follows:If there are at least 5 rolls left, stop only on a roll of 6.If there are 4, 3, or 2 rolls left, stop on a roll of 5 or 6.If there is only 1 roll left, stop on a roll of 4, 5, or 6.The expected value of our score with this strategy is given in the table below:\n$1 \rightarrow 3.5 $\n$2 \rightarrow 4.25$\n$3 \rightarrow 4.666$\n$4 \rightarrow 4.944$\n$5 \rightarrow 5.1296$\n... \n$10 \rightarrow 5.6502 $\nTherefore, we can use this strategy to maximize our score on average when rolling a 6-sided die up to $n$ times. If we have a score greater than expected value of remaining throws then stop else keep playing till next move.\n If there are at least 5 rolls left, stick only on 6. If there are 4, 3, or 2 rolls left, stick on 5 or 6. If there is only 1 roll left, stick on 4, 5 or 6.

https://www.puzzledquant.com/problems/clwycvw2b000814duwsrol5gx

On average, how many cards do you need to flip over in a standard 52-card deck to obtain your last heart-suited card?

Similar to the First Ace problem, we can view each of the 13 cards with heart suit as dividers within our 52-card deck. These 13 cards divide our deck into 14 regions. In expectation, by symmetry, each of these regions should have an equal amount of cards in them. There are 39 cards that are not hearts, so we would expect $\( \frac{39}{14} \)$ cards on average for each region. Then, to get the expected position of the last heart, note that this is just the total length of the deck, 52, but remove one of our equally-sized regions from the rightmost/bottom part of the deck. This implies our expected position is $\( 52 - \frac{39}{14} = \frac{689}{14} \)$.

https://www.puzzledquant.com/problems/clgfh6kvf0000mn08rcm7ez2q

You are taking out candies one by one from a jar that has $10$ red candies, $20$ blue candies, and $30$ green candies in it. What is the probability that there are at least $1$ blue candy and $1$ green candy left in the jar when you have taken out all the red candies? (Candies of same color are indistinguishable!)

The probability that the last of sixty candies drawn is one of the thirty green candies is $\frac{30}{60}$. Ignoring the green candies, the probability that the last of the thirty other candies drawn is one of the twenty blue is $\frac{20}{30}$. Likewise the probability that the last draw would be blue and the last not blue draw would be green is $\frac{20}{60} \times \frac{30}{40}$.\n Thus the probability that you seek is clearly: $\frac{30}{60}\times\frac{20}{30}+\frac{20}{60}\times\frac{30}{40}=\frac{7}{12}$

https://www.puzzledquant.com/problems/clgfh6pfx000ula08f5frltpi

A postman brought $5$ letters to a house with two letter-boxes. Since the two boxes were empty, he puts 1 mail in each of the two mail boxes. Then he chooses one of boxes with probability proportional to number of letters present in that box, and puts the 3rd letter in it. He does this for all subsequent letters. What is the expected number of letters in the box with lower letters?

Suppose I have a stack of 2 black cards and one red card.\n Initially I put red between 2 black cards. Now I add black cards randomly between any two cards (so, initially it is either above or below red).\n Note that the probability that I add the card above the red card, when $x-1$ is the number of cards above red and $y-1$ is the number of cards below red is $\frac{x}{x+y}$.\n Let the problem be: if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. Now this way, we are getting all possible combinations in which one red and $n$ black cards can be mixed, we see that the probability that the red card is at height $h$ is independent of $h$. So, the probability that the smallest box contains $\frac{n}{2}$ letter or $1$ letter (or any number of letters between $1$ and $\frac{n}{2}$) are all same.\n. Since for this case the smallest box can contain either 1 or 2 letters with equal probability. The solution is 1.5

https://www.puzzledquant.com/problems/clgfh6pu1000wla0862oqb0jb

You have an opportunity to make one bid on an object, whose value to its owner is, as far as you know, uniformly random integer between 0 and 100. What you do know is that you are so much better at operating the widget than he is, that its value to you is 80% greater than its value to him. If you offer more than the widget is worth to the owner, he will sell it. But you get only one shot. How much should you bid?\n\n

We should bet only 0 which means not betting at all.\n Suppose I bet $x$ and get the widget. So, the value of it for the owner would be $y$, uniformly distributed between $0$ and $x$. So, it's value for me is 1.8$y$. Expected value for me :\n 1.8* E[$y$] = 1.8*$x$/2= 0.9$x$\nSo, if I get, expected value of the widget for me is 0.9$x$ paying $x$. If $x$ is less, i.e I am not getting it, I did not gain/lose anything. So, overall I am losing. So, I should not bid.

https://www.puzzledquant.com/problems/clgfh6q6o000yla08s8irroeo

On a given highway, trucks arrive at the station according to a Poisson process with $\lambda$ = 0.1/minute. This means that after a truck is just passed, the time for the next truck to arrive is an exponential random number with average arrival time of 10 minutes. Your car just broke on this highway, and you are waiting for the next truck for hitchhiking, what is your expected waiting time in minutes?

The given situation mimics a Poisson distribution.\n $\Pr(X{=}k)={\frac {\lambda ^{k}e^{-\lambda }}{k!}}$ \n A property of poisson distribution :\n${\lambda =\operatorname {E} (X)=\operatorname {Var} (X)}$\nUsing memoryless property of exponential distribution, the expected waiting time is 10 minutes. This also holds backwards, hence the expected time last truck passed is also 10 minutes. But this does not violate the total inter-arrival time of 10 minutes, because if your car breaks at a random time, you are more likely to be in long interval than a short one.

https://www.puzzledquant.com/problems/clgfh6qlo0010la08t7fawcp8

A very sharp, consistently skillful blind archer aimed for the center of a circular board and shot 2 arrows. He is expected to hit the aim, but doesn't hit it for sure. The archer is told that his first shot is better than second. He tried one more shot. What is the probability that this 3rd shot is the best shot among 3?\n(ie, Probability that 3rd arrow lands closer to center than his first two shots?)

Suppose $x_1$, $x_2$ and $x_3$ are the distances of the arrows from center. As the archer is consistent, we can use symmetry, i.e., there are six equally likely cases: $x_1$\u003c$x_2$\u003c$x_3$, (or 5 others, which are its permutations). Since archer is told that $x_1$\u003c$x_2$, we are left with following equally likely cases: $x_1$\u003c$x_2$\u003c$x_3$ , $x_2$\u003c$x_1$\u003c$x_3$ , $x_1$\u003c$x_3$\u003c$x_2$. Among these three, one is favorable.\n Hence The probability of last shot being best is 1/3.\n Notice that if there were (N-1) arrows, with first being better than rest, and then he shoots Nth arrow. The probability that Nth shot is best is $\frac{1}{N}$.

https://www.puzzledquant.com/problems/clgfh6hl3000cla08vd9dvj0e

Given the set of numbers from $1$ to $n$: { $1, 2, 3 .. n $} We draw $n$ numbers randomly (with uniform distribution) from this set (with replacement). What is the expected number of distinct values that we would draw? Answer for $n=4$

Notice that number of distinct points in the produced set is same as number of distinct points selected from the given set {$1..n$} . For that we denote indicator function $S_i$, that is, $S_i$ = $1$ if the integer $i$ is taken into produced set. Let $S$ denote the number of distinct points selected, $S = S_1+..+S_n$ \n$E[S] = E[S_1] +...+ E[S_n]$\n $E[S_i] = 1*P(S_i) = 1$ - (Probability that '$i$' is not chosen in any draw) \n= 1 - ( Prob that is $i$ is not chosen in one $1^{st}$ draw$)^n$ = $1 - ( 1 - \frac{1}{n} )^n$\nThus $E[S] = n ( 1 - ( \frac{n-1}{n})^n )$

https://www.puzzledquant.com/problems/clgfh6rxi0016la086vhgexrb

Given an array of $n$ numbers. Finding minimum takes $n-1$ comparisons. Finding maximum takes $n-1$ comparisons. If you had to simultaneously find both minimum and maximum, what is the minimum number of comparisons you may require for $n=20$?

Solution requires approximately 1.5n comparisons instead of 2n comparisons.\nBreak n numbers into pairs of 2.So, that is n/2 pairs.Find maximum and minimum in each pair. Cost = n/2.\nNow given n/2 maximums, find the maximum. Cost = n/2. Given n/2 minimums, find the minimum. Cost = n/2 \nSo, overall cost 3n/2 comparisons. As you draw the comparisons, you will notice that there are two repetitions, hence the final result is 28

https://www.puzzledquant.com/problems/clgfh6tiw001ela089amj9nj9

A rectangular table has 100 coins with unit radius, placed on it such that none of the coins overlap, and it is impossible to place any more coins on the table without causing an overlap. Using this specific configuration, does there exist a special configuration of 400 coins which covers the table with overlaps?\n Covering means for every point on table there is a coin above it.

Consider just one of these coins, with center P. It follows that the center Q of any other coin cannot lie within the coin of radius 2 with center P because it must be at least 2 units away. Thus, we construct all of these coins of radius 2, concurrent with each of the coins of radius 1. If the set of coins of radius 2 did not cover the rectangle entirely, then we could place a coin of radius 1 in this region, contradiction. Thus, the set of coins of radius 2 entirely covers the rectangle.\n\nWe now have 100 coins of radius 2 that entirely covers the rectangle. Scale this by a factor of 1/2 in both planar dimensions. Now we have 100 coins of radius 1 that entirely covers a rectangle that is a quadrant of the original rectangle. By placing four of these sets together, we get 400 coins of radius 1 that entirely covers the original rectangle.

https://www.puzzledquant.com/problems/clgfh6tx3001gla08rwfqzz9g

On a table you have a square made of 4 coins at the corner at distance 1. So, the square is of size 1×1. In a valid move, you can choose any two coin let’s call them mirror and jumper. Now, you move the jumper in a new position which is its mirror image with respect to mirror. That is, imagine that mirror is a centre of a circle and the jumper is on the periphery. You move the jumper to a diagonally opposite point on that circle. With any number of valid moves, can you form a square of size 2×2?

No, it is not possible to form a square of size 2x2 using any number of valid moves. The reason is that no matter how we move the coins around, we can never create two pairs of adjacent coins that are at a distance of 2 from each other, which is a necessary condition for forming a 2x2 square.

https://www.puzzledquant.com/problems/clgfh6v32001mla08xanqp8bs

What is/are the next term(s) in the sequence:\na) 1, 11, 21, 1211, 111221, ?\nb) 10, 11, 12, 13, 14, 20, 22, 101, ? \nc) (This is a sequence made by only 2 \u0026 1): 2,2,1,1,2,1,2,2,1, ? ....\n Type in the answer separated by commas for the 3 sequences

a) 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, …This is a Look-and-say sequence! To generate a member of the sequence from the previous member, read off the digits of the previous member, counting the number of digits in groups of the same digit.\nb) 10, 11, 12, 13, 14, 20, 22, 101, 1010, 1111111111. This is '10' written in different bases, from 10 to 1 \nc) This a sequence made by only 2 \u0026 1: 2,2,1,1,2,1,2,2,1, 2, 2....This is a version of Kolakoski sequence, and is its own run-length encoding. Each symbol occurs in a "run" of either 1 or 2 consecutive terms, and writing down the lengths of these runs gives exactly the same sequence. It is the unique sequence with this property except for the same sequence with extra '1' at start.