01/04/2021
Aaron and Brooke are playing a game where a fair coin is being flipped repeatedly. If 4 heads in a row are ever flipped, the game ends and Aaron wins. If 3 tails in a row are ever flipped, the game ends and Brooke wins. What is the probability that Aaron wins?
Solution:
This problem is a more general format of Penney’s Game, with different lengths of sequences that two players choose. John Horton Conway’s algorithm can be used for this type of problems, with sequences of dissimilar length.
Here is a general description of Conway’s algorithm:
(1) Given two sequences $A$ and $B$, the leading numbers give us a way of working out the odds of sequence $B$.
(2) Here is the process to calculate the leading number with $A$ as the upper sequence and $B$ as the lower sequence:
(2.1) Put two sequences with upper sequence on top of lower sequence
(2.2) Compare two sequences, put 1 above the first digit of the upper sequence of equal, 0 otherwise
(2.3) Remove the leading digit from the upper sequence and shift it to the left. Then repeat step (II) to get next digit, and so on.
(3) Write $AA$ for the binary format of leading number we get using sequence $A$ as the upper and lower sequence. $AB$ for the binary format of leading number we get using sequence $A$ has the upper sequence and sequence $B$ as the lower sequence, and so on.
The odds of sequence $B$ winning are given by the equation $\dfrac{AA-AB}{BB-BA}$.
Apply Conway’s algorithm to this problem:
$A=HHHH, B=TTT$
The binary leading number of $AA$ is 1111, the binary leading number of $AB$ is 0000, the binary leading number of $BB$ is 111, and the binary leading number of $BA$ is 000.
So the odds of $B$ winning is given by $\dfrac{1111-0000}{111-000}=\dfrac{15}{7}$
This means the probability that Aaron wins is $\dfrac{7}{15+7}=\bbox[1px, border: 1px solid black]{\dfrac{7}{22}}$.
References:
-
Reading about Conway’s Algorithm
-
Coin Tossing on Wolfram MathWorld and reference
-
Winning Ways for Your Mathematical Plays, Vol. 1: Adding Games
-
Time Travel and Other Mathematical Bewilderments P. 64-66 tells some results but did not give reason.
-
-
-
Related problem:
A has 6 points and B has 4 points. They flip a coin and if it’s a head, then A gets a point. If it’s a tail, then B gets a point. What’s the probability that A wins with 10 points?
-
From Unequal Chance to a Coin Game Dance: Variants of Penney’s Game
-
Pattern Matching Probabilities and Paradoxes as a new Variation on Penney’s Coin Game
-
Humble-Nishiyama Randomness Game - A New Variation on Penney’s Coin Game
01/06/2021
An ant starts at the point $(1, 0)$. Each minute, it walks from its current position to one of the four adjacent lattice points until it reaches a point $(x, y)$ with $|x| + |y| \ge 2$. What is the probability that the ant ends at the point $(1, 1)?$ HMMT 2010 General Test Problem 4
Solutions:
-
From $(1, 0)$ there are $\dfrac{1}{4}$ of probability that the ant goes to point $(1, 1)$, $\dfrac{1}{4}$ of probability that the ant goes to point $(2, 0)$ and $\dfrac{1}{4}$ of probability that the ant goes to point $(-1, 0)$ such that the ant will not return back, and $\dfrac{1}{4}$ of probability that the ant goes to point $(0, 0)$, which we let it to be $p$. So the asked probability is $\dfrac{1}{4} + \dfrac{1}{4}p$.
-
Now we calculate the probability of the ant from $(0, 0)$ to point $(1, 1)$. There are eight border points at which the ant will stop, and they are divided into two groups: $(2, 0), (0, 2), (-2, 0), (0, -2)$ (they have the same probability to be reached by the ant starting from $(0, 0)$, and let this probability to be $p_1$), and $(1, 1), (-1, 1), (1, -1), (-1, -1)$ (they have the same probability to be reached by the ant starting from $(0, 0)$, and let this probability to be $p_2$). Easy to see that the ant has only one path of distance 2 to get to the points in the first group, while it has two paths of distance 2 to get to the points in the second group. That means $p_2=2p_1$. And we know the sum of probabilities of all the points in both group is $1$, so $4p_1+4p_2=1, p_2=2p_1 \implies p_2=\dfrac{1}{6}, p_1=\dfrac{1}{12}$.
-
So the asked probability is $\dfrac{1}{4}(\dfrac{1}{6}+1)=\bbox[1px, border: 1px solid black]{\dfrac{7}{24}}$.
01/15/2021
Let $x_1, x_2, x_3, x_4$ be positive reals such that $(x_1+x_3)(x_2+x_4)=1$. Prove $\dfrac{x_1^3}{x_2+x_3+x_4} + \dfrac{x_2^3}{x_1+x_3+x_4} + \dfrac{x_3^3}{x_1+x_2+x_4} + \dfrac{x_4^3}{x_1+x_2+x_3} \ge \dfrac{1}{3}.$
Solution:
$(x_1+x_3)(x_2+x_4)=1 \implies x_1^2+x_2^2+x_3^2+x_4^2 \ge \dfrac{1}{2}[(x_1+x_3)^2+(x_2+x_4)^2] \ge 1$
$\displaystyle\sum_{cyc}{\dfrac{x_1^3}{x_2+x_3+x_4}} = \sum_{cyc}{\dfrac{x_1^4}{x_1x_2+x_1x_3+x_1x_4}} \ge \dfrac{(x_1^2+x_2^2+x_3^2+x_4^2)^2}{2\sum_{i>j}{x_ix_j}} = \dfrac{(x_1^2+x_2^2+x_3^2+x_4^2)^2}{2(x_1x_3+x_2x_4)+2(x_1+x_3)(x_2+x_4)}$
since $2(x_1x_3+x_2x_4) \le x_1^2+x_2^2+x_3^2+x_4^2$
$\implies \displaystyle\sum_{cyc}{\dfrac{x_1^3}{x_2+x_3+x_4}} \ge \dfrac{(x_1^2+x_2^2+x_3^2+x_4^2)^2}{3(x_1^2+x_2^2+x_3^2+x_4^2)} \ge \dfrac{1}{3} \blacksquare$
01/17/2021
Adam, Bob and Charlie, each of them is given a unique number from 1,2,3,4,5,6,7,8,9. Everyone knows his number only. And they all know that Charlie’s number equals to the average of Adam’s and Bob’s numbers. Now they start to talk to guess others numbers.
Adam: I guess Charlie’s number is 7.
Bob: Charlie’s number cannot be 7. I guess Charlie’s number is 6.
Charlie: I know Bob is still guessing. I have known all our numbers, and I know Adam has known the numbers too.
If they are all smart and honest, what are their numbers?
Solution:
We use $A, B, C$ to represent Adam, Bob and Charlie’s numbers.
From Adam’s statement, we know that he thinks $A + B = 14$, so $A$ cannot be $1, 2, 3, 4$, and $A \ne 7$. Thus $A$ could be $5, 6, 8, 9$.
From Bob’s statement, since he thinks $A + B = 12$, and $A$ could be $5, 6, 8, 9$, $B$ could be $3, 4, 6, 7$, but he guesses $C=6$, so $B$ could be $3, 4, 7$.
Now we make all possible combinations that $A + B$ must be an even number:
| A | B | C |
|---|---|---|
| 5 | 3 | 4 |
| 5 | 7 | 6 |
| 6 | 4 | 5 |
| 8 | 4 | 6 |
| 9 | 3 | 6 |
| 9 | 7 | 8 |
These are the information that all three persons know. Then from Charlie’s statement, since he knows all the numbers, $C$ must be a unique number is all situations, so $C \ne 6$. And similarly, $A$ is also a unique number in all situations, so $A$ must be 6 or 8. $A$ cannot be 8 since it will make $C = 6$. So the answer is $\bbox[1px, border: 1px solid black]{A=6, B=4, C=5}$. To verify Charlie’s statement, before he said he and Adam have known the answer, Bob was still guessing. He was right, Bob has number 4 and it appears in two situations, so Bob was still guessing before Charlie finished his statement.
01/18/2021
Solution:
Easy to see that
$AB=FG, CD=2AB, EF=3AB \implies EF=4AB$
$\implies S_{\triangle{EFK}}=\dfrac{3}{4}S_{\triangle{EKG}}=\dfrac{9}{2}$
$\implies S_{\triangle{ABM}}=\dfrac{1}{9}S_{\triangle{ABM}}=\dfrac{1}{2}$
$\implies S_{\triangle{CDN}}=4S_{\triangle{ABM}}=2$
$\implies S_{\triangle{ABM}} + S_{\triangle{CDN}} + S_{\triangle{EFK}} = \dfrac{1}{2} + 2 + \dfrac{9}{2} = \bbox[1px, border: 1px solid black]{7}$
01/18/2021
Let $S_{n,k}=\displaystyle\sum_{a=0}^{n}{ {a \choose k}{n-a \choose k} }$. Find the remainder when $\displaystyle\sum_{n=0}^{200}{\sum_{k=0}^{200}{S_{n,k}}}$ is divided by 1000.
Solution:
01/24/2021
Point $I$ is the incenter of $\triangle{ABC}$. $DE \perp AI$. $DE$ and $AB$ intersect at $D$. $DE$ and $AC$ intersect at $E$. $FG$ is a tangent line of $\odot{I}$. $FG$ and $AB$ intersect at $F$. $FG$ and $AC$ intersect at $G$. Prove: $BD \cdot CE = DF \cdot EG.$
Prove 1:
Suppose the Tangent points of $\odot{I}$ with $AB, BC, CA$ are $M, K, N$ and easy to know the segment lengths as noted in above figure.
In $\triangle{ABC}$ we know the radius of inner circle is
$r_{in}=\sqrt{\dfrac{(s_{ABC}-AB)(s_{ABC}-BC)(s_{ABC}-CA)}{s_{ABC}}}$ where $s_{ABC}=\dfrac{AB+BC+CA}{2}$
Here we have $s_{ABC}=\dfrac{a+b+c+d+c+d+c+e+e+c+g+a+b-g}{2}=a+b+2c+d+e$
so $r_{in}=\sqrt{\dfrac{(c+e)(a+b)(c+d)}{a+b+2c+d+e}}$
Since $\triangle{ADI}$ and $\triangle{AMI}$ are both right angle triangles, we know $r_{in}^2=MI^2=(a+b)c$
In $\triangle{AFG}$ we know the radius of external circle $\odot{A}$ is
$r_{ex_A}=\sqrt{\dfrac{s_{AFG}(s_{AFG}-AF)(s_{AFG}-AG)}{s_{AFG}-FG}}$ where $s_{AFG}=\dfrac{AF+FG+GA}{2}$
Here we have $s_{AFG}=\dfrac{a+b+g+a+b-g}{2}=a+b$
so $r_{ex_A}=\sqrt{\dfrac{(a+b)bg}{a-g}}$, and we know $r_{ex_A}=r_{in} \implies r_{ex_A}^2=MI^2=(a+b)c$
$\implies \dfrac{(a+b)bg}{a-g}=(a+b)c \implies a=\dfrac{b+c}{c}g$
$r_{ex_A}=r_{in} \implies \dfrac{(c+e)(a+b)(c+d)}{a+b+2c+d+e}=\dfrac{(a+b)bg}{a-g}$
$\implies \dfrac{(c+e)(c+d)}{\dfrac{b+c}{c}g+b+2c+d+e}=\dfrac{bg}{\dfrac{b+c}{c}g-g}=c$
$\implies (c+e)(c+d)=(b+c)g+bc+2c^2+cd+ce$
$\implies de=(b+c)(c+g) \implies BD \cdot CE=DF \cdot EG \blacksquare$
Prove 2:
$\angle{BAI}=\angle{IAC}=\dfrac{A}{2}, \angle{ABI}=\dfrac{B}{2}, AI \perp DE \implies DI=EI$
$ \implies \angle{ADI} = \angle{AEI} = 90^{\circ}-\dfrac{A}{2}$
$\implies \angle{DIB} = \angle{ADI} - \angle{ABI} = 90^{\circ}-\dfrac{A}{2}-\dfrac{B}{2}=\dfrac{C}{2}, \angle{EIC}=\dfrac{B}{2}$
$\implies \triangle{BDI}\sim\triangle{IEC} \implies \dfrac{BD}{DI}=\dfrac{EI}{CE} \implies BD \cdot CE=DI^2$
Let $\angle{AFG}=\beta \implies \angle{DFI}=\angle{GFI}=\dfrac{180^{\circ}-\beta}{2}=90^{\circ}-\dfrac{\beta}{2}$
Let $\angle{AGF}=\gamma \implies \angle{EGI}=90^{\circ}-\dfrac{\gamma}{2}$
So $A+\beta+\gamma = 180^{\circ}$
So $\angle{DIF}=180^{\circ}-(90^{\circ}-\dfrac{A}{2})-(90^{\circ}-\dfrac{\beta}{2})=90^{\circ}-\dfrac{\gamma}{2}$
and $\angle{GIE}=90^{\circ}-\dfrac{\beta}{2}$
So $\triangle{FDI}\sim \triangle{GEI} \implies \dfrac{DF}{DI}=\dfrac{EI}{EG} \implies DF \cdot EG=DI^2$
So we know $BD \cdot CE=DF \cdot EG \blacksquare$
01/25/2021
Inscribed quadrilateral $ABCD$ of $\odot{O}$ has $AB=AD$. Now extend $CD$ to $F$, extend $CB$ to $E$ so that $DF=EF+BE$. Prove $\angle{BAD} = 2\angle{EAF}.$
Prove:
Make $G$ on $DF$ so that $GD=EB$
$DF=EF+EB=EF+GD \implies EF=FG$
Easy to see that $\angle{EBA}=\angle{GDA}, AB=AD \implies \triangle{EBA} \cong \triangle{GDA}$
$\implies EA=GA, \angle{EAB}=\angle{GAD} \implies \triangle{FEA} \cong \triangle{FGA} \implies \angle{EAF}=\angle{FAG}$
$\implies \angle{BAD}=\angle{BAF}+\angle{FAG}+\angle{GAD}=\angle{EAF}-\angle{EAB}+\angle{FAD}+\angle{EAB}$
$\implies \angle{BAD}=2\angle{EAF}\blacksquare$
01/30/2021
Acute $\triangle{ABC}$, point $D$ is on side $AC$ so that $AD=BC$, $CF$ bisects $\angle{ACB}$. Point $E$ on side $AB$ so that $DE \parallel CF$ and $AE=CD$. Prove: $\angle{ADB}=3\angle{BAC}$
Prove:
Let $AD=BC=m^2$, $CD=AE=mn$, easy to know that $EF=n^2$.
$EF$ bisects $\angle{ACB} \implies \dfrac{AC}{AF}=\dfrac{BC}{BF} \implies BF=mn$.
Let $DE=x, CG=p, GF=q$
In $\triangle{AED}$ we have $\dfrac{mn}{sin\beta}=\dfrac{x}{sin\alpha}$, $cos\beta = \dfrac{x^2+m^4-m^2n^2}{2m^2x}$
In $\triangle{ABC}$ we have $\dfrac{m^2}{sin\alpha}=\dfrac{2mn+n^2}{sin2\beta}$
$\implies \dfrac{x}{m^2}=\dfrac{mnsin2\beta}{(2mn+n^2)sin\beta} \implies \dfrac{x}{m^2}=\dfrac{2mcos\beta}{2m+n} \implies cos\beta=\dfrac{(2m+n)x}{2m^3}$
$\implies \dfrac{(2m+n)x}{2m^3}=\dfrac{x^2+m^4-m^2n^2}{2m^2x} \implies (2m+n)x^2=mx^2+m^3(m^2-n^2)$
$\implies x^2=m^3(m-n) \implies x=m\sqrt{m(m-n)}$
East to see $\dfrac{x}{p+q}=\dfrac{m^2}{m^2+mn} \implies p+q=(m+n)\sqrt{m(m-n)}$
And $\dfrac{q}{x}=\dfrac{mn}{mn+n^2} \implies q=\dfrac{mx}{m+n}=\dfrac{m^2\sqrt{m(m-n)}}{m+n}$
$\implies p=\dfrac{n(2m+n)\sqrt{m(m-n)}}{m+n}$
So in $\triangle{AED}$ we have $cos\alpha=\dfrac{m^2n^2+m^4-m^3(m-n)}{2m^3n}=\dfrac{m+n}{2m} \implies cos2\alpha=2cos^2\alpha-1= \dfrac{m^2+2mn+n^2-2m^2}{2m^2}=\dfrac{n^2+2mn-m^2}{2m^2}$
In $\triangle{ABC}$ we have $cos\angle{ABC}=\dfrac{(2mn+n^2)^2+m^4-(m^2+mn)^2}{2m^2(2mn+n^2)}=\dfrac{n^3+3m^2n+4mn^2-2m^3}{2m^2(2m+n)}=\dfrac{(2m+n)(n^2+2mn-m^2)}{2m^2(2m+n)}=\dfrac{n^2+2mn-m^2}{2m^2}=cos2\alpha$
so we know $\angle{ABC}=2\angle\alpha=2\angle{BAC}$
That’s as far as this problem can get. When $\angle{\alpha} = \angle{\beta}, AB=AC$, the target statement is correct, otherwise it is not correct. Any counter example with $\angle{BAC} \ne 36^{\circ}$ can satisfy the known facts:
Discussion of this problem can be seen here.