*Posted by Albert in : potd , *
Determine the last three non-zero digits ofÂ $(20!)^{2000}$

show

**Solution:**
Consider the factorization of $20! = 2^{18} \cdot 3^8 \cdot 5^4 \cdot 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19$.

We don’t want any zeros, so cancel every pair of $2$ and $5$: Let $S = 2^{14} \cdot 3^8 \cdot 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19$.

Since we want to find $(20!)^{2000} \pmod{1000}$, we may employ Euler’s Totient Function on each prime factor of $S$ that is relatively prime to $1000$. For some number $a$ relatively prime to $1000$, $a^{\phi(1000)} \equiv 1 \pmod{1000}$. $a^{400} \equiv a^{2000} \equiv 1 \pmod{1000}$. This means $S^{2000} \equiv (2^{14})^{2000} \pmod{1000}$.

Now we consider the periodicity of $2^n$ in $1000$. By the Chinese Remainder Theorem, we can consider $2^n \pmod{125}$ and $2^n \pmod{8}$ separately for some integer n. Since for all $n \geq 3$, $2^n \equiv 0 \pmod{8}$, we only need to consider the periodicity of $2^n$ in $125$. To do this, we notice we want to find the first $n > 0$ for which $2^n \equiv 1 \pmod{125}$. Since $2$ is relatively prime to $125$, we can employ Euler’s Totient Function again: $2^{\phi(125)} \equiv 1 \pmod{125}$. $\phi(125) = 125(1-\frac{1}{5}) = 100$. This means the periodicity of $2^n$ in $125$ is the periodicity of $2^n$ in $1000$ is $100$.

This means $2^n \equiv 2^{n+100} \pmod{125}$, for $n \geq 0$, which means $(2^{14})^{2000} \equiv 2^0 \equiv 1 \pmod{125}$. Using the Chinese Remainder Theorem on $1 \pmod{125}$ and $0 \pmod{8}$, we find the solution is $376 \pmod{1000}$.

Thus, the answer is $\fbox{376}$.

*Posted by Alex in : potd , *
A circle with center $C$ passes through point $B$. Let $A$ be a point outside of the circle and $Q$ be the intersection of the circle and $\overline{AB}$. If $\angle ACB$ is a right angle and $\overline{AB}$, $\overline{AC}$, $\overline{BC}$, and $\overline{BQ}$ have integer lengths, find the minimum possible perimeter of $\triangle CBQ$.

show

**Solution:**
Let $a$ be the length of $\overline{BC}$, $b$ be the length of $\overline{AC}$, $c$ be the length of $\overline{AB}$, and $x$ be the length of $\overline{BQ}$. Because $\triangle ABC$ is a right triangle, $a^2 + b^2 = c^2$. By the power of a point theorem, $(b – a)(b + a) = c(c – x)$. By substituting the first equation into the second and simplifying, one obtains: $x = \frac{2a^2}{c}$. Because $a$, $b$, $c$, and $x$ are all integers, $2a^2$ is an integer multiple of $c$. Considering Pythagorean triples that are multiples of $(3, 4, 5)$ leads to $(15, 20, 25)$, where the $b$ and $c$ would share the common factor of $5$ and $c$ is a perfect square. By letting $a = 15, b = 20, c = 25$, $x$ has the value of $18$. The perimeter of $\triangle CBQ$ is $a + a + x = \fbox{048}$. By considering other Pythagorean triples, there is no way to obtain a smaller perimeter.

*Posted by Sreenath in : potd , *
Seungln is standing two feet away from a spider. He takes a one-foot step once a second, either forwards (toward the spider) with $\frac57$ probability or backwards with $\frac27$ probability. Compute the expected value of the time it takes Seungln to reach the spider.

show

**Solution:**
Solution: The expected value of his movement per second is $$\frac{5}{7} \text{ feet} – \frac{2}{7} \text{ feet} \Rightarrow \frac{3}{7} \text{ feet forward}$$ $$\frac{2 \text{ feet}}{\frac{3}{7}\frac{\text{ feet }}{\text{second}}} = \boxed{\frac{14}{3} \text{ seconds}}$$

*Posted by Saketh in : bonus , *
On a 5×5 board, two players, Albert and Billy, alternately mark numbers on empty cells. The first player, Albert, always marks 1′s, the second, Billy, 0′s. One number is marked per turn, until the board is filled. For each of the nine 3 x 3 squares the sum of the nine numbers on its cells is computed. How large can the Albert force the maximum of these sums to be regardless of Billy’s behavior?

*Posted by Saketh in : potd , *
Albert is flipping his lucky coin, keeping track of the cumulative number of heads and tails. If the probability that he reaches $15$ heads before he reaches $14$ tails is $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers, find the remainder when $m+n$ is divided by $1000$.

show

**Solution:**
After the coin is flipped $28$ times, either $15$ heads will have occurred or $14$ tails will have occurred, but not both. The probability that $k$ heads occurred after these flips is $$\frac{\binom{28}{k}}{2^{28}}$$ The probability $a$ that at least $15$ heads have occurred is $$a= b – \frac{\binom{28}{14}}{2^{28}}$$ where $b$ is the probability that at least $14$ heads have occurred. $b$ is also equal to the probability that at least $14$ tails have occurred (by symmetry), which is $1 – a$. Solving the resulting system of equations, we find $$a= \frac{2^{25} – 3^3 \cdot 5^2 \cdot 17 \cdot 19 \cdot 23}{2^{26}} = \frac{\cdots 857}{ \cdots 864}$$ Then, the sum of the numerator and denominator of $a \pmod{1000}$ is $\fbox{721}$.