Math Applications

Question 1

[4 Prob] Connecting noodles

Given 100 noodles, pick two ends randomly and connect, repeat until no ends exist. What’s the expected number of loops?

What’s the probability of forming 1 loop?

Answer 1

Given n noodles, we want to know L[n].

There are (2n)C2 = 2n(2n-1)/2 = n(2n-1) ways to choose 2 ends:

n of which will form loop of length 1, in addition L[n-1]

n(2n-1)-n of which only lengthens one of the noodles, thus reduces to L[n-1]

L[i] = n/(n(2n-1)) (1+L[i-1]) + (1-n/(n(2n-1))) L[i-1] = 1/(2n-1) + L[i-1]

Now L[1] = 1, thus L[i] = 1 + 1/3 + .. + 1/(2i-1)

P[n noodles, 1 loop] = (1 - 1/(2n-1)) P[n-1 noodles, 1 loop] = (1-1/3).. (1-1/(2n-1))

Question 2

[4 Prob] Coupon collection

Each box comes with 1 of N types of coupons:

1. How many boxes expected to collect all N types?
2. Given k boxes, what’s the expected number of distinct types?

Answer 2

1. 1 box to get 1st type + N/(N-1) boxes to get 2nd type + .. + N/1 boxes to get last type = Σ_i=1..N N/(N-i+1) boxes to get N types
2. ((N-1)/N)^k probability that no boxes have nth type, 1<=n<=N –> 1 - ((N-1)/N)^k probability that at least one box has nth type –> N(1 - ((N-1)/N)^k) expected number of types

Question 3

[2 Brainteasers] Infinite sequence

f(x) = x^x^x^x… = 2, what’s x?

Answer 3

x^f(x) = x^2 = x –> x = sqrt(2)

Question 4

[4 Prob] cubic of integer

If 1 <= x <= 10¹², x integer. What’s the probability that the cubic of x ends with 11?

Answer 4

By binomial theorem, x³ = (a+10b)³ = a³ + 30a²b + 300ab² + 1000b³. So we require a = 1 and 3b = _1 –> a = 1, b = _7 –> x = _71 –> 1% probability

Question 5

[2 Brainteasers] Rainbow hat

Hat colors: 7. Prisoners: 7. They can see but not hear each other. How to ensure at least 1 correctly guesses own hat color?

Answer 5

Since Σ_i=0..6 x_i must be in {0, 1, 2, 3, 4, 5, 6},

guess_k = y_k s.t. (y_k + Σ_i=k x_i) mod 7 = k

Question 6

[4 Prob] 100th digit

What’s the 100th digit after the decimal of (1+sqrt(2))³⁰⁰⁰?

Answer 6

By binomial theorem and matching terms, (1+sqrt(2))³⁰⁰⁰ + (1-sqrt(2))³⁰⁰⁰ is an integer. Since 0 3000 << 10^-100, the 100th digit of (1+sqrt(2))³⁰⁰⁰ is 9.

Question 7

[4 Prob] E[max] E[min] of RVs

Yn = min(X1,..,Xn)

Zn = max(X1,..,Xn)

if X ~ Unif(0,1): E[Yn] = ? E[Zn] = ?

Answer 7

P(Yn >= x) = P(Xi >= x)ⁿ –> 1 - F_Y(x) = (1 - F_X(x))ⁿ –> f_Y(x) = n f_X(x) (1 - F_X(x))^n-1

P(Zn <= x) = P(Xi <= x)ⁿ –> F_Z(x) = F_X(x)ⁿ –> f_Y(x) = n f_X(x) F_X(x)^n-1

if X ~ Unif(0,1): F_X(x) = x, f_X(x) = 1

f_Y(x) = n(1-x)^n-1 –> integrate_x=0..1 xf_Y(x) dx = 1/(n+1)

f_Z(x) = nx^n-1 –> integrate_x=0..1 xf_Z(x) dx = n/(n+1)

Question 8

[2 Brainteasers] Counterfeit coins II

A coins weighs 0g, 1g, or 2g. Given 5 bags, 100 coins each (same type within each bag). How many weighings (digital scale) to determine weight by bag?

Answer 8

One weighing: 3ⁱ coins from each bag, i=0..4

Express total weight in base 3: w₄w₃w₂w₁w₀

Question 9

[4 Prob] Dice order

Roll 3 dice one by one, what’s the probability that they end up in strictly ascending order?

Answer 9

probability to get 3 distinct numbers 6*5*4/6³ x probability that they are in ascending order 1/3! = 5/54

Question 10

[3-1 Calc] ** what’s E[X|X>0] for X~N(0,1)?

Answer 10

integration by substitution: 1/sqrt(2π)

Question 11

[5 Stochastics] Drunk man

On a line 0 to N, you start at i. Every subsequent period, P(i++) = P(i–) = 0.5. What’s the probability that you get to N before 0? How many steps does it take to reach either N or 0?

Answer 11

let x₊ = N-i, x_- = i

Martingale:

E[Sn] = p₊x₊ - (1-p₊)x_- = S0 = 0

E[Sn² - n] = E[p₊x₊² + (1-p₊)x_-²] - E[n] = S0² - 0 = 0

–> p₊ = x_{<span>-</span>}/(x₊+x_{<span>-</span>}), E[n] = x₊x_{<span>-</span>}

Can also use Markov Chain with 2 absorbing states, or treat it as a special case of gambler’s ruin with p = 0.5

Question 12

[3-2 LinAl] correlations

corr(x,y) = corr(y,z) = 0.8 –> corr(x,z) in what range?

Answer 12

1. Geometry (n=3): max=1, min=cos(cos^-1(0.5) + cos^-1(0.5)) = -0.5
2. Cauchy-Schwartz (n=3): bc + sqrt((1-b^2)(1-c^2)) >= a >= bc - sqrt((1-b^2)(1-c^2))
3. Pos semi def (any n): det(C) >= 0 or all eigvalues >= 0

Question 13

[2 Brainteasers] Door to offer

Two doors: offer and no offer. Two guards: truth teller and liar. How to ask one guard one question to get offer?

Answer 13

“Would the other guard say that you are guarding the door to the offer?”

No: open that door

Yes: open other door

Question 14

[4 Prob] Russian roulette series

Gun has 6 chambers

1. 1 bullet, spin once then take turns, better 1st or 2nd?
2. 1 bullet, spin every time, better 1st or 2nd?
3. 2 bullets random, 1st empty chamber, better re-spin or not on 2nd?
4. 2 bullets adjacent, 1st empty chamber, better re-spin or not on 2nd?

Answer 14

1. doesn’t matter; outcome has been fixed since the spin
2. 2nd; 1st gets hit with probability p = 1/6 + 5/6 (1-p) = 6/11
3. re-spin; get hit with probability p = 2/6 if re-spin else 2/5
4. not re-spin; get hit with probability p = 1/4 if not re-spin else 2/6

Question 15

[2 Brainteasers] Trailing zeros

How many trailing zeros are in 100!

Answer 15

24

Question 16

[5 Stochastics] Coin triplets

1. What’s the expected number of tosses to get HHH? THH?
2. What’s the probability that you get HHH before THH?
3. Given triplet abc, find triplet xyz such that xyz is most likely before abc?

Answer 16

1. By Markov Chain, HHH 14, THH 8
2. By Markov Chain, P(HHH before THH) = 1/8 (can only have HHH if start with HHH)
3. xyz = _ab

Question 17

[4 Prob] Dice game

You roll a dice and get its face value each time. If you roll 1,2,3 game ends, 4,5,6 you can continue to roll. What’s the EV?

Answer 17

EV = 1/2(2) + 1/2(5+EV) –> EV = 7

E[Sn] = E[X]E[n] = 7/2 * 1/(3/6) = 7 (Wald’s Equality)

Question 18

[3-1 Calc] integrate_x=0..inf e^{-x^2/2} dx

Answer 18

recall Normal pdf: integrate_x=-inf..inf 1/sqrt(2π) e^{-x^2/2} dx = 1

–> integrate_x=0..inf 1/sqrt(2π) e^{-x^2/2} dx = 1/2

–> integrate_x=0..inf e^{-x^2/2} dx = 1/2 * sqrt(2π) = sqrt(π/2)

Question 19

[5 Stochastics] World series

Teams A and B are playing best 4 out of 7. How to bet on each individual game such that the overall bet that A wins is +100/-100?

Answer 19

f[i,j] = payoff that A has i losses and j wins, 0<= i,j <=4

boundary conditions: f[i,4] = 100, f[4,j] = -100, 0<= i,j <=4

DP:

f[i+1,j] = f[i,j] + bet[i,j]; f[i,j+1] = f[i,j] - bet[i,j]

–> f[i,j] = 1/2(f[i+1,j] + f[i,j+1]); bet[i,j] = 1/2(f[i+1,j] - f[i,j+1])

Question 20

[4 Prob] Basketball scores

Player will shoot 100 times, 1=score, 0=miss.

Let S[i] = 1/0 on ith shoot and T[i] = Σ_j=1..i S[j].

S[1] = 1 and S[2] = 0. P(S[i+1]==1) = T[i] / i, 2<=i<100.

What’s P(T[100]=50)?

Answer 20

P(T[3]=1) = P(T[3]=2) = 1/2

P(T[4]=1) = P(T[4]=2) = P(T[4]=3) = 1/3

guess: P(T[n]=k) = 1/(n-1), 1<=k

induction:

P(T[n+1]=k)

= P(S[n+1]=0|T[n]=k) P(T[n]=k) + P(S[n+1]=1|T[n]=k-1) P(T[n]=k-1)

= (1-k/n) 1/(n-1) + (k-1)/n 1/(n-1) = 1/n

Question 21

[5 Stochastics] Ticket line

A random walk X[t]: X[0] = X[2T] = 0; dX[t] = +/-1 for 0= 0 for all 0<=t<=2T?

Answer 21

Total number of paths: (2T)CT

Total number of paths that reach X[t] = -1 = total number of paths where X[0] = 0 and X[2T] = -2, by reflection principle: (2T)C(T-1)

1 - (2T)C(T-1)/(2T)CT = 1 - n/(n+1) = 1/(n+1)

Question 22

[2 Brainteasers] Prisoner problem

Hat colors: 3. Prisoners: 100. They line up and can only look in front. How to maximize number of prisoners that correctly guess own hat color?

Answer 22

E[num correct] = 99.33

R, G, B = 0, 1, 2

100th: guess₁₀₀ = Σ_i=1..99 i mod 3
kth: guessk = (guess_k+1 - Σ_i=1..k-1 i) mod 3

Question 23

[3-1 Calc] e^pi vs pi^e

Which is larger, e^π vs π^e?

Answer 23

e^x > 1 + x –> e^π/e-1 > 1 + π/e-1 –> e^π/e/e > π/e –> e^π > π^e

Question 24

[4 Prob] Gambler’s ruin

On a line 0 to N, you start at i. Every subsequent period, P(i++) = p, P(i–) = q = 1-p. What’s the probability that you get to N before 0?

Answer 24

Markov Chain transition matrix:

p[0,0] = p[N,N] = 1

p[i,i-1] = q and p[i,i+1] = p for 0

absorption probabilities:

x[N] = 1, x[0] = 0

x[i] = qx[i-1] + px[i+1] for 0

P[i] = i/N if p = q = 0.5, else (1-q/p)/(1-(q/p)^N) (1-(q/p)ⁱ)/(1-(q/p)^N)

Question 25

[4 Prob] Joint default prob A ~ Bernoulli(0.5), B ~ Bernoulli(0.3). What's the range of P(A or B)? What's the range of Corr(A,B)?

Answer 25

P(A or B) = [no overlap, all overlap] = [0.5, 0.8] E[A] = 0.5, Var(A) = 0.25 E[B] = 0.3, Var(B) = 0.21 max Cov(A,B) = 0.3(1-0.5)(1-0.3) + 0.2(1-0.5)(0-0.3) + 0.5(0-0.5)(0-0.3) = 0.15 min Cov(A,B) = 0.5(1-0.5)(0-0.3)+0.2(0-0.5)(0-0.3)+0.3(0-0.5)(1-0.3) = -0.15 -\> Corr(A,B) = Cov(A,B) / sqrt(Var(A)Var(B)) = within [-sqrt(3/7), sqrt(3/7)]

Question 26

[4 Prob] Poker hands In a 5-card hand, what's the probability of: * four-of-a-kind (quadruplet + single)? * full house (triplet+pair)? * two pairs?

Answer 26

* four-of-a-kind (quadruplet + single)? 13 \* 48 = 624 * full house (triplet+pair)? (13 \* 4C3) \* (12 \* 4C2) = 3744 * two pairs? 13C2 \* 4C2 \* 4C2 \* 44 = 123552

Question 27

[4 Prob] Candies in a jar Jar has 10R 20B 30G candies. Remove one at a time, what's the probability that when all R are removed, there is \>=1 B and \>=1 G in the jar?

Answer 27

p(#60=R) = 1/6 p(#59=R, #60=B or G) = 1/6(2/6+3/6) p(#58=R, #59-60=all B or all G) = 1/6((2/6)² + (3/6)²) p(#40=R, #41-60=all B or all G) = 1/6((2/6)²⁰ + (3/6)²⁰) p(#30=R, #31-60=all G) = 1/6((3/6)³⁰) -- sum: 1/6( 1 + (1/3)¹ + ... + (1/3)²⁰ + (1/2)¹ + ... + (1/2)³⁰) = 1/6(1+1/2+1) = 5/12 --\> 1 - 5/12 = 7/12

Question 28

[5 Stochastics] Color balls N balls of N different colors in box. Each time you pick two and set color[2nd] = color[1st]. What's the expected time until all balls are the same color?

Answer 28

(N-1)²

Question 29

[2 Brainteasers] Coin split problem f(n) = f(n-x) + f(x) + x(n-x) f(1) = 0, f(2) = 1, f(3) = 3 f(N) = ?

Answer 29

by induction: f(n) = f(n-x) + f(x) + x(n-x) --\> f(N) = N(N-1)/2

Question 30

[4 Prob] Correlation of max and min Let X1, X2 ~ Unif(0,1), and Y = min(X1,X2), Z = max(X1, X2). What's P(Y\>=y | Z\<=z) for y,z within [0,1]? What's Corr(Y,Z)?

Answer 30

Visually from coordinates with X1, X2 as dimensions, P(Y\>=y | Z\<=z) = (z-y)² / z² if 0\<=y\<=z\<=1, else 0 from previous question, f_Y(x) = n(1-x)^n-1, f_Z(x) = nx^n-1, E[Y] = 1/3, E[Z] = 2/3 E[Y²] = integrate_x=0..1 x²f_Y(x) dx = 1/6 E[Z²] = integrate_x=0..1 x²f_Z(x) dx = 1/2 E[XY] = integrate_z=0..1 integrate_y=0..z 2yz dydz \<= F(y,z) = 2zy-y²; f(y,z) = dF/dydz = 2 = integrate_x1=0..1 integrate_x2=0..1 x1x2 dx1dx2 \<= yz = x1x2 = 1/4 Corr(Y,Z) = (E[YZ] - E[Y]E[Z]) / sqrt((E[Y²]-E[Y]²)(E[Z²]-E[Z]²)) = 1/2

Question 31

[4 Prob] Coin toss game A and B take turns tossing a coin. Whoever that ends with HT wins. What's P(A wins?)

Answer 31

xT, xH = current person wins with the previous flip being T, H xT = 1/2 (1-xT) + 1/2 (1-xH) xH = 1/2 (1) + 1/2 (1-xH) --\> xT, xH = 4/9, 2/3 --\> P(A wins) = xT = 4/9

Question 32

[2 Brainteasers] Last ball Given 20/14 blue/red balls. Each time you remove 2: if same color, add 1 blue back, else, add 1 red back. What's the color of the last ball? What if given 20/13 blue/red balls?

Answer 32

(B,R) = (B-1, R) or (B+1, R-2) or (B-1, R) R never increases and sometimes decreases by 2, so its parity never changes. Thus for R even, last ball is B, else, last ball is R.

Question 33

[4 Prob] N points on a circle N points are placed randomly on the circumference of a circle. What's the probability that they are all within a semicircle?

Answer 33

Each point is a potential starting point (clockwise) of the semicircle. For each starting point, 1/2^N-1 probability that remaining points are in that semicircle. --\> N/2^N-1

Question 34

[3-1 Calc] intersecting cylinders Two cylinders each with radius r intersect at right angles and their centers overlap. What's the volume of the intersection?

Answer 34

Volume of inscribed sphere: 4/3 π r³ Area of each circular slice = π/4 Area of each square slice Volume of intersection: 4/3 π r³ / (π/4) = 16/3 r³

Question 35

[4 Prob] Aces Distribute 52 cards to 4 people. What's the probability that they each get an Ace?

Answer 35

Using counting: 4! \* MultiNomial(48,12,12,12,12) / MultiNomial(52,13,13,13,13) = (4! 48!/12!12!12!12!) / (52!/13!13!13!13!) = 1 39/51 26/50 13/49 Alternatively, using conditional probability: P(A1 in any pile) \* P(A2 in remaining 3 piles) \*P(A3 in remaining 2 piles) \*P(A4 in last pile) = 1 39/51 26/50 13/49

Question 36

[3-1 Calc] prove that (1+x)ⁿ \> 1+nx for all x \> -1 and integers n \>= 2

Answer 36

guess: n = 2 --\> (1+x)² \> 1+2x induction: n \> 2: (1+x)ⁿ⁺¹ = (1+x)ⁿ + x(1+x) \> 1 + (n+1)x = 1+nx+x

Question 37

[4 Prob] Screwy pirates 2 There are 11 pirates and one shared chestbox. Place locks and allocate keys such that the chestbox can be opened iff \>= 6 pirates present. How many locks in total and how many keys per pirate?

Answer 37

Every unique group of 5 pirates requires a lock that they can't open: 11C5 = 462 locks total. Every lock has 6 keys, given to a unique group of 6 pirates: 462\*6/11 = 252 keys per pirate.

Question 38

[5 Stochastics] Dynamic dice game Roll a dice, if i \<= 5, get face value and can repeat; if i=6, lose all profits. What's the EV of this game?

Answer 38

1/6(1+2+3+4+5-V[n]) = 15/6-V[n]/6 \> 0 --\> reroll if V[n] \< 15 For 15\<=v\<=19: EV[v] = v For 0\<=v\<= 14: EV[v] = 1/6 (Σ_i=1..5 E[v+i] + 0) EV[0] = 6.15

Question 39

[4 Prob] Amoeba population Start with one amoeba, after every minute every amoeba has 1/4 probability of dying, no change, doubling, or tripling. What's the probability that the amoeba population dies out?

Answer 39

p = 1/4(1+p+p²+p³) --\> p = sqrt(2)-1

Question 40

[2 Brainteasers] Division by 9 a_i = ith digit of A from the right, indexed by 0, i.e. A = Σ_i=0..n10ⁱa_i Prove that if Σ_i=0..na_i mod 9 = 0 then A mod 9 = 0

Answer 40

S = Σ_i=0..na_i D = A - S = Σ_i=1..n(10ⁱ-1)a_i --\> D mod 9 = 0 --\> if S mod 9 = 0 then A mod 9 = 0 (same logic for mod 11)

Question 41

[5 Stochastics] Dynamic card game A random walk X[t]: X[0] = X[52] = 0; dX[t] = +/-1. You can stop the process at any time s and take X[s] as profit. What's the EV of this game?

Answer 41

x_-, x₊ = left steps remaining, right steps remaining f[x_-, x₊] = EV of game with (x_-, x₊) remaining boundary conditions: f[x_-,0] = x_-, f[0,x₊] = 0 DP: E[f[x_-, x₊]] = max(x_- - x₊, x_-/(x_- + x₊)E[f[x_--1, x₊]] + x₊/(x_- + x₊)E[f[x_-, x₊-1]]) E[f[26,26]] = 2.62

Question 42

[5 Stochastics] Coin sequence What's the expected number of flips to get n Hs?

Answer 42

Markov Chain: E[1] = 2, E[2] = 6, E[3] = 14 --\> induction guess E[n] = 2ⁿ⁺¹ - 2 --\> E[n+1] = E[n] + 1/2(1) + 1/2(1+E[n+1]) --\> E[n+1] = 2E[n] + 2 = 2ⁿ⁺² - 2 Margingale: E[(xi-i)] = xi - E[i] = 0; xi = Σ_i=1..n 2ⁿ = 2ⁿ⁺¹ - 2 --\> E[i] = 2ⁿ⁺¹ - 2 For the general pattern(n): xi = Σ_i=1..n 2ⁿI(pattern.shift(n-i) == pattern[-(n-i):])

Question 43

[4 Prob] Application letters Given 5 pairs of letters-envelopes, randomly matched. What's the probability that all letters are mismatched?

Answer 43

c(n) = count of no match in n pairs of letter-envelope c(0) = 1 c(1) = 0 c(2) = 2! - [2C1 c(1) + 2C2 c(0)] = 1 c(3) = 3! - Σ_i=1..3 [3Ci c(3-i)] = 2 c(4) = 4! - Σ_i=1..4 [4Ci c(4-i)] = 9 c(5) = 5! - Σ_i=1..5 [5Ci c(5-i)] = 44 --\> 1 - 44 / 5! = 11/30

Question 44

[2 Brainteasers] Box packing Can you pack 53 bricks of 1x1x4 into a cube of 6x6x6?

Answer 44

No. Divided cube of 6x6x6 into 27 cubes of 2x2x2 --\> 13 white and 14 black. Each pair holds 4 1x1x4 bricks, so 13x4 = 52 \< 53 bricks.

Question 45

[2 Brainteasers] Defective ball Given a balance and 12 balls, 1 is lighter OR heavier than the rest. How to find the ball within 3 weighings?

Answer 45

n weighings --\> (3ⁿ - 3) / 2 balls try with 9 balls / 2 weightings first see book for full derivation

Question 46

[2 Brainteasers] Chocolate bar Given chocolate bar of nxm, what's minimum number of breaks to get nm pieces?

Answer 46

Since each break increases count by 1, we need nm-1 breaks

Question 47

[2 Brainteasers] Have we met before Show that among 6 people, either \>=3 people all connected, or \>=3 people none connected

Answer 47

(\>= 3 people all connect i.e. exist triangle) U (\<= 2 people all connect i.e. no triangle) = 1 (\<= 2 people all connect) --\> at most 6 edges --\> at least 6C2 - 6 = 9 non-edges --\> 9 non-edges in 6 nodes must form a triangle --\> (\>= 3 people none connect)

Question 48

[2 Brainteasers] Chameleon colors Given 45 chameleons: 13R 15G 17B. When two different colors meet they become the third color. Can all become one color?

Answer 48

Let x: -R-G+2B, y: -R-B+2G, z: -G-B+2R [13-x-y+2z, 15-x+2y-z, 17+2x-y-z] = [0,0,45] or [0,45,0] or [45,0,0] will find non-integer solutions --\> not possible see book for other solutions

Question 49

[3-1 Calc] Solve x² = 37

Answer 49

f(x) = x² - 37 = 0 Newton's method: x0 = 6 --\> x1 = 6 - (36-37)/2\*6 = 6 1/12 f(x) = sqrt(x) Taylor series: f(37) ~ f(36) + f'(36)(37-36) = 6 1/12