Math Contest | mathgarage

Posts Tagged ‘Math Contest’

Find the Hundreds Digit of 2011^2011

Posted: October 20, 2022 in Mathematics
Tags: AMC, math, Math Contest, number theory, solution

This is problem 23 of AMC 10B in 2011. So, here is the problem:

$\text{Find the hundreds digit of } 2011^{2011}$

I will present three solution here. The first one uses Chinese Remainder Theorem, which is the slowest, takes about 5 to 10 minutes. The second solution I will just use Euler Phi function, which is quicker, about 3 minutes. And the third solution I will use the trick of using Binomial Theorem, which is super fast, takes about 10 seconds.

SLOWEST method:

By Chinese Remainder Theorem, we have

$\displaystyle N = a_1 b_1 M_1 + a_2 b_2 M_2 \pmod{M} \qquad \text{where } M_1 = \frac{M}{M_2} \text{ and } M_2=\frac{M}{M_1}$

We have $N = 11^{2011}, M = 1000, M_1 = 8, \text{ and } M_2 = 125$ .

We need to find $a_1, b_1, a_2, b_2$

$2011^{2011} \equiv 11^{2011} \pmod{1000}$

Since $(11, 8)=1 \text{ and } \phi(8) = 8\cdot\dfrac{1}{2} = 4$ , then

$11^{2011} \equiv 11^3 \equiv 27 \equiv 3 \pmod{8}$

So, $a_1 = 3$

To find $b_1$ ,

$125b_1 \equiv 1 \pmod{8}$

$5b_1 \equiv 1$

$b_1 \equiv 5$

Next, we will find $a_2$ ,

Since $(11,125)=1 \text{ and } \phi(125) = 125\cdot \dfrac{4}{5} = 100$ , then

$11^{2011} \equiv 11^{11} \pmod{125}$

$11^2 \equiv 121 \equiv -4$

$11^4 \equiv 16$

$11^8 \equiv 256 \equiv 6$

$11^3 \equiv -44$

$\Rightarrow 11^{11} \equiv 6 \cdot (-44) \equiv -264 \equiv 111$

So, $a_2 = 111$

Next, we are going to find $b_2$

$8b_2 \equiv 1 \pmod{125}$

$8b_2 = 125k + 1$

$0 \equiv 5k+1 \mod{8}$

$5k \equiv 7 \mod{8}$

$k \equiv 35 \equiv 3 \mod{8}$

$\therefore b_2 = \dfrac{125\cdot3+1}{8} = 47$

Hence,

$2011^{2011} \equiv 11^{2011} \equiv 3 \cdot 5 \cdot 125 + 111 \cdot 47 \cdot 8 \equiv 875 + 736 \equiv 611 \pmod{1000}$

Therefore, the hundreds digit is 6.

STANDARD Number theory method:

Note that (11, 2011) = 1, hence

$\displaystyle 11^{\phi(1000)} \equiv 1 \pmod{1000} \qquad \text{where } \phi(n) = \prod_{p \mid n} \frac{p-1}{p}$

Now,

$\phi(1000) = 1000\cdot\dfrac{1}{2}\cdot\dfrac{4}{5} = 400$

then,

$2011^{2011} \equiv 11^{2011} \equiv 11^{400\cdot5+11} \equiv 11^{11} \pmod{1000}$

$11^2 \equiv 121$

$11^3 \equiv 121(1+10) \equiv 121 + 210 \equiv 331$

$11^4 \equiv 331 + 310 \equiv 641$

$11^5 \equiv 641 + 410 \equiv 51$

$11^{10} \equiv 51^2 \equiv (50+1)^2 \equiv 500 + 100 + 1 \equiv 601$

$11^{11} \equiv 601 + 10 \equiv 611$

Therefore the hundreds digit is 6.

SUPER FAST Method:

By Binomial Theorem,

$2011^{2011} = (1 + 2010)^{2011} = 1+2011\cdot 2010 + \binom{2011}{2} 2010^2 + \binom{2011}{3} 2010^3 + \cdots$

$\equiv 1+ 11\cdot10 + \dfrac{2011\cdot2010}{2}\cdot 10^2 \pmod{1000}$

$\equiv 1 + 110 + 11 \cdot 5 \cdot 100 \equiv 611$

Therefore the hundreds digit is 6.

A Little AIME Problem

Posted: May 16, 2022 in Mathematics
Tags: AIME, math, Math Contest

Solution

In general, let

$\displaystyle \sec x + \tan x = \alpha$

By Pythagoras Identity,

$\displaystyle \sin^2 x + \cos^2 x = 1, \quad \tan^2 x + 1 = \sec^2 x$

$\therefore \sec^2 x - \tan^2 x = 1$

$\displaystyle \therefore \sec x - \tan x = \frac{1}{\sec x + \tan x} = \frac{1}{\alpha}$

Solve this system by adding and subtracting, we get

$\displaystyle \sec x = \frac{1}{2}\left(\alpha+\frac{1}{\alpha}\right)$

$\displaystyle \tan x = \frac{1}{2}\left(\alpha-\frac{1}{\alpha}\right)$

Hence,

$\displaystyle \cos x = \frac{2}{\alpha+1/\alpha}$

and

$\displaystyle \sin x = \frac{1}{2}\left(\alpha-\frac{1}{\alpha}\right)\cos x = \frac{\alpha-1/\alpha}{\alpha+1/\alpha}$

Therefore,

$\displaystyle \csc x + \cot x = \frac{1}{\sin x} + \frac{\cos x}{\sin x}$

$\displaystyle = \frac{\alpha + 1/\alpha}{\alpha - 1/\alpha} + \frac{2}{\alpha-a/\alpha} = \frac{\alpha+1/\alpha+2}{\alpha-1/\alpha}$

$\displaystyle = \frac{\alpha^2+1+2\alpha}{\alpha^2-1} = \frac{(\alpha+1)^2}{(\alpha-1)(\alpha+1)} = \frac{\alpha+1}{\alpha-1}$

Let $\alpha = \frac{22}{7}$ , then

$\displaystyle \csc x + \cot x = \frac{22/7+1}{22/7-1} = \frac{22+7}{22-7} = \frac{29}{15}$

Stand With Ukraine

Posted: May 5, 2022 in Mathematics
Tags: math, Math Contest, MathOlympiad, StandWithUkraine

The way of solving this problem is to recognize that this is a math olympiad type problem and it probably has an elegant solution. This equation is nice. There is a symmetry in the coefficients and this is a nice hint for us to crack this problem. My idea is coming from squaring the number 111.

But 1, 2, 3, 2, 1 is not exactly 1, 7, 14, 7, 1. However I know I am getting there. If I play around with the numbers a bit, it is not difficult to get the following.

So, here it is. The hard part is solved! The rest is trivial.

$x^4 - 7x^3 + 14x^2 - 7x + 1 = x^4 - 4x^3 + x^2$

$\text{.}\qquad\qquad\qquad\qquad\qquad\qquad\quad -3x^3 + 12x^2 - 3x$

$\text{.}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad + x^2 - 4x + 1 = 0$

$x^2(x^2-4x+1) - 3x(x^2-4x+1) + (x^2-4x+1) = 0$

$(x^2-4x+1)(x^2-3x+1)=0$

$\therefore x=2\pm\sqrt3 \text{ or } \dfrac{3\pm\sqrt5}{2}$

A Simple Little Math Contest Problem

Posted: May 2, 2022 in Mathematics
Tags: math, Math Contest, Mathematics, number theory

So, here is the problem I found on the internet.

$\displaystyle \text{Find all natural numbers } a \text{, } b \text{, and } c \text{ such that } a>b>c \text{ and } \frac1a + \frac2b + \frac3c = 1$

Solution

Let’s find some bounds on a, b, and c. Since $\frac1a+\frac2b+\frac3c=1$ , hence

$a>1, b>2, \text{ and } c>3$

Since a > b > c, then

$\displaystyle \frac1a + \frac2a + \frac3a < \frac1a + \frac2b + \frac3c = 1$

$\therefore a > 6$

This doesn’t seem to help us much. Let’s consider c,

$\displaystyle \frac1c + \frac2c + \frac3c > \frac1a + \frac2b + \frac3c = 1$

$\therefore 3 < c < 6$

So, this is great! We only have 2 cases to consider.

Case c = 4,

$\displaystyle \frac1a + \frac2b + \frac{3}{4} = 1 \Rightarrow \frac1a + \frac2b = \frac{1}{4}$

$4b + 8a = ab$

$0 = ab - 8a - 4b$

$32 = a(b-8)-4(b-8)$

$32 = (a-4)(b-8)$

$(a-4, b-8) = (32, 1) \Rightarrow (a,b) = (36, 9)$

$(a-4, b-8) = (16, 2) \Rightarrow (a,b) = (20, 10)$

Similarly for case c = 5,

$\displaystyle \frac1a+\frac2b+\frac{3}{5}=1 \Rightarrow \frac1a + \frac2b = \frac{2}{5}$

$5b + 10a = 2ab$

$0 = 2ab - 10a - 5b$

$25 = 2a(b-5) - 5(b-5)$

$25 = (2a-5)(b-5)$

$(2a-5, b-5) = (25, 1) \Rightarrow (a, b) = (15, 6)$

Therefore, the solutions are

$(a, b, c) = (36,9,4), (20,10,4), (15,6,5)$

A solution to BMO round 1 Problem 5

Posted: October 20, 2020 in Mathematics
Tags: math, Math Contest, number theory

WLOG, suppose that $a \leq b$ . Rewrite the equation as

$(a!-1)(b!-1)=c!+1$

Obviously, both a and b cannot be 0 or 1.

$a \neq 2$ , otherwise if a = 2 then

$b!-1=c!+1 \quad\text{or}\quad b!=c!+2$

which is impossible because no two factorials have the difference of 2.

By way of contradiction, assume $c \leq b$ , and the fact that $3 \leq a \leq b$ , we have

$3!b! \leq a!b! = a! + b! + c! \leq 3b!$

or $6 \leq 3$ , which is impossible. And hence b < c.

Next, we are gonna show that a = b. Assume a < b, then

$a+1 \leq b \quad\text{and} \quad a+2 \leq c \quad \text{ since } a<b<c$

and then

$\displaystyle a!b! = a! +b! + c! \quad \text{becomes} \quad b!=1+\frac{b!}{a!}+\frac{c!}{a!}$

This implies that $\dfrac{b!}{a!}$ is odd because $b!$ and $\dfrac{c!}{a!}$ are both even. And this mean that

$b=a+1$

otherwise $b \geq a+2$ and $\dfrac{b!}{a!} = b(b-1)\ldots(b-a-1)$ would be even.

So now $\displaystyle b! = 1 + \frac{b!}{a!} + \frac{c!}{a!}$ becomes

$\displaystyle (a+1)! = 1 + a+1 + \frac{c!}{a!}$

$\Rightarrow \quad 1 = (a+1)! - (a+1) - \dfrac{c!}{a!}$

$\Rightarrow \quad a+1 \mid 1 \quad\Rightarrow \quad a=0$

Contradiction, and hence a = b. And so we have,

$a!a!=2a!+c! \quad \text{or} \quad a! = 2+\dfrac{c!}{a!} \quad\text{for } 3 \leq a = b < c$

Hence, we have

$c = a + 1 \quad \text{or} \quad c = a + 2$

Suppose that $c \geq a + 3$ , then

$\displaystyle 3 \mid \frac{c!}{a!} \text{ and } 3 \mid a!$

then

$\displaystyle 3 \mid a!-\frac{c!}{a!} = 2$

Contradiction.

Case c = a + 2:

$a!=2+(a+2)(a+1)=a^2+3a+4$

$4=a!-a^2-3a=a((a-1)!-a-3)$

hence, $a \mid 4$ or a = 4 since $a\geq 3$ .

Then,

$4!4! = 4! + 4! + 6!$

$4! = 1 + 1 + 6\cdot5$

$24 = 32, \qquad \text{Contradiction.}$

Case c = a + 1:

$a!a! = a! + a! + (a+1)!$

$a! = 1 + 1 + a+1 = a + 3$

Obviously, a = 3 and a! > a + 3 for all integer a > 3.

Therefore, (a, b, c) = (3, 3, 4) is the only solution.

One-liner Solution to IMO 2012 Problem 2

Posted: October 8, 2020 in Mathematics
Tags: IMO, math, Math Contest

It is not quite often that you can solve the problem from IMO in one try, but I have just found one that I can do in one line. So here is the problem 2 from IMO 2012:

And here is the Solution in one line:

$\displaystyle \prod_{k=2}^n (1+a_k)^k = \prod_{k=2}^n \left(\sum_{j=1}^{k-1}\frac{1}{k-1}+a_k\right)^k \stackrel{A-G, \frac{1}{k-1}\neq a_k}{>} \prod_{k=2}^n \frac{k^k \cdot a_k}{(k-1)^{k-1}} \stackrel{\prod_2^n a_k=1}{=} n^n$

Detailed explanation:

The secret ingredient of cooking this dish is to realize that you can use AM-GM inequality to pan fry those summations into products and then heat it with telescoping product to reduce the sauce to the final result you want to prove.

So, start with the $(1+a_k)^k$ , you see there is an exponent of k, it may give us a hint that we need k terms when using AM-GM inequality, hence

$\displaystyle 1+a_k = \frac{k-1}{k-1}+a_k = \frac{1}{k-1}+\frac{1}{k-1}+\cdots+\frac{1}{k-1}+a_k = \sum_{j=1}^{k-1} \frac{1}{k-1} + a_k$

Next, $\frac{1}{k-1}$ and $a_k$ are positive, so we can apply the AM-GM inequality,

$\displaystyle \frac{1}{k} \left(\sum_{j=1}^{k-1}\frac{1}{k-1} + a_k\right) \geq \left(\frac{1}{(k-1)^{k-1}} \cdot a_k\right)^{1/k}$

Then raise both sides to the kth power and move the $k^k$ to the right,

$\displaystyle \left(\sum_{j=1}^{k-1} \frac{1}{k-1}+a_k\right)^k \geq \frac{k^k}{(k-1)^{k-1}} \cdot a_k$

Then, multiply $(n-1)$ of these inequalities together we get

$\displaystyle \prod_{k=2}^n \left(\sum_{j=1}^{k-1}\frac{1}{k-1}+a_k\right)^k \geq \prod_{k=2}^n \frac{k^k}{(k-1)^{k-1}}\cdot a_k$

Equality holds if $\frac{1}{k-1}=a_k \quad \forall k \in \{2,3,\ldots,n\}$ , but then we have

$\displaystyle \frac{1}{1}\cdot\frac{1}{2}\cdot\frac{1}{3}\cdots\frac{1}{n-1}=a_2 a_3 \cdots a_n = 1$

$(n-1)! = 1$

which is impossible because by assumption $n \geq 3$ , so this is indeed strict inequality,

$\displaystyle \prod_{k=2}^n \left(\sum_{j=1}^{k-1}\frac{1}{k-1}+a_k\right)^k > \prod_{k=2}^n \frac{k^k}{(k-1)^{k-1}}\cdot a_k$

or simply

$\displaystyle \prod_{k=2}^n (1+a_k)^k > \prod_{k=2}^n \frac{k^k}{(k-1)^{k-1}}\cdot a_k$

Then we can reduce the right side by using the telescoping product and the given assumption that $a_2 a_3 \cdots a_n = 1$ ,

$\displaystyle \prod_{k=2}^n \frac{k^k}{(k-1)^{k-1}}\cdot a_k = \frac{2^2\cdot3^3\cdot4^4\cdots n^n}{1^1\cdot2^2\cdot3^3\cdots(n-1)^{n-1}}\cdot a_2 a_3 \cdots a_n = n^n$