Difference between revisions of "Problems Collection"

(Other Problems (This section will be deleted once I cleared out the page))
 
(97 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
This is a page where you can share the problems you made (try not to use past exams).  
 
This is a page where you can share the problems you made (try not to use past exams).  
  
If you have problems or solutions to problems already on this page to contribute, please put it below. In the former case, please give at least one solution to that problem. Problems/solutions in the following section shall be inspected by [[User:Ddk001|Ddk001]] and will be put in the section after that section. If you would like, put your user name to the list of contributors of this page (at the near-end).
+
If you have problems or solutions to problems already on this page to contribute, please put it below. If you would like, put your user name to the list of contributors of this page (at the near-end).
  
 
==Contributed Problems and Solutions==
 
==Contributed Problems and Solutions==
  
 +
Please contribute whatever problems you have.
  
WARNING: This page is going to be a very very messy page and will be hard to clear out!
+
==Problems==
==AMC styled==
+
===AMC styled===
==AIME styled==
+
Nothing yet to show
1. There is one and only one perfect square in the form
+
===AIME styled===
 +
1. There is exactly one perfect square in the form <math>(p^2+1)(q^2+1)-((pq)^2-pq+1)</math> where <math>p</math> and <math>q</math> are prime. Find that perfect square.
  
<cmath>(p^2+1)(q^2+1)-((pq)^2-pq+1)</cmath>
+
2. <math>m</math> and <math>n</math> are positive integers. If <math>m^2=2^8+2^{11}+2^n</math>, find <math>m+n</math>.
 +
 
 +
3. The fraction, <math>\frac{ab+bc+ac}{(a+b+c)^2}</math>, where <math>a,b</math> and <math>c</math> are side lengths of a triangle, lies in the interval <math>(p,q]</math>, where <math>p</math> and <math>q</math> are rational numbers. Then, <math>p+q</math> can be expressed as <math>\frac{r}{s}</math>, where <math>r</math> and <math>s</math> are relatively prime positive integers. Find <math>r+s</math>.
 +
 
 +
4. Suppose there are complex values <math>x_1, x_2,</math> and <math>x_3</math> that satisfy
 +
 
 +
<cmath>(x_i-\sqrt[3]{13})(x_i-\sqrt[3]{53})(x_i-\sqrt[3]{103})=\frac{1}{3}</cmath>
 +
Find <math>x_{1}^3+x_{2}^3+x_{2}^3</math>.
 +
 
 +
5.Suppose
 +
 
 +
<cmath>x \equiv 2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6 \pmod{7!}</cmath>
 +
Find the remainder when <math>\min{x}</math> is divided by 1000.
 +
 
 +
 
 +
6.Suppose that there is <math>192</math> rings, each of different size. All of them are placed on a peg, smallest on the top and biggest on the bottom. There are <math>2</math> other pegs positioned sufficiently apart. A <math>move</math> is made if
 +
 
 +
(i) <math>1</math> ring changed position (i.e., that ring is transferred from one peg to another)
 +
 
 +
(ii) No bigger rings are on top of smaller rings.
 +
 
 +
Then, let <math>x</math> be the minimum possible number <math>moves</math> that can transfer all <math>192</math> rings onto the second peg. Find the remainder when <math>x</math> is divided by <math>1000</math>.
 +
 
 +
 
 +
7.Let <math>\overline{ab}</math> be a 2-digit [[positive integer]] satisfying <math>\overline{ab}^2=a! +b!</math>. Find the sum of all possible values of  <math>\overline{ab}</math>.
 +
 
 +
8.Suppose <math>f(x)</math> is a <math>10000000010</math>-degrees polynomial. The [[Fundamental Theorem of Algebra]] tells us that there are <math>10000000010</math> roots, say <math>r_1, r_2, \dots, r_{10000000010}</math>. Suppose all integers <math>n</math> ranging from <math>-1</math> to <math>10000000008</math> satisfies <math>f(n)=n</math>. Also, suppose that
 +
 
 +
<cmath>(2+r_1)(2+r_2) \dots (2+r_{10000000010})=m!</cmath>
 +
 
 +
for an integer <math>m</math>. If <math>p</math> is the minimum possible positive integral value of
 +
 
 +
<cmath>(1+r_1)(1+r_2) \dots (1+r_{10000000010})</cmath>.
 +
 
 +
Find the number of factors of the prime <math>999999937</math> in <math>p</math>.
 +
 
 +
 
 +
9.<math>\Delta ABC</math> is an isosceles triangle where <math>CB=CA</math>. Let the circumcircle of <math>\Delta ABC</math> be <math>\Omega</math>. Then, there is a point <math>E</math> and a point <math>D</math> on circle <math>\Omega</math> such that <math>AD</math> and <math>AB</math> trisects <math>\angle CAE</math> and <math>BE<AE</math>, and point <math>D</math> lies on minor arc <math>BC</math>. Point <math>F</math> is chosen on segment <math>AD</math> such that <math>CF</math> is one of the altitudes of <math>\Delta ACD</math>. Ray <math>CF</math> intersects <math>\Omega</math> at point <math>G</math> (not <math>C</math>) and is extended past <math>G</math> to point <math>I</math>, and <math>IG=AC</math>. Point <math>H</math> is also on <math>\Omega</math> and <math>AH=GI<HB</math>. Let the perpendicular bisector of <math>BC</math> and <math>AC</math> intersect at <math>O</math>. Let <math>J</math> be a point such that <math>OJ</math> is both equal to <math>OA</math> (in length) and is perpendicular to <math>IJ</math> and <math>J</math> is on the same side of <math>CI</math> as <math>A</math>. Let <math>O’</math> be the reflection of point <math>O</math> over line <math>IJ</math>. There exist a circle <math>\Omega_1</math> centered at <math>I</math> and tangent to <math>\Omega</math> at point <math>K</math>. <math>IO’</math> intersect <math>\Omega_1</math> at <math>L</math>. Now suppose <math>O’G</math> intersects <math>\Omega</math> at one distinct point, and <math>O’, G</math>, and <math>K</math> are collinear. If <math>IG^2+IG \cdot GC=\frac{3}{4} IK^2 + \frac{3}{2} IK \cdot O’L + \frac{3}{4} O’L^2</math>, then <math>\frac{EH}{BH}</math> can be expressed in the form <math>\frac{\sqrt{b}}{a} (\sqrt{c} + d)</math>, where <math>b</math> and <math>c</math> are not divisible by the squares of any prime. Find <math>a^2+b^2+c^2+d^2+abcd</math>.
 +
 
 +
 
 +
10. Let <math>A={1,2, \dots ,100}</math>. Let <math>A_i</math>, for each <math>i</math> between <math>1</math> and an positive integer <math>m</math>, be four-element subsets of the set <math>A</math>, no 2 of which have 3 or 4 elements in common. If <math>m \ge 40425</math>, find the last 3 digids of the sum of all elements, distinct or not, of the <math>A_i</math>'s.
 +
 
 +
 
 +
11. Let <math>x</math> be the remainder when
 +
 
 +
<cmath>106! + (53!)^2</cmath>
 +
 
 +
is divided by <math>107 \cdot 53^3</math>. Find the remainder when <math>x</math> is divided by <math>1000</math>.
 +
 
 +
 
 +
12. Let <math>\pi (n)</math> denote the number of primes that is less than or equal to <math>n</math>.
 +
 
 +
Show that there exist numbers <math>c_1</math> and <math>c_2</math> such that
 +
 
 +
<cmath>c_1 \frac{x}{\log{x}} \le \pi (x) \le c_2 \frac{x}{\log{x}}</cmath>
 +
 
 +
 
 +
13. Suppose there is <math>6</math> hats and <math>34</math> bins to put them in, and all objects are assigned a corresponding integer. Suppose there is <math>x</math> ways of putting the hats in the bins such that the following criteria are followed:
 +
 
 +
(i) If <math>i<j</math> (where <math>i</math> and <math>j</math> are integers), then hat <math>i</math> is placed in a bin whose number is less than or equal to the number of the bin that hat <math>j</math> is placed in
 +
 
 +
(ii) There is at least one bin that contains at least two hats
  
where <math>p</math> and <math>q</math> are prime. Find that perfect square.
+
Find <math>x \mod 1000</math>.
  
 +
===Olympiad styled===
 +
1. Let <math>0<a<b</math> and <math>t_i \ge 0, i=1,2, \dots ,n</math>. Suppose further that <math>t_1 + t_2 + \dots + t_n =1</math>. Then show that for any <math>x_1, x_2, \dots, x_n \in [a,b],</math>
  
2. <math>m</math> and <math>n</math> are positive integers. If <math>m^2=2^8+2^{11}+2^n</math>, find <math>m+n</math>.
+
<cmath>1 \le (\sum_{n=1}^{n} t_i x_i )(\sum_{n=1}^{n} \frac{t_i}{x_i} ) \le \frac{(a+b)^2}{4ab}</cmath>
  
 +
2. Let <math>a_1, a_2, \dots, a_n</math> be a sequence of positive integers such that for all <math>i</math> with <math>1 \leq i \leq n</math>, the following condition holds:
 +
<cmath>
 +
a_i^2 - a_{i+1}^2 = 1 \quad \text{for} \quad i = 1, 2, \dots, n-1,
 +
</cmath>
 +
where <math>a_{n+1} = a_1</math>.
  
3.The fraction,  
+
If <math>a_1 = 1</math>, what is the value of <math>a_n</math> in terms of <math>n</math>? ([[Problems Collection#Problem_22|Solution]])
  
<cmath>\frac{ab+bc+ac}{(a+b+c)^2}</cmath>
+
===Putnam styled (Calculus version of AMC, AIME, and Olympiad)===
 +
1.Suppose <cmath>\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}+\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]=\frac{p}{q}</cmath> where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.
  
where <math>a,b</math> and <math>c</math> are side lengths of a triangle, lies in the interval <math>(p,q]</math>, where <math>p</math> and <math>q</math> are rational numbers. Then, <math>p+q</math> can be expressed as <math>\frac{r}{s}</math>, where <math>r</math> and <math>s</math> are relatively prime positive integers. Find <math>r+s</math>.
 
  
 +
2. Let <math>x,y</math> and <math>z</math> be real numbers. Show that
  
4. Suppose there is complex values <math>x_1, x_2,</math> and <math>x_3</math> that satisfy
+
<cmath>(x^2+z^2)^2+y^4 \ge 4xzy^2</cmath>
  
<cmath>(x_i-\sqrt[3]{13})((x_i-\sqrt[3]{53})(x_i-\sqrt[3]{103})=\frac{1}{3}</cmath>
 
  
Find <math>x_{1}^3+x_{2}^3+x_{2}^3</math>.
+
3. Common blood types are determined genetically by 3 alleles: <math>A</math>,<math>B</math>, and <math>O</math>. A person whose blood genotype is <math>AB</math>, <math>AO</math>, <math>BO</math>, <math>BA</math>, <math>OA</math>, or <math>OB</math> is heterozygous while a person whose blood genotype is <math>AA</math>, <math>OO</math>, or <math>BB</math> is homozygous. The Hardy-Weinberg Law states that the proportion P of heterozygous individuals in a certain population (in genetic equilibrium) is given by
  
 +
<cmath>P(p,q,r)=2pq+2pr+2qr</cmath>
  
5. Suppose
+
where <math>p</math> is the percent of allele <math>A</math>, <math>q</math> the percent of allele <math>B</math>, and <math>r</math> the percent allele <math>O</math> within the population. Find the maximum possible proportion of heterozygous individuals in a population (in genetic equilibrium).
  
<cmath>x \equiv 2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6 \pmod{7!}</cmath>
+
4. Let
  
Find the remainder when <math>\min{x}</math> is divided by <math>1000</math>.
+
<cmath>(x^2-2y)^3+(y^2-2x)^3+(4-xy)^3-3(x^2-2y)(y^2-2x)(4-xy)=64</cmath>
  
 +
and <math>x=\frac{6m}{1+m^3} <0</math> for a real number <math>m</math>.
  
6. Suppose that there is <math>192</math> rings, each of different size. All of them are placed on a peg, smallest on the top and biggest on the bottom. There are <math>2</math> other pegs positioned sufficiently apart. A <math>move</math> is made if
+
Find <math>y</math> in terms of <math>m</math>.
  
<math>(i)</math> <math>1</math> ring changed position (i.e., that ring is transferred from one peg to another)
+
===Others (proofs & ect.)===
 +
1.In <math>\Delta ABC</math> with <math>AB=AC</math>, <math>D</math> is the foot of the perpendicular from <math>A</math> to <math>BC</math>. <math>E</math> is the foot of the perpendicular from <math>D</math> to <math>AC</math>. <math>F</math> is the midpoint of <math>DE</math>. Prove that <math>AF \perp BE</math>.
  
<math>(ii)</math> No rings are on top of smaller rings.
 
  
Then, let <math>x</math> be the minimum possible number <math>moves</math> that can transfer all <math>192</math> rings onto the second peg. Find the remainder when <math>x</math> is divided by <math>1000</math>.
+
2.Show that the series
  
 +
<cmath>\sum_{n=2}^\infty \frac{1}{n^m (\log{n})^p}</cmath>
  
7. Let <math>\overline{ab}</math> be a 2-digit [[positive integer]] satisfying <math>\overline{ab}^2=a! +b!</math>. Find the sum of all possible values of  <math>\overline{ab}</math>.
+
where p and m are real numbers converge if <math>m>1</math> or <math>m=1</math> but <math>p>1</math> and diverge otherwise.
  
  
 +
3. Let <math>F_n</math> denote the <math>n</math>th Fibonacci number. Prove that if <math>n</math> is odd, then all odd prime divisors of <math>F_n</math> are <math>1 \mod{4}</math>.
  
8. Suppose <math>f(x)</math> is a <math>10000000010</math>-degrees polynomial. The Fundamental Theorem of Algebra tells us that there are <math>10000000010</math> roots, say <math>r_1, r_2, \dots, r_{10000000010}</math>. Suppose all integers <math>n</math> ranging from <math>-1</math> to <math>10000000008</math> satisfies <math>f(n)=n</math>. Also, suppose that
+
Problem by [[User:Yiyj1|Yiyj1]]
  
<cmath>(2+r_1)(2+r_2) \dots (2+r_{10000000010})=m!</cmath>
+
4. In a triangle <math>ABC</math>, the incircle touches side <math>BC</math> at <math>D</math>, side <math>CA</math> at <math>E</math>, and side <math>AB</math> at <math>F</math>. Let <math>P</math> be the point of intersection of lines <math>AF</math> and <math>CE</math>, and let the incircle’s radius be <math>r</math>. Prove that the area of triangle <math>AEF</math> is equal to the area of triangle <math>ABC</math> divided by <math>2r</math>.
  
for an integer <math>m</math>. If <math>p</math> is the minimum possible positive integral value of
+
<asy>
 +
// Asymptote code and diagram by aoum
 +
size(250);
 +
defaultpen(fontsize(10pt));
  
<cmath>(1+r_1)(1+r_2) \dots (1+r_{10000000010})</cmath>.
+
// Define triangle vertices
 +
pair A = (0,5);
 +
pair B = (-4,0);
 +
pair C = (4,0);
  
Find the number of factors of the prime <math>999999937</math> in <math>p</math>.
+
// Draw triangle ABC
 +
draw(A--B--C--cycle);
  
 +
// Incenter and incircle
 +
pair I = incenter(A,B,C);
 +
real r = abs(foot(I,B,C) - I);
 +
draw(circle(I, r), dashed);
  
9. <math>\Delta ABC</math> is an isosceles triangle where <math>CB=CA</math>. Let the circumcircle of <math>\Delta ABC</math> be <math>\Omega</math>. Then, there is a point <math>E</math> and a point <math>D</math> on circle <math>\Omega</math> such that <math>AD</math> and <math>AB</math> trisects <math>\angle CAE</math> and <math>BE<AE</math>, and point <math>D</math> lies on minor arc <math>BC</math>. Point <math>F</math> is chosen on segment <math>AD</math> such that <math>CF</math> is one of the altitudes of <math>\Delta ACD</math>. Ray <math>CF</math> intersects <math>\Omega</math> at point <math>G</math> (not <math>C</math>) and is extended past <math>G</math> to point <math>I</math>, and <math>IG=AC</math>. Point <math>H</math> is also on <math>\Omega</math> and <math>AH=GI<HB</math>. Let the perpendicular bisector of <math>BC</math> and <math>AC</math> intersect at <math>O</math>. Let <math>J</math> be a point such that <math>OJ</math> is both equal to <math>OA</math> (in length) and is perpendicular to <math>IJ</math> and <math>J</math> is on the same side of <math>CI</math> as <math>A</math>. Let <math>O’</math> be the reflection of point <math>O</math> over line <math>IJ</math>. There exist a circle <math>\Omega_1</math> centered at <math>I</math> and tangent to <math>\Omega</math> at point <math>K</math>. <math>IO’</math> intersect <math>\Omega_1</math> at <math>L</math>. Now suppose <math>O’G</math> intersects <math>\Omega</math> at one distinct point, and <math>O’, G</math>, and <math>K</math> are collinear. If <math>IG^2+IG \cdot GC=\frac{3}{4} IK^2 + \frac{3}{2} IK \cdot O’L + \frac{3}{4} O’L^2</math>, then <math>\frac{EH}{BH}</math> can be expressed in the form <math>\frac{\sqrt{b}}{a} (\sqrt{c} + d)</math>, where <math>b</math> and <math>c</math> are not divisible by the squares of any prime. Find <math>a^2+b^2+c^2+d^2+abcd</math>.
+
// Tangency points (feet of perpendiculars from incenter to triangle sides)
 +
pair D = foot(I, B, C);
 +
pair E = foot(I, C, A);
 +
pair F = foot(I, A, B);
  
Someone mind making a diagram for this?
+
// Cevians AF and CE
 +
draw(A--F);
 +
draw(C--E);
  
 +
// Intersection point P of AF and CE
 +
pair P = extension(A, F, C, E);
  
10. Suppose <cmath>\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}+\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]=\frac{p}{q}</cmath> where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.
+
// Triangle AEF
 +
draw(A--E--F--cycle);
  
==Proofs==
+
// Points
11. In <math>\Delta ABC</math> with <math>AB=AC</math>, <math>D</math> is the foot of the perpendicular from <math>A</math> to <math>BC</math>. <math>E</math> is the foot of the perpendicular from <math>D</math> to <math>AC</math>. <math>F</math> is the midpoint of <math>DE</math>. Prove that <math>AF</math> is perpendicular to <math>BE</math>.
+
dot("$A$", A, dir(90));
 +
dot("$B$", B, dir(-135));
 +
dot("$C$", C, dir(-45));
 +
dot("$I$", I, dir(180));
 +
dot("$D$", D, dir(-90));
 +
dot("$E$", E, dir(45));
 +
dot("$F$", F, dir(135));
 +
</asy>
 +
([[Problems Collection#Problem_23|Solution]])
  
 
==Solutions==
 
==Solutions==
Line 111: Line 212:
 
Calculating the terms on the RHS, we find that <math>256 + 2048 + 2^n = 2304 + 2^n = m^2</math>. We use trial-and-error to find a power of two that makes the RHS a perfect square. We find that <math>4096 = 2^{12}</math> works, and it produces <math>6400 = 80^2</math>. Then <math>m + n = \boxed{092}</math>.
 
Calculating the terms on the RHS, we find that <math>256 + 2048 + 2^n = 2304 + 2^n = m^2</math>. We use trial-and-error to find a power of two that makes the RHS a perfect square. We find that <math>4096 = 2^{12}</math> works, and it produces <math>6400 = 80^2</math>. Then <math>m + n = \boxed{092}</math>.
  
~ (also) cxsmi
+
~ cxsmi
 
===Problem 3===
 
===Problem 3===
 
The fraction,  
 
The fraction,  
Line 177: Line 278:
 
<cmath>\implies \frac{ab+bc+ac}{(a+b+c)^2}>\frac{1}{4}</cmath> <math>\square</math>
 
<cmath>\implies \frac{ab+bc+ac}{(a+b+c)^2}>\frac{1}{4}</cmath> <math>\square</math>
  
Even though unallowed, if <math>a=0,b=c</math>, then <math>\frac{ab+bc+ac}{(a+b+c)^2}=\frac{1}{4}</math>, so
+
Note that
  
 
<cmath>\lim_{b=c,a \to 0} (\frac{ab+bc+ac}{(a+b+c)^2})=\frac{1}{4}</cmath>.
 
<cmath>\lim_{b=c,a \to 0} (\frac{ab+bc+ac}{(a+b+c)^2})=\frac{1}{4}</cmath>.
Line 183: Line 284:
 
Hence, <math>p=\frac{1}{4}</math>, since by taking <math>b=c</math> and <math>a</math> close <math>0</math>, we can get <math>\frac{ab+bc+ac}{(a+b+c)^2}</math> to be as close to <math>\frac{1}{4}</math> as we wish.
 
Hence, <math>p=\frac{1}{4}</math>, since by taking <math>b=c</math> and <math>a</math> close <math>0</math>, we can get <math>\frac{ab+bc+ac}{(a+b+c)^2}</math> to be as close to <math>\frac{1}{4}</math> as we wish.
  
<math>p+q=\frac{1}{3}+\frac{1}{4}=\frac{7}{12} \implies r+s=7+12=\boxed{019}</math> <math>\blacksquare</math>~[[Ddk001]]
+
<math>p+q=\frac{1}{3}+\frac{1}{4}=\frac{7}{12} \implies r+s=7+12=\boxed{019}</math> <math>\square</math>~[[Ddk001]]
  
 
===Solution 2 (Fast, risky, no proofs)===
 
===Solution 2 (Fast, risky, no proofs)===
Line 195: Line 296:
  
 
===Solution 1===
 
===Solution 1===
To make things easier, instead of saying <math>x_i</math>, we say <math>x</math>.
+
We interpret the <math>x_i</math> 's as roots of the polynomial
  
Now, we have
 
 
<cmath>(x-\sqrt[3]{13})(x-\sqrt[3]{53})(x-\sqrt[3]{103})=\frac{1}{3}</cmath>.
 
<cmath>(x-\sqrt[3]{13})(x-\sqrt[3]{53})(x-\sqrt[3]{103})=\frac{1}{3}</cmath>.
 +
 
Expanding gives  
 
Expanding gives  
  
Line 247: Line 348:
 
<cmath>=\boxed{170}</cmath>. <math>\square</math>
 
<cmath>=\boxed{170}</cmath>. <math>\square</math>
  
Note: If you don't know [[Newton's Sums]], you can also use [[Vieta's Formulas]] to bash.~[[Ddk001]]
+
Note: If you don't know [[Newton's Sums]], you can also use [[Vieta's Formulas]] to bash.
 +
~[[Ddk001]]
  
 
===Problem 5===
 
===Problem 5===
Line 286: Line 388:
 
<cmath>x \equiv 0 \pmod{144}</cmath>.
 
<cmath>x \equiv 0 \pmod{144}</cmath>.
  
Solving yields <math>x \equiv 2\boxed{736} \pmod{7!}</math>, and we're done. <math>\square</math>~[[Ddk001]]
+
Solving yields <math>x \equiv 2\boxed{736} \pmod{7!}</math>, and we're done. <math>\square</math>
 +
~[[Ddk001]]
  
 
===Problem 6===
 
===Problem 6===
Line 434: Line 537:
 
Testing cases, we can see that there is no such <math>b</math>.
 
Testing cases, we can see that there is no such <math>b</math>.
  
We see that <math>(a,b)=(7,1) \implies a+b=\boxed{008}</math>. <math>\blacksquare</math> ~[[Ddk001]]
+
We see that <math>(a,b)=(7,1) \implies a+b=\boxed{008}</math>. <math>square</math>
 +
~[[Ddk001]]
  
 
===Solution 2 (Official)===
 
===Solution 2 (Official)===
Line 461: Line 565:
 
which is really very easy to calculate and get 71 as the only possible solution to the problem and  
 
which is really very easy to calculate and get 71 as the only possible solution to the problem and  
  
thus, our answer is 7+1=<math>\boxed{008}</math>.~ SANSGANKRSNGUPTA
+
thus, our answer is 7+1=<math>\boxed{008}</math>.
 +
~SANSGANKRSNGUPTA
  
 
===Solution 3 (Official and Fastest)===
 
===Solution 3 (Official and Fastest)===
Line 484: Line 589:
 
which is very easy to calculate and get 71 as the only possible solution to the problem and  
 
which is very easy to calculate and get 71 as the only possible solution to the problem and  
  
thus, our answer is 7+1=<math>\boxed{008}</math>.~ SANSGANKRSNGUPTA
+
thus, our answer is 7+1=<math>\boxed{008}</math>.
 +
~SANSGANKRSNGUPTA
 
===Problem 8===
 
===Problem 8===
 
Suppose <math>f(x)</math> is a <math>10000000010</math>-degrees polynomial. The [[Fundamental Theorem of Algebra]] tells us that there are <math>10000000010</math> roots, say <math>r_1, r_2, \dots, r_{10000000010}</math>. Suppose all integers <math>n</math> ranging from <math>-1</math> to <math>10000000008</math> satisfies <math>f(n)=n</math>. Also, suppose that
 
Suppose <math>f(x)</math> is a <math>10000000010</math>-degrees polynomial. The [[Fundamental Theorem of Algebra]] tells us that there are <math>10000000010</math> roots, say <math>r_1, r_2, \dots, r_{10000000010}</math>. Suppose all integers <math>n</math> ranging from <math>-1</math> to <math>10000000008</math> satisfies <math>f(n)=n</math>. Also, suppose that
Line 543: Line 649:
 
<cmath>=5000000005 \cdot 10000000010!</cmath>
 
<cmath>=5000000005 \cdot 10000000010!</cmath>
  
, so there is <math>\left\lfloor \frac{10000000010}{999999937} \right\rfloor=\boxed{011}</math> factors of <math>999999937</math>. <math>\square</math>~[[Ddk001]]
+
, so there is <math>\left\lfloor \frac{10000000010}{999999937} \right\rfloor=\boxed{011}</math> factors of <math>999999937</math>. <math>\square</math>
 +
~[[Ddk001]]
  
 
===Problem 9===
 
===Problem 9===
 
<math>\Delta ABC</math> is an isosceles triangle where <math>CB=CA</math>. Let the circumcircle of <math>\Delta ABC</math> be <math>\Omega</math>. Then, there is a point <math>E</math> and a point <math>D</math> on circle <math>\Omega</math> such that <math>AD</math> and <math>AB</math> trisects <math>\angle CAE</math> and <math>BE<AE</math>, and point <math>D</math> lies on minor arc <math>BC</math>. Point <math>F</math> is chosen on segment <math>AD</math> such that <math>CF</math> is one of the altitudes of <math>\Delta ACD</math>. Ray <math>CF</math> intersects <math>\Omega</math> at point <math>G</math> (not <math>C</math>) and is extended past <math>G</math> to point <math>I</math>, and <math>IG=AC</math>. Point <math>H</math> is also on <math>\Omega</math> and <math>AH=GI<HB</math>. Let the perpendicular bisector of <math>BC</math> and <math>AC</math> intersect at <math>O</math>. Let <math>J</math> be a point such that <math>OJ</math> is both equal to <math>OA</math> (in length) and is perpendicular to <math>IJ</math> and <math>J</math> is on the same side of <math>CI</math> as <math>A</math>. Let <math>O’</math> be the reflection of point <math>O</math> over line <math>IJ</math>. There exist a circle <math>\Omega_1</math> centered at <math>I</math> and tangent to <math>\Omega</math> at point <math>K</math>. <math>IO’</math> intersect <math>\Omega_1</math> at <math>L</math>. Now suppose <math>O’G</math> intersects <math>\Omega</math> at one distinct point, and <math>O’, G</math>, and <math>K</math> are collinear. If <math>IG^2+IG \cdot GC=\frac{3}{4} IK^2 + \frac{3}{2} IK \cdot O’L + \frac{3}{4} O’L^2</math>, then <math>\frac{EH}{BH}</math> can be expressed in the form <math>\frac{\sqrt{b}}{a} (\sqrt{c} + d)</math>, where <math>b</math> and <math>c</math> are not divisible by the squares of any prime. Find <math>a^2+b^2+c^2+d^2+abcd</math>.
 
<math>\Delta ABC</math> is an isosceles triangle where <math>CB=CA</math>. Let the circumcircle of <math>\Delta ABC</math> be <math>\Omega</math>. Then, there is a point <math>E</math> and a point <math>D</math> on circle <math>\Omega</math> such that <math>AD</math> and <math>AB</math> trisects <math>\angle CAE</math> and <math>BE<AE</math>, and point <math>D</math> lies on minor arc <math>BC</math>. Point <math>F</math> is chosen on segment <math>AD</math> such that <math>CF</math> is one of the altitudes of <math>\Delta ACD</math>. Ray <math>CF</math> intersects <math>\Omega</math> at point <math>G</math> (not <math>C</math>) and is extended past <math>G</math> to point <math>I</math>, and <math>IG=AC</math>. Point <math>H</math> is also on <math>\Omega</math> and <math>AH=GI<HB</math>. Let the perpendicular bisector of <math>BC</math> and <math>AC</math> intersect at <math>O</math>. Let <math>J</math> be a point such that <math>OJ</math> is both equal to <math>OA</math> (in length) and is perpendicular to <math>IJ</math> and <math>J</math> is on the same side of <math>CI</math> as <math>A</math>. Let <math>O’</math> be the reflection of point <math>O</math> over line <math>IJ</math>. There exist a circle <math>\Omega_1</math> centered at <math>I</math> and tangent to <math>\Omega</math> at point <math>K</math>. <math>IO’</math> intersect <math>\Omega_1</math> at <math>L</math>. Now suppose <math>O’G</math> intersects <math>\Omega</math> at one distinct point, and <math>O’, G</math>, and <math>K</math> are collinear. If <math>IG^2+IG \cdot GC=\frac{3}{4} IK^2 + \frac{3}{2} IK \cdot O’L + \frac{3}{4} O’L^2</math>, then <math>\frac{EH}{BH}</math> can be expressed in the form <math>\frac{\sqrt{b}}{a} (\sqrt{c} + d)</math>, where <math>b</math> and <math>c</math> are not divisible by the squares of any prime. Find <math>a^2+b^2+c^2+d^2+abcd</math>.
  
Someone mind making a diagram for this?
+
{{image}}
 
===Solution 1===
 
===Solution 1===
 
Line <math>IJ</math> is tangent to <math>\Omega</math> with point of tangency point <math>J</math> because <math>OJ=OA \implies \text{J is on } \Omega</math> and <math>IJ</math> is perpendicular to <math>OJ</math> so this is true by the definition of tangent lines. Both <math>G</math> and <math>K</math> are on <math>\Omega</math> and line <math>O’G</math>, so <math>O’G</math> intersects <math>\Omega</math> at both <math>G</math> and <math>K</math>, and since we’re given <math>O’G</math> intersects <math>\Omega</math> at one distinct point, <math>G</math> and <math>K</math> are not distinct, hence they are the same point.  
 
Line <math>IJ</math> is tangent to <math>\Omega</math> with point of tangency point <math>J</math> because <math>OJ=OA \implies \text{J is on } \Omega</math> and <math>IJ</math> is perpendicular to <math>OJ</math> so this is true by the definition of tangent lines. Both <math>G</math> and <math>K</math> are on <math>\Omega</math> and line <math>O’G</math>, so <math>O’G</math> intersects <math>\Omega</math> at both <math>G</math> and <math>K</math>, and since we’re given <math>O’G</math> intersects <math>\Omega</math> at one distinct point, <math>G</math> and <math>K</math> are not distinct, hence they are the same point.  
Line 616: Line 723:
 
<cmath>a=4, b=2, c=3, d=1 \implies a^2+b^2+c^2+d^2+abcd=1+4+9+16+24=\boxed{054}</cmath>
 
<cmath>a=4, b=2, c=3, d=1 \implies a^2+b^2+c^2+d^2+abcd=1+4+9+16+24=\boxed{054}</cmath>
  
, and we’re done. <math>\blacksquare</math> ~[[Ddk001]]
+
, and we’re done. <math>\square</math> ~[[Ddk001]]
 +
 
  
 
===Problem 10===
 
===Problem 10===
Suppose <cmath>\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}+\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]=\frac{p}{q}</cmath> where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.
+
Let <math>A={1,2, \dots ,100}</math>. Let <math>A_i</math>, for each <math>i</math> between <math>1</math> and an positive integer <math>m</math>, be four-element subsets of the set <math>A</math>, no 2 of which have 3 or 4 elements in common. If <math>m \ge 40425</math>, find the last 3 digits of the sum of all elements, distinct or not, of the <math>A_i</math>'s.
  
===Solution 1(Wordless endless bash)===
+
===Solution 1===
<cmath>\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}</cmath>
+
Despite how ridiculously difficult this question might seem, there is actually a relatively simple solution, based on a slick observation.
 
 
<cmath>=\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{mn(m+n+2)}</cmath>
 
 
 
<cmath>=\sum_{n=1}^{\infty} \frac{1}{n} \sum_{m=1}^{\infty} \frac{1}{m(m+n+2)}</cmath>
 
 
 
<cmath>=\sum_{n=1}^{\infty} \frac{1}{n} \sum_{m=1}^{\infty} \frac{1}{n+2} (\frac{1}{m}-\frac{1}{m+n+2})</cmath>
 
 
 
<cmath>=\sum_{n=1}^{\infty} \frac{1}{n(n+2)} \sum_{m=1}^{\infty} (\frac{1}{m}-\frac{1}{m+n+2})</cmath>
 
 
 
<cmath>=\sum_{n=1}^{\infty} \frac{1}{n(n+2)} \cdot [(1-\frac{1}{n+3})+(\frac{1}{2}-\frac{1}{n+4})+ \dots]</cmath>
 
 
 
<cmath>=\sum_{n=1}^{\infty} \frac{1}{n(n+2)} \cdot (1+\frac{1}{2}+\frac{1}{3}+ \dots \frac{1}{n+2})</cmath>
 
 
 
<cmath>=\sum_{n=1}^{\infty} (\frac{\frac{1}{2}}{n}-\frac{\frac{1}{2}}{n+2}) \cdot (1+\frac{1}{2}+\frac{1}{3}+ \dots \frac{1}{n+2})</cmath>
 
 
 
<cmath>=\frac{1}{2} [(1-\frac{1}{3})(1+\frac{1}{2}+\frac{1}{3})+(\frac{1}{2}-\frac{1}{4})(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4})+ \dots</cmath>
 
 
 
<cmath>=\frac{1}{2} [[(1-\frac{1}{3})+(\frac{1}{3}-\frac{1}{5})+\dots](1+\frac{1}{2}+\frac{1}{3})+[(\frac{1}{2}-\frac{1}{4})+(\frac{1}{4}-\frac{1}{6})+\dots](1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4})+[(\frac{1}{3}-\frac{1}{5})+(\frac{1}{5}-\frac{1}{7})+\dots](\frac{1}{4}+\frac{1}{5})+\dots]</cmath>
 
 
 
<cmath>=\frac{1}{2} [(1+\frac{1}{2}+\frac{1}{3})+\frac{1}{2} (1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4})+\frac{1}{3} (\frac{1}{4}+\frac{1}{5})+\dots]</cmath>
 
 
 
<cmath>=\frac{1}{2} [\frac{11}{6}+\frac{1}{2} \cdot \frac{25}{12}+(\frac{1}{3 \cdot 4}+\frac{1}{4 \cdot 5}+\dots)+(\frac{1}{3 \cdot 5}+\frac{1}{4 \cdot 6}+\dots)]</cmath>
 
 
 
<cmath>=\frac{1}{2} [\frac{69}{24}+[(\frac{1}{3}-\frac{1}{4})+(\frac{1}{4}-\frac{1}{5})+\dots ]+\frac{1}{2} [(\frac{1}{3}-\frac{1}{5})+(\frac{1}{4}-\frac{1}{6})+\dots ]</cmath>
 
 
 
<cmath>=\frac{1}{2} [\frac{69}{24}+\frac{1}{3}+\frac{1}{6}+\frac{1}{8}]</cmath>
 
 
 
<cmath>=\frac{1}{2} \cdot \frac{84}{24}</cmath>
 
 
 
<cmath>=\frac{7}{4}</cmath>
 
 
 
<cmath>(1+\frac{1}{x})^x=e^{x \cdot \ln (1+\frac{1}{x})}</cmath>
 
 
 
<cmath>=e^{x \cdot [(\frac{1}{x})-\frac{(\frac{1}{x})^2}{2}+\frac{(\frac{1}{x})^3}{3}+\dots]}</cmath>
 
 
 
<cmath>=e^{1-\frac{1}{2} (\frac{1}{x})+\frac{1}{3} (\frac{1}{x})^2+\dots}</cmath>
 
 
 
<cmath>=e \cdot e^{-\frac{1}{2} (\frac{1}{x})} \cdot e^{\frac{1}{3} (\frac{1}{x})^2} \dots</cmath>
 
 
 
<cmath>=e \cdot [1-\frac{1}{2x}+\frac{1}{2!} (\frac{1}{2x})^2- \dots] \cdot [1+\frac{1}{3x^2}+\frac{1}{2!} (\frac{1}{3x^2})^2+ \dots]</cmath>
 
 
 
<cmath>=e[1-\frac{1}{2x}+\frac{11}{24} (\frac{1}{x})^2+\dots]</cmath>
 
 
 
<cmath>\implies \lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]</cmath>
 
 
 
<cmath>=\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{e[1-\frac{1}{2x}+\frac{11}{24} (\frac{1}{x})^2+\dots]}{e}-1]]</cmath>
 
 
 
<cmath>=\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 (1-\frac{1}{2x}+\frac{11}{24} (\frac{1}{x})^2+\dots-1)]</cmath>
 
 
 
<cmath>=\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 (-\frac{1}{2x}+\frac{11}{24} (\frac{1}{x})^2+\dots)]</cmath>
 
 
 
<cmath>=\lim_{x\rightarrow \infty} (\frac{x}{2}-\frac{x}{2}+\frac{11}{24}+\dots)</cmath>
 
  
<cmath>=\frac{11}{24}</cmath>
 
  
<cmath>\implies \sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}+\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]</cmath>
+
For each <math>A_i</math> there are <math>6</math> 2-element subsets that can be chosen from it. By the [[Pigeonhole Principle]], since there are only <math>4950</math> possible 2 element subsets of <math>A</math> at all, there must be at least one subset that appeared at least <math>\lfloor \frac{6 \cdot 40425}{4950} \rfloor =49</math> times. In fact, if <math>m >40425</math>, one subset appears 50 times. However, the condition about no 2 <math>A_i</math>'s having 3 or 4 elements in common shows that there'd be over <math>102</math> distinct elements in <math>A</math>, which is absurd. Thus, <math>m</math> is exactly <math>40425</math>, and this implies all 2-element subsets of <math>A</math> appeared exactly 49 times in <math>A_i</math>. Now, the sum of all 2-element subsets of <math>A_i</math> is exactly 3 times the sum of all elements in <math>A_i</math>, distinct or not, so our desired answer is <math>\frac{1}{3} \cdot 6 \cdot 40425 \cdot 101 = 8165 \boxed{850} </math> where the 101 is the average sum of 2-element subsets of <math>A</math>. <math>\square</math>
 
 
<cmath>=\frac{7}{4}+\frac{11}{24}</cmath>
 
 
 
<cmath>=\frac{53}{24}</cmath>
 
 
 
<cmath>\implies p=53,q=24</cmath>
 
 
 
<cmath>\implies p+q=\boxed{077}</cmath> <math>\square</math>~[[Ddk001]]
 
  
 
===Problem 11===
 
===Problem 11===
In <math>\Delta ABC</math> with <math>AB=AC</math>, <math>D</math> is the foot of the perpendicular from <math>A</math> to <math>BC</math>. <math>E</math> is the foot of the perpendicular from <math>D</math> to <math>AC</math>. <math>F</math> is the midpoint of <math>DE</math>. Prove that <math>AF \perp BE</math>.
 
  
===Solution 1 (Analytic geo)===
+
Let <math>x</math> be the remainder when
Let  
 
  
<cmath>A=(0,0)</cmath>
+
<cmath>106! + (53!)^2</cmath>
  
<cmath>B=(4a,4b)</cmath>
+
is divided by <math>107 \cdot 53^3</math>. Find the remainder when <math>x</math> is divided by <math>1000</math>.
  
<cmath>C=(4 \sqrt{a^2+b^2},0)</cmath>
+
===Solution 1 (Endless Hensel's Lemma)===
  
We set it this way to simplify calculation when we calculate the coordinates of <math>E</math> and <math>F</math> (Notice to find <math>E</math>, you just need to take the x coordinate of <math>D</math> and let the y coordinate be <math>0</math>).
+
We note that
  
Obviously,
+
<cmath>(53!)^2</cmath>
  
<cmath>D=(\frac{4a+4 \sqrt{a^2+b^2}}{2},\frac{4b+0}{2})=(2a+2 \sqrt{a^2+b^2},2b)</cmath>
+
<cmath>=1 \cdot 2 \cdot \dots \cdot 53 \cdot (53 \cdot 52 \cdot \dots \cdot 1)</cmath>
  
<cmath>\implies E=(2a+2 \sqrt{a^2+b^2},0)</cmath>
+
<cmath>=1 \cdot 2 \cdot \dots \cdot 53 \cdot [53 \cdot 52 \cdot \dots \cdot 1 \cdot (-1)^{53}] \cdot (-1)</cmath>
  
<cmath>\implies F=(\frac{2a+2 \sqrt{a^2+b^2}+2a+2 \sqrt{a^2+b^2}}{2},\frac{2b+0}{2})=(2a+2 \sqrt{a^2+b^2},b)</cmath>
+
<cmath>=1 \cdot 2 \cdot \dots \cdot 53 \cdot [(-53) \cdot (-52) \cdot \dots \cdot (-1)] \cdot (-1)</cmath>
  
Now, we see that
+
<cmath>\equiv 1 \cdot 2 \cdot \dots \cdot 53 \cdot [(107-53) \cdot (107-52) \cdot \dots \cdot (107-1)] \cdot (-1)</cmath>
  
<cmath>\text{Slope} _ {AF}=\frac{b}{2a+2 \sqrt{a^2+b^2}}</cmath>
+
<cmath>= 1 \cdot 2 \cdot \dots \cdot 53 \cdot 54 \cdot 55 \cdot \dots \cdot 106 \cdot (-1)</cmath>
  
<cmath>\text{Slope} _ {BE}=\frac{0-4b}{2a+2 \sqrt{a^2+b^2}-4a}=\frac{-2b}{\sqrt{a^2+b^2}-a}</cmath>
+
<cmath>= -106!</cmath>
  
<cmath>\implies \text{Slope} _ {AF} \cdot \text{Slope} _ {BE}=\frac{b}{2a+2 \sqrt{a^2+b^2}} \cdot \frac{-2b}{a+ \sqrt{a^2+b^2}-2a}=\frac{-2b^2}{2(a+\sqrt{a^2+b^2})(\sqrt{a^2+b^2}-a)}=\frac{-2b^2}{2b^2}=-1</cmath>
+
<cmath>\equiv 1 \pmod {107} </cmath>
  
, so <math>AF \perp BE</math>, as desired. <math>\square</math>~[[Ddk001]]
+
where the last step follows from [[Wilson's Theorem]].
===Solution 2 (Hard vector bash)===
 
====Solution 2a (Hard)====
 
<cmath>\overrightarrow{AF} \cdot \overrightarrow{BE}</cmath>
 
  
<cmath>=(\overrightarrow{AE}+\overrightarrow{EF}) \cdot (\overrightarrow{BD}+\overrightarrow{DE})</cmath>
+
Now, applying [[Wilson's Theorem]] again implies <math>106! \equiv 1 \pmod {107}</math>, so
  
<cmath>=\overrightarrow{AE} \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{DE}+\overrightarrow{AE} \cdot \overrightarrow{DE}</cmath>
+
<cmath>106! + (53!)^2 \equiv 0 \pmod {107}</cmath>
  
<cmath>=\overrightarrow{AE} \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{DE}</cmath>
+
We see that
  
<cmath>=(\overrightarrow{AD}+\overrightarrow{DE}) \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{BD} + \overrightarrow{EF} \cdot \overrightarrow{DE}</cmath>
+
<cmath>(52!)^2 \equiv (-1)^2</cmath>
  
<cmath>=\overrightarrow{DE} \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{BD} + \overrightarrow{EF} \cdot \overrightarrow{DE}</cmath>
+
<cmath>= 1 \pmod {53}</cmath>
  
<cmath>=\overrightarrow{DE} \cdot \overrightarrow{DC}-\frac{\overrightarrow{DE}}{2} \cdot \overrightarrow{BD}-\frac{\overrightarrow{DE}}{2} \cdot \overrightarrow{DE}</cmath>
+
by [[Wilson's Theorem]], so
  
<cmath>=\frac{\overrightarrow{DE}}{2} \cdot \overrightarrow{DC}-\frac{\overrightarrow{DE}}{2} \cdot \overrightarrow{DE}</cmath>
+
<cmath>(53!)^2 = 53^2 (52!)^2</cmath>
  
<cmath>=\overrightarrow{DE} \cdot (\frac{\overrightarrow{DC}-\overrightarrow{DE}}{2})</cmath>
+
<cmath>\equiv 53^2 \pmod {53^3}</cmath>
  
<cmath>=\frac{\overrightarrow{DE} \cdot \overrightarrow{EC}}{2}</cmath>
+
Somewhat similarly,
  
<cmath>=0</cmath>
+
<cmath>\frac{106!}{53^2} = \dbinom{106}{53} \cdot (52!)^2</cmath>
  
Hence, <math>AF \perp BE</math>. <math>\square</math>~[[Ddk001]]
+
<cmath>\equiv 2 \pmod {53}</cmath>
====Solution 2b (Harder)====
 
<cmath>\angle ACD=\angle ECD</cmath>
 
  
<cmath>\angle ADC=\angle DEC</cmath>
+
since <math>\binom{2p}{p} \equiv 2 \pmod p</math> when <math>p</math> is a prime. (Proof [[Proofs to Some Number Theory Facts|here]]) Thus,
  
<cmath>\implies \Delta ADC \sim \Delta DEC</cmath>
+
<cmath>106!= \frac{106!}{53^2} \cdot 53^2</cmath>
  
<cmath>\implies \frac{EC}{DC}=\frac{DC}{AC}</cmath>
+
<cmath>\equiv 2 \cdot 53^2 \pmod {53^3}</cmath>
  
<cmath>\implies EC=\frac{DC^2}{AC}</cmath>
+
so
  
<cmath>\implies \overrightarrow{E}=\overrightarrow{C}+\overrightarrow{CE}</cmath>
+
<cmath>106!+(53!)^2 \equiv 3 \cdot 53^2 \pmod {53^3}</cmath>
  
<cmath>=\overrightarrow{C}+\frac{CE}{AC} \cdot \overrightarrow{CA}</cmath>
+
We obtain the following linear system of congruences:
  
<cmath>=\overrightarrow{C}+\frac{DC^2}{AC^2} \overrightarrow{CA}</cmath>
+
<cmath>106! + (53!)^2 \equiv 0 \pmod {107}</cmath>
  
<cmath>=\overrightarrow{C}+\frac{DC^2}{AC^2} (\overrightarrow{A}-\overrightarrow{C})</cmath>
+
<cmath>106!+(53!)^2 \equiv 3 \cdot 53^2 \pmod {53^3}</cmath>
  
<cmath>=\frac{AC^2-DC^2}{AC^2} \overrightarrow{C}+\frac{DC^2}{AC^2} \overrightarrow{A}</cmath>
+
By the [[Chinese Remainder Theorem]],
  
<cmath>=\frac{AD^2}{AC^2} \overrightarrow{C}+\frac{DC^2}{AC^2} \overrightarrow{A}</cmath>
+
<cmath>106!+(53!)^2 \equiv 3 \cdot 53^2 \cdot 107 \cdot y \pmod {107 \cdot 53^3}</cmath>
  
<cmath>\overrightarrow{D}=\frac{\overrightarrow{B}+\overrightarrow{C}}{2}</cmath>
+
where <math>y</math> is an integer such that
  
Since <math>F</math> is the midpoint of <math>DE</math>,
+
<cmath>107y \equiv 1 \pmod {53^3}</cmath>
  
<cmath>\overrightarrow{F}=\frac{\overrightarrow{D}+\overrightarrow{E}}{2}</cmath>
+
(i.e. <math>y</math> is an inverse of <math>107</math> modulo <math>53^3</math>).
  
<cmath>=\frac{\frac{\overrightarrow{B}+\overrightarrow{C}}{2}+\frac{AD^2}{AC^2} \overrightarrow{C}+\frac{DC^2}{AC^2} \overrightarrow{A}}{2}</cmath>
+
Seeing a power of a prime as modulus reminds us of [[Hensel's Lemma]] for solving polynomial congruences. Let <cmath>f(y)=107y-1</cmath>. We wish to solve <math>f(y) \equiv 0 \pmod {53^3}</math>. Obviously, <math>107 \equiv 1 \pmod {53}</math>, so <math>f(1) \equiv 0 \pmod {53}</math>. By [[Hensel's Lemma]], there exists a unique integer <math>t \in [0,53)</math> such that <math>f(53t+1) \equiv 0 \pmod {53^2}</math>, and <math>t</math> is given by
  
<cmath>=\frac{\overrightarrow{B}}{4}+\frac{AC^2+2AD^2}{4AC^2} \overrightarrow{C}+\frac{DC^2}{2AC^2} \overrightarrow{A}</cmath>
+
<cmath>t=- \bar{f'(1)} \cdot (\frac{f(1)}{53})</cmath>
  
<cmath>\overrightarrow{AF}=\overrightarrow{F}-\overrightarrow{A}=\frac{\overrightarrow{B}}{4}+\frac{AC^2+2AD^2}{4AC^2} \overrightarrow{C}+\frac{DC^2-2AC^2}{2AC^2} \overrightarrow{A}</cmath>
+
where <math>\bar{f'(1)}</math> denotes the inverse of <math>f'(1)</math> modulo <math>53</math> (just <math>53</math>, not <math>53</math> to any power). Again, <math>107 \equiv 1 \pmod {53}</math>, so since <math>f'(1) =107</math>, <math>\bar{f'(1)}=1</math>, so
  
<cmath>\overrightarrow{BE}=\overrightarrow{E}-\overrightarrow{B}=\frac{AD^2}{AC^2} \overrightarrow{C}+\frac{DC^2}{AC^2} \overrightarrow{A}-\overrightarrow{B}</cmath>
+
<cmath>t= -1 \cdot \frac{106}{53}</cmath>
  
Now come the coordinates. Let
+
<cmath>=-2</cmath>
  
<cmath>A=(0,0)</cmath>
+
Therefore, we see that <math>f(-105) \equiv 0 \pmod {53^2}</math>. We preform another lift. Again, there exists unique integer <math>t \in [0,53)</math> such that <math>f(-105+53^2 \cdot t) \equiv 0 \pmod {53^3}</math>, given by
  
<cmath>B=(-a,-b)</cmath>
+
<cmath>t = - \bar{f'(-105)} \cdot (\frac{f(-105)}{53^2})</cmath>
  
<cmath>C=(a,-b)</cmath>
+
<math>f'(-105)</math> is also <math>107</math>, so <math>\bar{f'(-105)} = 1</math>. We have <math>f(-105)= -105 \cdot 107 -1=-106^2= (-4) \cdot 53^2</math>, so
  
so that
+
<cmath>t = -1 \cdot (\frac{(-4) \cdot 53^2}{53^2}</cmath>
  
<cmath>\overrightarrow{A}=\langle 0,0 \rangle</cmath>
+
<cmath>=4</cmath>
  
<cmath>\overrightarrow{B}=\langle -a,-b \rangle</cmath>
+
Therefore, <math>f(4 \cdot 53^2-105) \equiv 0 \pmod {53^3}</math>. We can thus set <math>y=4 \cdot 53^2-105</math>, so that
  
<cmath>\overrightarrow{C}=\langle a,-b \rangle</cmath>.
+
<cmath>x \equiv 106!+(53!)^2</cmath>
  
Therefore, 
+
<cmath>\equiv 3 \cdot 53^2 \cdot 107 \cdot y</cmath>
  
<cmath>\overrightarrow{AF}=\langle \frac{-a}{4},\frac{-b}{4} \rangle + \frac{(a^2+b^2)+2b^2}{4(a^2+b^2)} \langle a,-b \rangle=\langle \frac{ab^2}{2(a^2+b^2)},\frac{-a^2b-2b^3}{2(a^2+b^2)} \rangle</cmath>
+
<cmath>= 3 \cdot 53^2 \cdot 107 \cdot (4 \cdot 53^2-105)</cmath>
  
<cmath>\overrightarrow{BE}=\frac{b^2}{a^2+b^2} \langle a,-b \rangle-\langle -a,-b \rangle=\langle \frac{2ab^2+a^3}{a^2+b^2},\frac{a^2b}{a^2+b^2} \rangle</cmath>
+
<cmath>=12 \cdot 53^4 \cdot 107 - 315 \cdot 53^2 \cdot 107</cmath>
  
<cmath>\implies \overrightarrow{AF} \cdot \overrightarrow{BE}=\langle \frac{ab^2}{2(a^2+b^2)},\frac{-a^2b-2b^3}{2(a^2+b^2)} \rangle \cdot \langle \frac{2ab^2+a^3}{a^2+b^2},\frac{a^2b}{a^2+b^2} \rangle</cmath>
+
<cmath>\equiv - 315 \cdot 53^2 \cdot 107 \pmod {107 \cdot 53^3}</cmath>
  
<cmath>=\frac{1}{2(a^2+b^2)^2}[ab^2(a^3+2ab^2)-a^2b(a^2b+2b^3)]</cmath>
+
Thus,
  
<cmath>=\frac{ab}{2(a^2+b^2)^2} (a^3b+2ab^3-a^3b-2ab^3)</cmath>
+
<cmath>x=53^3 \cdot 107 \cdot k - 315 \cdot 53^2 \cdot 107</cmath>
  
<cmath>=0</cmath>
+
<cmath>= (53k-315) \cdot 53^2 \cdot 107</cmath>
  
Hence, we have that <math>AF</math> is perpendicular to <math>BE</math>. <math>\square</math> ~[[Ddk001]]
+
for some integer <math>k</math>. Since <math>0 \le x < 53^3 \cdot 107</math> (since it is a remainder), <math>0 \le 53k-315 < 53 \implies k=6</math>. Therefore,
  
==Problems I made==
+
<cmath>x=3 \cdot 53^2 \cdot 107</cmath>
===Aime styled===
 
====Introductory====
 
1. There is one and only one perfect square in the form
 
  
<cmath>(p^2+1)(q^2+1)-((pq)^2-pq+1)</cmath>
+
A simple calculation shows <math>53^2=2809</math>, so
  
where <math>p</math> and <math>q</math> are prime. Find that perfect square.
+
<cmath>x \equiv 3 \cdot 809 \cdot 107</cmath>
  
 +
<cmath>\equiv \boxed{689} \pmod {1000}</cmath>
  
2. <math>m</math> and <math>n</math> are positive integers. If <math>m^2=2^8+2^{11}+2^n</math>, find <math>m+n</math>.
+
This is our answer. <math>\square</math>.
 
+
~[[Ddk001]]
====Intermediate====
 
3.The fraction,
 
 
 
<cmath>\frac{ab+bc+ac}{(a+b+c)^2}</cmath>
 
 
 
where <math>a,b</math> and <math>c</math> are side lengths of a triangle, lies in the interval <math>(p,q]</math>, where <math>p</math> and <math>q</math> are rational numbers. Then, <math>p+q</math> can be expressed as <math>\frac{r}{s}</math>, where <math>r</math> and <math>s</math> are relatively prime positive integers. Find <math>r+s</math>.
 
 
 
 
 
4. Suppose there is complex values <math>x_1, x_2,</math> and <math>x_3</math> that satisfy
 
 
 
<cmath>(x_i-\sqrt[3]{13})((x_i-\sqrt[3]{53})(x_i-\sqrt[3]{103})=\frac{1}{3}</cmath>
 
 
 
Find <math>x_{1}^3+x_{2}^3+x_{2}^3</math>.
 
 
 
  
5. Suppose
+
===Problem 12===
  
<cmath>x \equiv 2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6 \pmod{7!}</cmath>
+
Let <math>\pi (n)</math> denote the number of primes that is less than or equal to <math>n</math>.
  
Find the remainder when <math>\min{x}</math> is divided by <math>1000</math>.
+
Show that there exist numbers <math>c_1</math> and <math>c_2</math> such that
  
 +
<cmath>c_1 \frac{x}{\log{x}} \le \pi (x) \le c_2 \frac{x}{\log{x}}</cmath>
  
6. Suppose that there is <math>192</math> rings, each of different size. All of them are placed on a peg, smallest on the top and biggest on the bottom. There are <math>2</math> other pegs positioned sufficiently apart. A <math>move</math> is made if
+
===Solution 1(The Proof by Chebyshev)===
  
(i) <math>1</math> ring changed position (i.e., that ring is transferred from one peg to another)
+
Let <math>p</math> be a prime and <math>n</math> be an integer. Since
  
(ii) No rings are on top of smaller rings.
+
<cmath>\dbinom{2n}{n} = \frac{(2n)!}{(n!)(n!)}</cmath>
  
Then, let <math>x</math> be the minimum possible number <math>moves</math> that can transfer all <math>192</math> rings onto the second peg. Find the remainder when <math>x</math> is divided by <math>1000</math>.
+
, <math>p</math> divides <math>\dbinom{2n}{n}</math> exactly
  
 +
<cmath>\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)</cmath>
  
7. Suppose <math>f(x)</math> is a <math>10000000010</math>-degrees polynomial. The Fundamental Theorem of Algebra tells us that there are <math>10000000010</math> roots, say <math>r_1, r_2, \dots, r_{10000000010}</math>. Suppose all integers <math>n</math> ranging from <math>-1</math> to <math>10000000008</math> satisfies <math>f(n)=n</math>. Also, suppose that
+
times.  
  
<cmath>(2+r_1)(2+r_2) \dots (2+r_{10000000010})=m!</cmath>
+
Therefore, since
  
for an integer <math>m</math>. If <math>p</math> is the minimum possible positive integral value of
+
<cmath>\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor \le 1</cmath>
  
<cmath>(1+r_1)(1+r_2) \dots (1+r_{10000000010})</cmath>.
+
, we have
  
Find the number of factors of the prime <math>999999937</math> in <math>p</math>.
+
<cmath>\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)</cmath>
  
 +
<cmath>\le \sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} 1</cmath>
  
====Olympiad====
+
<cmath>=\lfloor \log_{p}{(2n)} \rfloor</cmath>
  
8. (Much harder) <math>\Delta ABC</math> is an isosceles triangle where <math>CB=CA</math>. Let the circumcircle of <math>\Delta ABC</math> be <math>\Omega</math>. Then, there is a point <math>E</math> and a point <math>D</math> on circle <math>\Omega</math> such that <math>AD</math> and <math>AB</math> trisects <math>\angle CAE</math> and <math>BE<AE</math>, and point <math>D</math> lies on minor arc <math>BC</math>. Point <math>F</math> is chosen on segment <math>AD</math> such that <math>CF</math> is one of the altitudes of <math>\Delta ACD</math>. Ray <math>CF</math> intersects <math>\Omega</math> at point <math>G</math> (not <math>C</math>) and is extended past <math>G</math> to point <math>I</math>, and <math>IG=AC</math>. Point <math>H</math> is also on <math>\Omega</math> and <math>AH=GI<HB</math>. Let the perpendicular bisector of <math>BC</math> and <math>AC</math> intersect at <math>O</math>. Let <math>J</math> be a point such that <math>OJ</math> is both equal to <math>OA</math> (in length) and is perpendicular to <math>IJ</math> and <math>J</math> is on the same side of <math>CI</math> as <math>A</math>. Let <math>O’</math> be the reflection of point <math>O</math> over line <math>IJ</math>. There exist a circle <math>\Omega_1</math> centered at <math>I</math> and tangent to <math>\Omega</math> at point <math>K</math>. <math>IO’</math> intersect <math>\Omega_1</math> at <math>L</math>. Now suppose <math>O’G</math> intersects <math>\Omega</math> at one distinct point, and <math>O’, G</math>, and <math>K</math> are collinear. If <math>IG^2+IG \cdot GC=\frac{3}{4} IK^2 + \frac{3}{2} IK \cdot O’L + \frac{3}{4} O’L^2</math>, then <math>\frac{EH}{BH}</math> can be expressed in the form <math>\frac{\sqrt{b}}{a} (\sqrt{c} + d)</math>, where <math>b</math> and <math>c</math> are not divisible by the squares of any prime. Find <math>a^2+b^2+c^2+d^2+abcd</math>.
+
so if <math>p^r | \dbinom{2n}{n}</math>, <math>p^r \le 2n</math>
  
Someone mind making a diagram for this?
+
Repeated applications of that gives
  
 +
<cmath>\dbinom{2n}{n} \le (2n)^{\pi (2n)}</cmath>
  
9. Suppose <cmath>\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}+\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]=\frac{p}{q}</cmath> where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.
+
Additionally,
  
 +
<cmath>2^n=\prod_{a=1}^n {2} \le \prod_{a=1}^n {\frac{n+a}{a}} = \frac{(n+1) \cdot (n+2) \cdot \dots \cdot 2n}{n!} = \dbinom{2n}{n} \le \sum_{a=0}^{2n} {\dbinom{2n}{a}} = 2^{2n}</cmath>
  
===Proofs===
+
so
10. In <math>\Delta ABC</math> with <math>AB=AC</math>, <math>D</math> is the foot of the perpendicular from <math>A</math> to <math>BC</math>. <math>E</math> is the foot of the perpendicular from <math>D</math> to <math>AC</math>. <math>F</math> is the midpoint of <math>DE</math>. Prove that <math>AF</math> is perpendicular to <math>BE</math>.
 
  
I will leave a big gap below this sentence so you won't see the answers accidentally.
+
<cmath>2^n \le (2n)^{\pi (2n)}</cmath>
  
 +
<cmath>\implies n \cdot \log {2} \le \pi (2n) \cdot \log {2n}</cmath>
  
 +
<cmath>\implies \pi (2n) \ge \frac{n \cdot \log {2}}{\log {2n}}</cmath>
  
 +
<cmath>\implies \pi (n) \ge \frac{\log{2}}{2} \cdot \frac{n}{\log {n}}</cmath>
  
 +
Now, we note also that
  
 +
<cmath>\prod_{\text{p is a prime from n to 2n}} {p} | \dbinom{2n}{n}</cmath>
  
 +
so
  
 +
<cmath>n^{\pi (2n) - \pi (n)}=\prod_{\text{p is a prime from n to 2n}} n < \prod_{\text{p is a prime from n to 2n}} p \le \dbinom{2n}{n} \le 2^{2n}</cmath>
  
 +
Thus,
  
 +
<cmath>\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}</cmath>
  
 +
We have
  
 +
<cmath>\log {2n} \cdot \pi (2n)+\log {n} \cdot \pi (n)= \log {2} \cdot \pi (2n) + \log {n} \cdot (\pi (2n) - \pi (n)) \le \log {2} \cdot \pi (2n) + n \cdot \log {4} \le 3n \cdot \log {2}</cmath>
  
 +
since <math>\pi (2n) \le n</math> for <math>n>3</math> (because there is at least a half of even numbers).
  
 +
Repeated addition of that gives
  
 +
<cmath>\pi (2n) = \frac{1}{\log{2n}} \cdot (\log {2n} \cdot \pi (2n)- \log {n} \cdot \pi (n))+(\log {n} \cdot \pi (n)- \log {\frac{n}{2}} \cdot \pi (\frac{n}{2}))+ (\log {\frac{n}{2}} \cdot \pi (\frac{n}{2})- \log {\frac{n}{4}} \cdot \pi (\frac{n}{4}))+ \dots</cmath>
  
 +
<cmath>\le \frac{1}{\log {2n}} \cdot (3n \cdot \log {2}+\frac{3n}{2} \cdot \log {2}+\frac{3n}{4} \cdot \log {2}+ \dots)</cmath>
  
 +
<cmath>= \frac{3n \cdot \log {2}}{\log {2n}} \cdot (1+ \frac{1}{2}+\frac{1}{4} + \dots)</cmath>
  
 +
<cmath>= \frac{6n \cdot \log {2}}{\log {2n}}</cmath>
  
 +
<cmath>\le \frac{\log{64} \cdot n}{\log{n}}</cmath>
  
 +
As we have previously derived,
  
 
+
<cmath>\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}</cmath>
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
==Solutions==
 
 
 
<math>\textbf{I wrote a couple of solutions here. Hope it's okay :) - cxsmi (please feel free to delete this note and/or the solutions)}</math>
 
 
 
I like your solutions.~[[Ddk001]]
 
===Problem 1===
 
There is one and only one perfect square in the form
 
 
 
<cmath>(p^2+1)(q^2+1)-((pq)^2-pq+1)</cmath>
 
 
 
where <math>p</math> and <math>q</math> is prime. Find that perfect square.
 
 
 
===Solution 1===
 
<math>(p^2+1)(q^2+1)-((pq)^2-pq+1)=p^2 \cdot q^2 +p^2+q^2+1-p^2 \cdot q^2 +pq-1=p^2+q^2+pq</math>.
 
Suppose <math>n^2=(p^2+1)(q^2+1)-((pq)^2-pq+1)</math>.
 
Then,
 
 
 
<cmath>n^2=(p^2+1)(q^2+1)-((pq)^2-pq+1)=p^2+q^2+pq=(p+q)^2-pq \implies pq=(p+q)^2-n^2=(p+q-n)(p+q+n)</cmath>
 
 
 
, so since <math>n=\sqrt{p^2+q^2+pq}>\sqrt{p^2+q^2}</math>, <math>n>p,n>q</math> so <math>p+q-n</math> is less than both <math>p</math> and <math>q</math> and thus we have <math>p+q-n=1</math> and <math>p+q+n=pq</math>. Adding them gives <math>2p+2q=pq+1</math> so by [[Simon's Favorite Factoring Trick]], <math>(p-2)(q-2)=3 \implies (p,q)=(3,5)</math> in some order. Hence, <math>(p^2+1)(q^2+1)-((pq)^2-pq+1)=p^2+q^2+pq=\boxed{049}</math>.<math>\square</math>
 
 
 
===Problem 2===
 
<math>m</math> and <math>n</math> are positive integers. If <math>m^2=2^8+2^{11}+2^n</math>, find <math>m+n</math>.
 
===Solution 1 (Slow, probably official MAA)===
 
<cmath>m^2=2^8+2^{11}+2^n</cmath>
 
 
 
<cmath>\implies 2^n=m^2-2^8-2^{11}</cmath>
 
 
 
<cmath>\implies 2^n=(m+48)(m-48)</cmath>
 
 
 
Let <math>m+48=2^t</math> and <math>m-48=2^s</math>. Then,
 
 
 
<cmath>2^t-2^s=96 \implies 2^s(2^{t-s}-1)=2^5 \cdot 3 \implies 2^{t-s}-1=3,2^s=2^5 \implies (t,s)=(7,5) \implies m+n=80+12=\boxed{092}</cmath> <math>\square</math>
 
 
 
===Solution 2 (Fast)===
 
Recall that a perfect square <math>(a + b)^2</math> can be written as <math>a^2 + 2ab + b^2</math>. Since <math>m^2</math> is a perfect square, the RHS must be in this form. We substitute <math>2^4</math> for <math>a</math> to get that <math>2^8 + 2^5 \cdot 2^b + 2^{2b} = m^2</math>. To make the middle term have an exponent of <math>11</math>, we must have <math>b = 6</math>. Then <math>n = 12</math> and <math>m = (2^4 + 2^6)^2 = (16 + 64)^2 = 80^2</math>, so <math>m + n = \boxed{092}</math>.
 
 
 
~ cxsmi
 
 
 
===Solution 3 (Faster)===
 
Calculating the terms on the RHS, we find that <math>256 + 2048 + 2^n = 2304 + 2^n = m^2</math>. We use trial-and-error to find a power of two that makes the RHS a perfect square. We find that <math>4096 = 2^{12}</math> works, and it produces <math>6400 = 80^2</math>. Then <math>m + n = \boxed{092}</math>.
 
 
 
~ (also) cxsmi
 
 
 
===Problem 3===
 
The fraction,
 
 
 
<cmath>\frac{ab+bc+ac}{(a+b+c)^2}</cmath>
 
 
 
where <math>a,b</math> and <math>c</math> are side lengths of a triangle, lies in the interval <math>(p,q]</math>, where <math>p</math> and <math>q</math> are rational numbers. Then, <math>p+q</math> can be expressed as <math>\frac{r}{s}</math>, where <math>r</math> and <math>s</math> are relatively prime positive integers. Find <math>r+s</math>.
 
===Solution 1(Probably official MAA, lots of proofs)===
 
'''Lemma 1: <math>\text{max} (\frac{ab+bc+ac}{(a+b+c)^2})=\frac{1}{3}</math>'''
 
 
 
''Proof:'' Since the sides of triangles have positive length, <math>a,b,c>0</math>. Hence,
 
 
 
<cmath>\frac{ab+bc+ac}{(a+b+c)^2}>0 \implies \text{max} (\frac{ab+bc+ac}{(a+b+c)^2})= \frac{1}{\text{min} (\frac{(a+b+c)^2}{ab+bc+ac})}</cmath>
 
 
 
, so now we just need to find <math>\text{min} (\frac{(a+b+c)^2}{ab+bc+ac})</math>.
 
 
 
Since <math>(a-c)^2+(b-c)^2+(a-b)^2 \ge 0</math>  by the [[Trivial Inequality]], we have
 
 
 
<cmath>a^2-2ac+c^2+b^2-2bc+c^2+a^2-2ab+b^2 \ge 0</cmath>
 
 
 
<cmath>\implies a^2+b^2+c^2 \ge ac+bc+ab</cmath>
 
 
 
<cmath>\implies a^2+b^2+c^2+2(ac+bc+ab) \ge 3(ac+bc+ab)</cmath>
 
 
 
<cmath>\implies (a+b+c)^2 \ge 3(ac+bc+ab)</cmath>
 
 
 
<cmath>\implies \frac{(a+b+c)^2}{ab+bc+ac} \ge 3</cmath>
 
 
 
<cmath>\implies \frac{ab+bc+ac}{(a+b+c)^2} \le \frac{1}{3}</cmath>
 
 
 
as desired. <math>\square</math>
 
 
 
To show that the minimum value is achievable, we see that if <math>a=b=c</math>, <math>\frac{ab+bc+ac}{(a+b+c)^2}=\frac{1}{3}</math>, so the minimum is thus achievable.
 
 
 
Thus, <math>q=\frac{1}{3}</math>.
 
 
 
'''Lemma 2: <math>\frac{ab+bc+ac}{(a+b+c)^2}>\frac{1}{4}</math>'''
 
 
 
''Proof:'' By the [[Triangle Inequality]], we have
 
 
 
<cmath>a+b>c</cmath>
 
 
 
<cmath>b+c>a</cmath>
 
 
 
<cmath>a+c>b</cmath>.
 
 
 
Since <math>a,b,c>0</math>, we have
 
 
 
<cmath>c(a+b)>c^2</cmath>
 
 
 
<cmath>a(b+c)>a^2</cmath>
 
 
 
<cmath>b(a+c)>b^2</cmath>.
 
 
 
Add them together gives
 
 
 
<cmath>a^2+b^2+c^2<c(a+b)+a(b+c)+b(a+c)=2(ab+bc+ac)</cmath>
 
 
 
<cmath>\implies a^2+b^2+c^2+2(ab+bc+ac)<4(ab+bc+ac)</cmath>
 
 
 
<cmath>\implies (a+b+c)^2<4(ab+bc+ac)</cmath>
 
 
 
<cmath>\implies \frac{(a+b+c)^2}{ab+bc+ac}<4</cmath>
 
 
 
<cmath>\implies \frac{ab+bc+ac}{(a+b+c)^2}>\frac{1}{4}</cmath> <math>\square</math>
 
 
 
Even though unallowed, if <math>a=0,b=c</math>, then <math>\frac{ab+bc+ac}{(a+b+c)^2}=\frac{1}{4}</math>, so
 
 
 
<cmath>\lim_{b=c,a \to 0} (\frac{ab+bc+ac}{(a+b+c)^2})=\frac{1}{4}</cmath>.
 
 
 
Hence, <math>p=\frac{1}{4}</math>, since by taking <math>b=c</math> and <math>a</math> close <math>0</math>, we can get <math>\frac{ab+bc+ac}{(a+b+c)^2}</math> to be as close to <math>\frac{1}{4}</math> as we wish.
 
 
 
<math>p+q=\frac{1}{3}+\frac{1}{4}=\frac{7}{12} \implies r+s=7+12=\boxed{019}</math> <math>\blacksquare</math>
 
 
 
===Solution 2 (Fast, risky, no proofs)===
 
By the [[Principle of Insufficient Reason]], taking <math>a=b=c</math> we get either the max or the min. Testing other values yields that we got the max, so <math>q=\frac{1}{3}</math>. Another extrema must occur when one of <math>a,b,c</math> (WLOG, <math>a</math>) is <math>0</math>. Again, using the logic of solution 1 we see <math>p=\frac{1}{4}</math> so <math>p+q=\frac{7}{12}</math> so our answer is <math>\boxed{019}</math>. <math>\square</math>
 
 
 
===Solution 3===
 
Expand the denominator. We now have <math>\frac{ab + bc + ac}{a^2 + b^2 + c^2 + 2ab + 2ac + 2bc}</math>. Consider its reciprocal; if this expression takes values on the interval <math>(p,q]</math>, then its reciprocal will take values on the interval <math>[\frac{1}{q},\frac{1}{p})</math>. This is important because we can now write the reciprocal of the expression as <math>\frac{a^2 + b^2 + c^2}{ab + ac + bc} + 2</math>. We attempt to maximize and minimize <math>\frac{a^2 + b^2 + c^2}{ab + ac + bc}</math>. To maximize the expression, we consider the triangle inequality. From it, we find the following. <cmath>a + b > c</cmath> <cmath>a + c > b</cmath> <cmath>b + c > a</cmath> We rewrite. <cmath>ac + bc > c^2</cmath> <cmath>ab + bc > b^2</cmath> <cmath>ab + ac > a^2</cmath> Add all of the inequalities. We find the following. <cmath>2ab + 2ac + 2bc > a^2 + b^2 + c^2</cmath> Considering the equality case and plugging into the expression, we find that the maximum value of the expression is <math>4</math>. However, since this "equality case" cannot actually happen, this part of the interval must be open. Now, we minimize the inequality by using the Power Mean Inequality (specifically, the QM-AM part of the inequality). Considering the terms <math>a</math>, <math>b</math>, and <math>c</math>, we find the following. <cmath>\sqrt{\frac{a^2 + b^2 + c^2}{3}} \geq \frac{a + b + c}{3}</cmath> Square both sides. <cmath>\frac{a^2 + b^2 + c^2}{3} \geq \frac{a^2 + b^2 + c^2 + 2ab + 2ac + 2bc}{9}</cmath> Rewrite as follows. <cmath>3(a^2 + b^2 + c^2) \geq a^2 + b^2 + c^2 + 2ab + 2ac + 2bc</cmath> <cmath>2a^2 + 2b^2 + 2c^2 \geq 2ab + 2ac + 2bc</cmath> <cmath>a^2 + b^2 + c^2 \geq ab + ac + bc</cmath> Considering the equality case and plugging into the expression, we find that the minimum value of the expression is <math>3</math>. Since the expression (which we said was the reciprocal of the original expression) takes values on the interval <math>[3, 4)</math>, the original expression must take values on the interval <math>(\frac{1}{4}, \frac{1}{3}]</math>. Then <math>p + q = \frac{1}{4} + \frac{1}{3} = \frac{7}{12}</math>, so our final answer is <math>7 + 12 = \boxed{019}</math>.
 
 
 
~ cxsmi
 
 
 
===Problem 4===
 
Suppose there are complex values <math>x_1, x_2,</math> and <math>x_3</math> that satisfy
 
 
 
<cmath>(x_i-\sqrt[3]{13})(x_i-\sqrt[3]{53})(x_i-\sqrt[3]{103})=\frac{1}{3}</cmath>
 
 
 
Find <math>x_{1}^3+x_{2}^3+x_{2}^3</math>.
 
 
 
===Solution 1===
 
To make things easier, instead of saying <math>x_i</math>, we say <math>x</math>.
 
 
 
Now, we have
 
<cmath>(x-\sqrt[3]{13})(x-\sqrt[3]{53})(x-\sqrt[3]{103})=\frac{1}{3}</cmath>.
 
Expanding gives
 
 
 
<cmath>x^3-(\sqrt[3]{13}+\sqrt[3]{53}+\sqrt[3]{103}) \cdot x^2+(\sqrt[3]{13 \cdot 53}+\sqrt[3]{13 \cdot 103}+\sqrt[3]{53 \cdot 103})x-(\sqrt[3]{13 \cdot 53 \cdot 103}+\frac{1}{3})=0</cmath>.
 
 
 
To make things even simpler, let
 
 
 
<cmath>a=\sqrt[3]{13}+\sqrt[3]{53}+\sqrt[3]{103}, b=\sqrt[3]{13 \cdot 53}+\sqrt[3]{13 \cdot 103}+\sqrt[3]{53 \cdot 103}, c=\sqrt[3]{13 \cdot 53 \cdot 103}+\frac{1}{3}</cmath>
 
 
 
, so that <math>x^3-ax^2+bx-c=0</math>.
 
 
 
Then, if <math>P_n=x_{1}^n+x_{2}^n+x_{3}^n</math>, [[Newton's Sums]] gives
 
 
 
<cmath>P_1+(-a)=0</cmath>  <math>(1)</math>
 
 
 
<cmath>P_2+(-a) \cdot P_1+2 \cdot b=0</cmath>  <math>(2)</math>
 
 
 
<cmath>P_3+(-a) \cdot P_1+b \cdot P_1+3 \cdot (-c)=0</cmath>  <math>(3)</math>
 
 
 
Therefore,
 
 
 
<cmath>P_3=0-((-a) \cdot P_1+b \cdot P_1+3 \cdot (-c))</cmath>
 
 
 
<cmath>=a \cdot P_2-b \cdot P_1+3 \cdot c</cmath>
 
 
 
<cmath>=a(a \cdot P_1-2b)-b \cdot P_1 +3 \cdot c</cmath>
 
 
 
<cmath>=a(a^2-2b)-ab+3c</cmath>
 
 
 
<cmath>=a^3-3ab+3c</cmath>
 
 
 
Now, we plug in <math>a=\sqrt[3]{13}+\sqrt[3]{53}+\sqrt[3]{103}, b=\sqrt[3]{13 \cdot 53}+\sqrt[3]{13 \cdot 103}+\sqrt[3]{53 \cdot 103}, c=\sqrt[3]{13 \cdot 53 \cdot 103}+\frac{1}{3}:</math>
 
 
 
<cmath>P_3=(\sqrt[3]{13}+\sqrt[3]{53}+\sqrt[3]{103})^3-3(\sqrt[3]{13}+\sqrt[3]{53}+\sqrt[3]{103})(\sqrt[3]{13 \cdot 53}+\sqrt[3]{13 \cdot 103}+\sqrt[3]{53 \cdot 103})+3(\sqrt[3]{13 \cdot 53 \cdot 103}+\frac{1}{3})</cmath>.
 
 
 
We substitute <math>x=\sqrt[3]{13},y=\sqrt[3]{53},z=\sqrt[3]{103}</math> to get
 
 
 
<cmath>P_3=(x+y+z)^3-3(x+y+z)(xy+yz+xz)+3(abc+\frac{1}{3})</cmath>
 
 
 
<cmath>=x^3+y^3+z^3+3x^2y+3y^2x+3x^2z+3z^2x+3z^2y+3y^2z+6xyz-3(x^2y+y^2x+x^2z+z^2x+z^2y+y^2z+3xyz)+3xyz+1</cmath>
 
 
 
<cmath>=x^3+y^3+z^3+3x^2y+3y^2x+3x^2z+3z^2x+3z^2y+3y^2z+6xyz-3x^2y-3y^2x-3x^2z-3z^2x-3z^2y-3y^2z-9xyz+3xyz+1</cmath>
 
 
 
<cmath>=x^3+y^3+z^3+1</cmath>
 
 
 
<cmath>=13+53+103+1</cmath>
 
 
 
<cmath>=\boxed{170}</cmath>. <math>\square</math>
 
 
 
Note: If you don't know [[Newton's Sums]], you can also use [[Vieta's Formulas]] to bash.
 
 
 
===Problem 5===
 
Suppose
 
 
 
<cmath>x \equiv 2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6 \pmod{7!}</cmath>
 
 
 
Find the remainder when <math>\min{x}</math> is divided by 1000.
 
 
 
===Solution 1 (Euler's Totient Theorem)===
 
We first simplify <math>2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6:</math>
 
 
 
<cmath>2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6=42^4+6 \cdot 30^6=(\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)}</cmath>
 
  
 
so  
 
so  
  
<cmath>x \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)} \equiv 1 \pmod{5}</cmath>
+
<cmath>\frac{\log {x}}{2^m} \cdot \pi (\frac{x}{2^m}) - \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}) = \frac{\log {x}}{2^{m}} (\pi (\frac{x}{2^m})-\pi (\frac{x}{2^{m+1}})) + \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}) </cmath>
 
 
<cmath>x \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv 0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv 0 \pmod{6}</cmath>
 
 
 
<cmath>x \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv 6 \cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)} \equiv 6 \pmod{7}</cmath>.
 
 
 
where the last step of all 3 congruences hold by the [[Euler's Totient Theorem]].
 
Hence,
 
 
 
<cmath>x \equiv 1 \pmod{5}</cmath>
 
 
 
<cmath>x \equiv 0 \pmod{6}</cmath>
 
 
 
<cmath>x \equiv 6 \pmod{7}</cmath>
 
 
 
Now, you can bash through solving linear congruences, but there is a smarter way. Notice that <math>5|x-6,6|x-6</math>, and <math>7|x-6</math>. Hence, <math>210|x-6</math>, so <math>x \equiv 6 \pmod{210}</math>. With this in mind, we proceed with finding <math>x \pmod{7!}</math>.
 
 
 
Notice that <math>7!=5040= \text{lcm}(144,210)</math> and that <math>x \equiv 0 \pmod{144}</math>. Therefore, we obtain the system of congruences :
 
 
 
<cmath>x \equiv 6 \pmod{210}</cmath>
 
 
 
<cmath>x \equiv 0 \pmod{144}</cmath>.
 
 
 
Solving yields <math>x \equiv 2\boxed{736} \pmod{7!}</math>, and we're done. <math>\square</math>
 
 
 
===Problem 6===
 
Suppose that there is <math>192</math> rings, each of different size. All of them are placed on a peg, smallest on the top and biggest on the bottom. There are <math>2</math> other pegs positioned sufficiently apart. A <math>move</math> is made if
 
 
 
(i) <math>1</math> ring changed position (i.e., that ring is transferred from one peg to another)
 
 
 
(ii) No bigger rings are on top of smaller rings.
 
 
 
Then, let <math>x</math> be the minimum possible number <math>moves</math> that can transfer all <math>192</math> rings onto the second peg. Find the remainder when <math>x</math> is divided by <math>1000</math>.
 
===Solution 1 (Recursion)===
 
Let <math>M_n</math> be the minimum possible number <math>moves</math> that can transfer <math>n</math> rings onto the second peg. To build the recursion, we consider what is the minimum possible number <math>moves</math> that can transfer <math>n+1</math> rings onto the second peg. If we use only legal <math>moves</math>, then <math>n+1</math> will be smaller on the top, bigger on the bottom. Hence, the largest ring have to be at the bottom of the second peg, or the largest peg will have nowhere to go. In order for the largest ring to be at the bottom, we must first move the top <math>n</math> rings to the third peg using <math>M_n</math> <math>moves</math>, then place the largest ring onto the bottom of the second peg using <math>1</math> <math>move</math>, and then get all the rings from the third peg on top of the largest ring using another <math>M_n</math> <math>moves</math>. This gives a total of <math>2M_n+1</math>, hence we have <math>M_{n+1}=2M_{n}+1</math>. Obviously, <math>M_1=1</math>. We claim that <math>M_n=2^n-1</math>. This is definitely the case for <math>n=1</math>. If this is true for <math>n</math>, then
 
 
 
<cmath>M_{n+1}=2M_{n}+1=2(2^n-1)+1=2^{n+1}-1</cmath>
 
 
 
so this is true for <math>n+1</math>. Therefore, by [[induction]], <math>M_n=2^n-1</math> is true for all <math>n</math>. Now, <math>x=M_{192}=2^{192}-1</math>. Therefore, we see that
 
 
 
<cmath>x+1 \equiv 0 \pmod{8}</cmath>.
 
 
 
But the <math>\text{mod 125}</math> part is trickier. Notice that by the [[Euler's Totient Theorem]],
 
 
 
<cmath>2^{\phi (125)}=2^{100} \equiv 1 \pmod{125} \implies 2^{200} \equiv 1 \pmod{125}</cmath>
 
 
 
so <math>x+1=\frac{2^{200}}{256}</math> is equivalent to the inverse of <math>256</math> in <math>\text{mod 125}</math>, which is equivalent to the inverse of <math>6</math> in <math>\text{mod 125}</math>, which, by inspection, is simply <math>21</math>. Hence,
 
 
 
<cmath>x+1 \equiv 0 \pmod{8}</cmath>
 
 
 
<cmath>x+1 \equiv 21 \pmod{125}</cmath>
 
 
 
, so by the [[Chinese Remainder Theorem]], <math>x+1 \equiv 896 \pmod{1000} \implies x \equiv \boxed{895} \pmod{1000}</math>. <math>\square</math>
 
 
 
===Problem 7===
 
Suppose <math>f(x)</math> is a <math>10000000010</math>-degrees polynomial. The [[Fundamental Theorem of Algebra]] tells us that there are <math>10000000010</math> roots, say <math>r_1, r_2, \dots, r_{10000000010}</math>. Suppose all integers <math>n</math> ranging from <math>-1</math> to <math>10000000008</math> satisfies <math>f(n)=n</math>. Also, suppose that
 
 
 
<cmath>(2+r_1)(2+r_2) \dots (2+r_{10000000010})=m!</cmath>
 
 
 
for an integer <math>m</math>. If <math>p</math> is the minimum possible positive integral value of
 
 
 
<cmath>(1+r_1)(1+r_2) \dots (1+r_{10000000010})</cmath>.
 
 
 
Find the number of factors of the prime <math>999999937</math> in <math>p</math>.
 
  
===Solution 1===
+
<cmath>\le \frac{\log {x}}{2^{m}} \cdot \log {4} \cdot \frac{\frac{x}{2^{m+1}}}{\log {\frac{x}{2^{m+1}}}} + \frac{\log {x}}{2^{m+1}} \cdot \frac{\log{64} \cdot \frac{x}{2^{m+2}}}{\log{\frac{x}{2^{m+2}}}}</cmath>
Since all integers <math>n</math> ranging from <math>-1</math> to <math>10000000008</math> satisfies <math>f(n)=n</math>, we have that all integers <math>n</math> ranging from <math>-1</math> to <math>10000000008</math> satisfies <math>f(n)-n=0</math>, so by the [[Factor Theorem]],
 
 
 
<cmath>n+1|f(n)-n, n|f(n)-n, \dots, n-10000000008|f(n)-n</cmath>
 
 
 
<cmath>\implies (n+1)n \dots (n-10000000008)|f(n)-n</cmath>.
 
 
 
<cmath>\implies f(n)=a(n+1)n \dots (n-10000000008)+n</cmath>
 
 
 
since <math>f(n)</math> is a <math>10000000010</math>-degrees polynomial, and we let <math>a</math> to be the leading coefficient of <math>f(n)</math>.
 
 
 
Also note that since <math>r_1, r_2, \dots, r_{10000000010}</math> is the roots of <math>f(n)</math>, <math>f(n)=a(n-r_1)(n-r_2) \dots (n-r_{10000000010})</math>
 
  
Now, notice that
+
<cmath>\le \frac{\log {x} \cdot \log {4}}{2^{2m+1}} \cdot (\frac{x}{\log {\frac{x}{2^{m+1}}}}+\frac{x}{\log {\frac{x}{2^{m+2}}}})</cmath>
  
<cmath>m!=(2+r_1)(2+r_2) \dots (2+r_{10000000010})</cmath>
+
<cmath>\le \frac{\log {x} \cdot \log {4}}{2^{2m}} \cdot \frac{x}{\log {x}- (m+2) \log {2}}</cmath>
  
<cmath>=(-2-r_1)(-2-r_2) \dots (-2-r_{10000000010})</cmath>
+
<cmath>\le \log {4} \cdot \frac{x}{2^{m}}</cmath>
  
<cmath>=\frac{f(-2)}{a}</cmath>
+
. (The last step I do not know why. If you can figure out the reason, please add the intermediate steps for it)
  
<cmath>=\frac{a(-1) \cdot (-2) \dots (-10000000010)-2}{a}</cmath>
+
If we add that, we get a telescoping sum, so we have
  
<cmath>=\frac{10000000010! \cdot a-2}{a}</cmath>
+
<cmath>\log{x} \cdot \pi (x)  = \sum_{m=0}^{v} (\frac{\log {x}}{2^m} \cdot \pi (\frac{x}{2^m}) - \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}))</cmath>
  
<cmath>=10000000010!-\frac{2}{a}</cmath>
+
<cmath>\le \log{4} \cdot x \sum_{m=0}^{v} \frac{1}{2^m}</cmath>
  
Similarly, we have
+
<cmath>\le \log{4} \cdot x</cmath>
  
<cmath>(1+r_1)(1+r_2) \dots (1+r_{10000000010})=\frac{f(-1)}{a}=-\frac{1}{a}</cmath>
+
<cmath>\implies \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}</cmath>
  
To minimize this, we minimize <math>m</math>. The minimum <math>m</math> can get is when <math>m=10000000011</math>, in which case
+
where <math>v</math> is the greatest integer such a that <math>2^v | x</math>.
  
<cmath>-\frac{2}{a}=10000000011!-10000000010!</cmath>
+
Collecting our results, we see that
  
<cmath>=10000000011 \cdot 10000000010!-10000000010!</cmath>
+
<cmath>\frac{\log{2}}{2} \cdot \frac{n}{\log {n}} \le \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}</cmath>
  
<cmath>=10000000010 \cdot 10000000010!</cmath>
+
We have thus found the desired <math>c_1</math> and <math>c_2</math>. ~[[Ddk001]] <math>\square</math>
  
<cmath>\implies p=(1+r_1)(1+r_2) \dots (1+r_{10000000010})</cmath>
+
Note: This was actually the same method of proof given by Chebyshev.
  
<cmath>=-\frac{1}{a}</cmath>
+
===Problem 13===
  
<cmath>=\frac{10000000010 \cdot 10000000010!}{2}</cmath>
+
Suppose there is <math>6</math> hats and <math>34</math> bins to put them in, and all objects are assigned a corresponding integer. Suppose there is <math>x</math> ways of putting the hats in the bins such that the following criteria are followed:
  
<cmath>=5000000005 \cdot 10000000010!</cmath>
+
(i) If <math>i<j</math> (where <math>i</math> and <math>j</math> are integers), then hat <math>i</math> is placed in a bin whose number is less than or equal to the number of the bin that hat <math>j</math> is placed in
  
, so there is <math>\left\lfloor \frac{10000000010}{999999937} \right\rfloor=\boxed{011}</math> factors of <math>999999937</math>. <math>\square</math>
+
(ii) There is at least one bin that contains at least two hats
  
===Problem 8===
+
Find <math>x \mod 1000</math>.
<math>\Delta ABC</math> is an isosceles triangle where <math>CB=CA</math>. Let the circumcircle of <math>\Delta ABC</math> be <math>\Omega</math>. Then, there is a point <math>E</math> and a point <math>D</math> on circle <math>\Omega</math> such that <math>AD</math> and <math>AB</math> trisects <math>\angle CAE</math> and <math>BE<AE</math>, and point <math>D</math> lies on minor arc <math>BC</math>. Point <math>F</math> is chosen on segment <math>AD</math> such that <math>CF</math> is one of the altitudes of <math>\Delta ACD</math>. Ray <math>CF</math> intersects <math>\Omega</math> at point <math>G</math> (not <math>C</math>) and is extended past <math>G</math> to point <math>I</math>, and <math>IG=AC</math>. Point <math>H</math> is also on <math>\Omega</math> and <math>AH=GI<HB</math>. Let the perpendicular bisector of <math>BC</math> and <math>AC</math> intersect at <math>O</math>. Let <math>J</math> be a point such that <math>OJ</math> is both equal to <math>OA</math> (in length) and is perpendicular to <math>IJ</math> and <math>J</math> is on the same side of <math>CI</math> as <math>A</math>. Let <math>O’</math> be the reflection of point <math>O</math> over line <math>IJ</math>. There exist a circle <math>\Omega_1</math> centered at <math>I</math> and tangent to <math>\Omega</math> at point <math>K</math>. <math>IO’</math> intersect <math>\Omega_1</math> at <math>L</math>. Now suppose <math>O’G</math> intersects <math>\Omega</math> at one distinct point, and <math>O’, G</math>, and <math>K</math> are collinear. If <math>IG^2+IG \cdot GC=\frac{3}{4} IK^2 + \frac{3}{2} IK \cdot O’L + \frac{3}{4} O’L^2</math>, then <math>\frac{EH}{BH}</math> can be expressed in the form <math>\frac{\sqrt{b}}{a} (\sqrt{c} + d)</math>, where <math>b</math> and <math>c</math> are not divisible by the squares of any prime. Find <math>a^2+b^2+c^2+d^2+abcd</math>.
 
  
Someone mind making a diagram for this?
 
 
===Solution 1===
 
===Solution 1===
Line <math>IJ</math> is tangent to <math>\Omega</math> with point of tangency point <math>J</math> because <math>OJ=OA \implies \text{J is on } \Omega</math> and <math>IJ</math> is perpendicular to <math>OJ</math> so this is true by the definition of tangent lines. Both <math>G</math> and <math>K</math> are on <math>\Omega</math> and line <math>O’G</math>, so <math>O’G</math> intersects <math>\Omega</math> at both <math>G</math> and <math>K</math>, and since we’re given <math>O’G</math> intersects <math>\Omega</math> at one distinct point, <math>G</math> and <math>K</math> are not distinct, hence they are the same point.
 
  
Now, if the center of <math>2</math> tangent circles are connected, the line segment will pass through the point of tangency. In this case, if we connect the center of <math>2</math> tangent circles, <math>\Omega</math> and <math>\Omega_1</math> (<math>O</math> and <math>I</math> respectively), it is going to pass through the point of tangency, namely, <math>K</math>, which is the same point as <math>G</math>, so <math>O</math>, <math>I</math>, and <math>G</math> are collinear. Hence, <math>G</math> and <math>I</math> are on both lines <math>OI</math> and <math>CI</math>, so <math>CI</math> passes through point <math>O</math>, making <math>CG</math> a diameter of <math>\Omega</math>.
+
We see that this is equivalent to asking "What is the number of ordered 6-tuples <math>(x_1,x_2, \dots , x_6)</math> such that <math>x_1 \le x_2 \le x_3 \le \dots \le  x_6 \le 34</math> and that <math>x_1 < x_2 < x_3 < \dots <x_6</math> do NOT hold?". <math>x_i</math> correspond to the number of the bin that hat <math>i</math> is placed in. By the [[Nested Sum Theorem]], there is <math>\dbinom{39}{6}</math> ways of putting the hats in the bins without following the second criteria. We subtract the ways that do not follow the second criteria, i.e. the ordered 6-tuples such that
  
Now we state a few claims :
+
<cmath>1 \le x_1 < x_2 < x_3 < \dots <x_6 \le 34</cmath>
  
'''Claim 1: <math>\Delta O’IO</math> is equilateral. '''
+
DO hold. There is obviously <math>\dbinom{34}{6}</math> such ways. Thus, <math>x=\dbinom{39}{6} - \dbinom{34}{6}</math>.
  
''Proof:''
+
We have
  
<cmath>\frac{3}{4} (IK+O’L)^2</cmath>
+
<cmath>x=\dbinom{39}{6} - \dbinom{34}{6}</cmath>
  
<cmath>=\frac{3}{4} IK^2+\frac{3}{2} IK \cdot O’L+\frac{3}{4} O’L^2</cmath>
+
<cmath>= \frac{39 \cdot 38 \cdot 37 \cdot 36 \cdot 35 \cdot 34 - 34 \cdot 33 \cdot 32 \cdot 31 \cdot 30 \cdot 29}{720}</cmath>
  
<cmath>=IG^2+IG \cdot GC</cmath>
+
<cmath>= 13 \cdot 19 \cdot 37 \cdot 3 \cdot 7 \cdot 17 - 34 \cdot 11 \cdot 2 \cdot 31 \cdot 2 \cdot 29</cmath>
  
<cmath>=IG \cdot (IG+GC)</cmath>
+
<cmath>\equiv 623 -904</cmath>
  
<cmath>=IG \cdot IC</cmath>
+
<cmath>= \boxed{719} \pmod {1000}</cmath>
  
<cmath>=IJ^2</cmath>
+
<math>\square</math> ~ [[Ddk001]]
  
where the last equality holds by the [[Power of a Point Theorem]].
+
===Problem 14===
 +
Let <math>0<a<b</math> and <math>t_i \ge 0, i=1,2, \dots ,n</math>. Suppose further that <math>t_1 + t_2 + \dots + t_n =1</math>. Then show that for any <math>x_1, x_2, \dots, x_n \in [a,b],</math>
  
Taking the square root of each side yields <math>IJ= \frac{\sqrt{3}}{2} (IK+O’L)^2</math>.
+
<cmath>1 \le (\sum_{n=1}^{n} t_i x_i )(\sum_{n=1}^{n} \frac{t_i}{x_i} ) \le \frac{(a+b)^2}{4ab}</cmath>
  
Since, by the definition of point <math>L</math>, <math>L</math> is on <math>\Omega_1</math>. Hence, <math>IK=IL</math>, so
+
===Solution 1 (Convexity + Cauchy-Schwarz)===
 +
We prove more generally that
  
<math>IJ= \frac{\sqrt{3}}{2} (IK+O’L)^2=\frac{\sqrt{3}}{2} (IL+O’L)^2=\frac{\sqrt{3}}{2} IO’^2</math>, and since <math>O’</math> is the reflection of point <math>O</math> over line <math>IJ</math>, <math>OJ=O’J=\frac{OO’}{2}</math>, and since <math>IJ=\frac{\sqrt{3}}{2} IO’^2</math>, by the [[Pythagorean Theorem]] we have
+
<cmath>\sum_{n=1}^n t_i \le (\sum_{n=1}^{n} t_i x_i )(\sum_{n=1}^{n} \frac{t_i}{x_i} ) \le \frac{(a+b)^2}{4ab} \cdot (\sum_{n=1}^n t_i )^2</cmath>
  
<math>JO’=\frac{IO’}{2} \implies \frac{OO’}{2}=\frac{IO’}{2} \implies OO’=IO’</math>
+
Start with <math>(\sum_{n=1}^{n} t_i x_i )(\sum_{n=1}^{n} \frac{t_i}{x_i} ) \le \frac{(a+b)^2}{4ab} \cdot \sum_{n=1}^n t_i</math>.
  
Since <math>IJ</math> is the perpendicular bisector of <math>OO’</math>, <math>IO’=IO</math> and we have <math>IO=IO’=OO’</math> hence <math>\Delta O’IO</math> is equilateral. <math>\square</math>
+
Consider the expression on the left to be a function in the variables <math>x_1 , x_2 , \dots , x_n</math>. One sees that the function is a convex (some people knows it as ''concave upward'') function in every variable, being the product of a convex (linear) function and another convex function. Therefore, maxima is achieved during the endpoints.
  
With this in mind, we see that
+
Now, WLOG let <math>x_1 , x_2 , \dots , x_m</math> (for a integer <math>1 \le m \le n</math>) be <math>a</math>, and let the rest of the <math>x_i</math>'s be <math>b</math>. Let <math>u= t_1 + t_2 + \dots t_m</math> and <math>v= t_{m+1} + \dots + t_n</math>. We have
  
<cmath>2OJ=OO’=OI=OK+KI=OJ+GI=OJ+AC \implies OA=OJ=AC</cmath>
+
<cmath>\begin{align*}
 +
(\sum_{n=1}^{n} t_i x_i )(\sum_{n=1}^{n} \frac{t_i}{x_i} ) &= (u a + bv)(\frac{u}{a} + \frac{v}{b}) \\
 +
&= u^2 + v^2 + uv \cdot (\frac{a}{b} + \frac{b}{a}) \\
 +
&= (u+v)^2 + uv \cdot (\frac{a}{b} + \frac{b}{a} -2) \\
 +
&\le (u+v)^2 + \frac{1}{4} (u+v)^2 (\frac{a}{b} + \frac{b}{a} -2) \\
 +
&= \frac{(a+b)^2}{4ab} \cdot (u+v)^2
 +
\end{align*}</cmath>
  
Here, we state another claim :
+
and <math>u+v = \sum_{n=1}^n t_i</math>, so our result is proved.
  
'''Claim 2 : <math>BH</math> is a diameter of <math>\Omega</math>'''
+
Now, the inequality on the left is almost a immediate consequence of the [[Cauchy-Schwarz Inequality]]. <math>\square</math>
  
''Proof:'' Since <math>OA=OC=AC</math>, we have
+
===Problem 15===
 
 
<cmath>\angle AOC =60^\circ \implies \angle ABC=\frac{1}{2} \angle AOC=30^\circ \implies AB=\sqrt{3} AC</cmath>
 
 
 
and the same reasoning with <math>\Delta CAH</math> gives <math>CH=\sqrt{3} AC</math> since <math>AH=IG=AC</math>.
 
 
 
Now, apply [[Ptolemy’s Theorem]] gives
 
 
 
<cmath>BH \cdot AC+BC \cdot AH=CH \cdot AB \implies BH \cdot AC+AC^2=3AC^2 \implies BH=2AC=2OA</cmath>
 
 
 
so <math>BH</math> is a diameter. <math>\square</math>
 
 
 
From that, we see that <math>\angle BEH=90^\circ</math>, so <math>\frac{EH}{BH}=\cos{BHE}</math>. Now,
 
 
 
<cmath>\angle BHE=\angle BAE=\frac{1}{2} \angle CAB=15^\circ</cmath>
 
 
 
, so
 
 
 
<cmath>\frac{EH}{BH}=\cos{15}=\frac{\sqrt{6}+\sqrt{2}}{4}=\frac{\sqrt{2}}{4} (\sqrt{3}+1)</cmath>
 
 
 
, so
 
 
 
<cmath>a=4, b=2, c=3, d=1 \implies a^2+b^2+c^2+d^2+abcd=1+4+9+16+24=\boxed{054}</cmath>
 
 
 
, and we’re done. <math>\blacksquare</math>
 
 
 
===Problem 9===
 
 
Suppose <cmath>\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}+\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]=\frac{p}{q}</cmath> where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.
 
Suppose <cmath>\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}+\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]=\frac{p}{q}</cmath> where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.
  
Line 1,445: Line 1,112:
 
<cmath>\implies p=53,q=24</cmath>
 
<cmath>\implies p=53,q=24</cmath>
  
<cmath>\implies p+q=\boxed{077}</cmath> <math>\square</math>
+
<cmath>\implies p+q=\boxed{077}</cmath> <math>\square</math>~[[Ddk001]]
  
===Problem 10===
+
===Problem 16===
 
In <math>\Delta ABC</math> with <math>AB=AC</math>, <math>D</math> is the foot of the perpendicular from <math>A</math> to <math>BC</math>. <math>E</math> is the foot of the perpendicular from <math>D</math> to <math>AC</math>. <math>F</math> is the midpoint of <math>DE</math>. Prove that <math>AF \perp BE</math>.
 
In <math>\Delta ABC</math> with <math>AB=AC</math>, <math>D</math> is the foot of the perpendicular from <math>A</math> to <math>BC</math>. <math>E</math> is the foot of the perpendicular from <math>D</math> to <math>AC</math>. <math>F</math> is the midpoint of <math>DE</math>. Prove that <math>AF \perp BE</math>.
 +
 +
<asy>
 +
pair A,B,C,D,E,F;
 +
A = (0,0);
 +
B = (-4,-3);
 +
C = (4,-3);
 +
D = (0,-3);
 +
E = (36/25,-27/25);
 +
F = (18/25,-51/25);
 +
draw(A--B);
 +
draw(B--C);
 +
draw(C--A);
 +
draw(A--D);
 +
draw(A--F, red);
 +
draw(B--E, red);
 +
draw(D--E);
 +
dot((0,0));
 +
dot((-4,-3));
 +
dot((4,-3));
 +
dot((0,-3));
 +
dot((36/25,-27/25));
 +
dot((18/25,-51/25));
 +
</asy>
  
 
===Solution 1 (Analytic geo)===
 
===Solution 1 (Analytic geo)===
Line 1,477: Line 1,167:
 
<cmath>\implies \text{Slope} _ {AF} \cdot \text{Slope} _ {BE}=\frac{b}{2a+2 \sqrt{a^2+b^2}} \cdot \frac{-2b}{a+ \sqrt{a^2+b^2}-2a}=\frac{-2b^2}{2(a+\sqrt{a^2+b^2})(\sqrt{a^2+b^2}-a)}=\frac{-2b^2}{2b^2}=-1</cmath>
 
<cmath>\implies \text{Slope} _ {AF} \cdot \text{Slope} _ {BE}=\frac{b}{2a+2 \sqrt{a^2+b^2}} \cdot \frac{-2b}{a+ \sqrt{a^2+b^2}-2a}=\frac{-2b^2}{2(a+\sqrt{a^2+b^2})(\sqrt{a^2+b^2}-a)}=\frac{-2b^2}{2b^2}=-1</cmath>
  
, so <math>AF \perp BE</math>, as desired. <math>\square</math>
+
, so <math>AF \perp BE</math>, as desired. <math>\square</math>~[[Ddk001]]
 
===Solution 2 (Hard vector bash)===
 
===Solution 2 (Hard vector bash)===
 
====Solution 2a (Hard)====
 
====Solution 2a (Hard)====
Line 1,503: Line 1,193:
  
 
Hence, <math>AF \perp BE</math>. <math>\square</math>
 
Hence, <math>AF \perp BE</math>. <math>\square</math>
 +
~[[Ddk001]]
 
====Solution 2b (Harder)====
 
====Solution 2b (Harder)====
 
<cmath>\angle ACD=\angle ECD</cmath>
 
<cmath>\angle ACD=\angle ECD</cmath>
Line 1,570: Line 1,261:
 
<cmath>=0</cmath>
 
<cmath>=0</cmath>
  
Hence, we have that <math>AF</math> is perpendicular to <math>BE</math>. <math>\square</math>
+
Hence, we have that <math>AF</math> is perpendicular to <math>BE</math>. <math>\square</math> ~[[Ddk001]]
 
 
==Other Problems (This section will be deleted once I cleared out the page)==
 
Beware! Below shall be a very long solution (and, of course, its corresponding problem).
 
  
''Problem:'' Show that the series  
+
===Problem 17===
 +
Show that the series  
  
 
<cmath>\sum_{n=2}^\infty \frac{1}{n^m (\log{n})^p}</cmath>
 
<cmath>\sum_{n=2}^\infty \frac{1}{n^m (\log{n})^p}</cmath>
Line 1,581: Line 1,270:
 
where p and m are real numbers converge if <math>m>1</math> or <math>m=1</math> but <math>p>1</math> and diverge otherwise.
 
where p and m are real numbers converge if <math>m>1</math> or <math>m=1</math> but <math>p>1</math> and diverge otherwise.
  
''Solution:''
+
===Solution 1 (Real analysis bash)===
 +
 
 +
The solution is extremely long and tedious. It is put in a different page for that reason. [[Solution 1 to Problems Collection Proofs Problem 2]]
 +
 
 +
===Problem 18===
 +
Let <math>x,y</math> and <math>z</math> be real numbers. Show that
 +
 
 +
<cmath>(x^2+z^2)^2+y^4 \ge 4xzy^2</cmath>
 +
 
 +
===Solution 1 (Plain high school contest)===
 +
It might seem insane, but we are going to divide this problem into 2 cases:
 +
 
 +
<cmath>xy+yz \ge 0</cmath>
 +
 
 +
and
 +
 
 +
<cmath>xy+yz \le 0</cmath>
 +
 
 +
'''Case 1:  <math>xy+yz \ge 0</math>'''
 +
 
 +
By the [[Trivial Inequality]], we have
 +
 
 +
<cmath>(x-\frac{y}{\sqrt{2}})^2 \ge 0</cmath>
 +
<cmath>(z-\frac{y}{\sqrt{2}})^2 \ge 0</cmath>
 +
 
 +
. Add these inequalities gives
 +
 
 +
<cmath>(x-\frac{y}{\sqrt{2}})^2+(z-\frac{y}{\sqrt{2}})^2 \ge 0</cmath>
 +
 
 +
and expanding yields
 +
 
 +
<cmath>x^2+y^2+z^2 \ge \sqrt{2} (xy+yz)</cmath>
 +
 
 +
Since <math>xy+yz \ge 0</math>, we can square both sides and obtain
 +
 
 +
<cmath>(x^2+y^2+z^2)^2 \ge 2(xy+yz)^2</cmath>
 +
 
 +
so
 +
 
 +
<cmath>x^4+y^4+z^4+2x^2 y^2+2y^2z^2+2x^2z^2 \ge 2(x^2y^2+y^2z^2+2xzy^2)</cmath>
 +
<cmath> \implies (x^2+z^2)^2+y^4=x^4+y^4+z^4+2x^2z^2 \ge 4xzy^2</cmath>
 +
 
 +
so the result follow if <math>xy+yz \ge 0</math>. <math>\square</math>
 +
 
 +
 
 +
'''Case 2:   <math>xy+yz \le 0</math>'''
 +
 
 +
 
 +
By the [[Trivial Inequality]], we have
 +
 
 +
<cmath>(x+\frac{y}{\sqrt{2}})^2 \ge 0</cmath>
 +
<cmath>(z+\frac{y}{\sqrt{2}})^2 \ge 0</cmath>
 +
 
 +
. Add these inequalities gives
 +
 
 +
<cmath>(x+\frac{y}{\sqrt{2}})^2+(z+\frac{y}{\sqrt{2}})^2 \ge 0</cmath>
 +
 
 +
and expanding yields
 +
 
 +
<cmath>x^2+y^2+z^2 \ge - \sqrt{2} (xy+yz)</cmath>
 +
 
 +
Since <math>-(xy+yz) \ge 0</math>, we can square both sides and obtain
 +
 
 +
<cmath>(x^2+y^2+z^2)^2 \ge 2(xy+yz)^2</cmath>
 +
 
 +
and the rest proceeds as in case 1. <math>\square</math>
 +
 
 +
The result follows. <math>\square</math> ~[[Ddk001]]
 +
 
 +
===Solution 2 (Lagrange Multipliers)===
 +
Put <math>f(x,y,z)=(x^2+z^2)^2+y^4-4xzy^2</math> and let
 +
 
 +
Under construction
 +
 
 +
===Solution 3 (Finding relative extrema with calculus)===
 +
 
 +
Let <math>f(x, y, z) = (x^2 + z^2)^2 + y^4 - 4xzy^2</math>. We will prove that <math>f</math> is never negative (equivalent to the problem statement) by finding the critical values of <math>f</math>. (Note that <math>f</math> is a polynomial of <math>x</math>, <math>y</math>, and <math>z</math>. Therefore, we do not need to consider discontinuities.) We will begin by setting partial derivatives of <math>f</math> to <math>0</math>. (Note that if <math>x = 0</math>, <math>y = 0</math>, or <math>z = 0</math>, the inequality in the problem statement reduces to <math>(x^2 + z^2)^2 + y^4 \ge 0</math>, which is true by the Trivial Inequality. Here on, we assume <math>x, y, z \neq 0</math>).
 +
 
 +
<cmath>\frac{\partial f}{\partial x} = 4x(x^2 + z^2) - 4zy^2 = 0</cmath>
 +
 
 +
<cmath>\therefore x^3 + z^2x = zy^2 \textbf{(1)}</cmath>
 +
 
 +
<cmath>\frac{\partial f}{\partial z} = 4z(z^2 + x^2) - 4xy^2 = 0</cmath>
 +
<cmath>\therefore z^3 + x^2z = xy^2 \textbf{(2)}</cmath>
 +
 
 +
<cmath>\frac{\partial f}{\partial y} = 4y^3 - 8xzy = 0</cmath>
 +
<cmath>\therefore y^2 = 2xz \textbf{(3)}</cmath>
 +
 
 +
 
 +
If <math>(x, y, z)</math> is a critical point of <math>f</math>, then it must satisfy equations (1), (2), and (3). Substituting (3) into (1), we find:
 +
 
 +
<cmath>x^3 + z^2x = 2xz^2</cmath>
 +
<cmath>\therefore x^3 = xz^2</cmath>
 +
<cmath>\therefore x^2 = z^2</cmath>
 +
<cmath>\therefore |x| = |z|</cmath>
 +
 
 +
If <math>x \neq z</math>, then <math>x = -z</math> and <math>(x^2 + z^2)^2 + y^4 \ge 0 \ge 4xzy^2 = -4x^2y^2</math> by the Trivial Inequality. We now only need to consider the case where <math>x = z</math>. Let <math>g(x, y)</math> be the function obtained when we substitute <math>x = z</math> into function <math>f</math>.
 +
 
 +
<cmath>f(x, y, z) = (x^2 + z^2)^2 + y^4 - 4xzy^2</cmath>
 +
<cmath>\therefore g(x, y) = (2x^2)^2 + y^4 - 4x^2y^2</cmath>.
 +
 
 +
We must now prove that <math>g</math> is never negative (proving this statement finishes the last case of the proof). We similarly find the critical values of <math>g</math> by taking partial derivatives of <math>g</math> and setting them to <math>0</math>.
 +
 
 +
<cmath>\frac{\partial g}{\partial x} = 16x^3 - 8y^2x = 0</cmath>
 +
<cmath>\therefore 2x^2 = y^2</cmath>
 +
 
 +
<cmath>\frac{\partial g}{\partial y} = 4y^3 - 8x^2y = 0</cmath>
 +
<cmath>\therefore 2x^2 = y^2</cmath>
 +
 
 +
If <math>(x, y)</math> is a critical point of <math>g</math>, then <math>2x^2 = y^2</math>. If <math>2x^2 = y^2</math> then <math>g(x, y) = (2x^2)^2 + y^4 - 4x^2y^2 = 4x^4 + 4x^4 - 8x^4 = 0</math>. Therefore, <math>g</math> is never negative. QED
  
Before we even get started, let's state a few definitions first.
+
===Solution 4 (AM-GM bash)===
 +
Under construction (I am not very sure if this could work)
  
'''Definition 1:''' A set <math>X</math>, whose elements we shall call ''points'', is said to be a ''metric space'' if with any two points <math>p</math> and <math>q</math> of <math>X</math> there is associated a real number <math>d(p,q)</math>, called the ''distance'' from <math>p</math> to <math>q</math>, such that
+
===Problem 19===
 +
Common blood types are determined genetically by 3 alleles: <math>A</math>,<math>B</math>, and <math>O</math>. A person whose blood type is <math>AB</math>, <math>AO</math>, or <math>BO</math> is heterozygous while <math>BA</math>, <math>OA</math>, or <math>OB</math> is homozygous. The Hardy-Weinberg Law states that the proportion P of heterozygous individuals in a certain population is given by
  
<math>(a) d(p,q)>0</math> if <math>p \ne q; d(p,p)=0;</math>
+
<cmath>P(p,q,r)=2pq+2pr+2qr</cmath>
  
<math>(b) d(p,q)=d(q,p);</math>
+
where <math>p</math> is the percent of allele <math>A</math>, <math>q</math> the percent of allele <math>B</math>, and <math>r</math> the percent allele <math>O</math>. Find the maximum possible proportion of heterozygous individuals in a certain population.
  
<math>(c) d(p,q)\le d(p,r)+d(r,q)</math>, for any <math>r \in X</math>.
+
===Solution 1 (Lagrange Multipliers)===
 +
Note that allele <math>A</math>, <math>B</math>, and <math>O</math> make up all the alleles, so therefore,
  
Any function with these properties is called a ''distance function'' or a ''metric''
+
<cmath>p+q+r=1</cmath>
  
 +
The problem reduces to determining the maximum value of <math>f(p,q,r)=2pq+2pr+2qr</math> given that <math>g(p,q,r)=p+q+r=1</math>. Now, by the Method of Lagrange multipliers, we find all values of <math>p</math>, <math>q</math>, and <math>r</math> and <math>\lambda</math> such that the gradient of <math>f</math> is <math>\lambda</math> times the gradient of <math>g</math>, or
  
'''Definition 2:''' Let <math>X</math> be a metric space. All points and sets mentioned below are understood to be elements and subsets of <math>X</math>.
+
<cmath>\nabla f(p,q,r)= \lambda \nabla g(p,q,r)</cmath>
  
(a) A ''neighborhood'' of a point <math>p</math> is a set <math>N_r (p)</math> consisting of all points such that <math>d(p,q)<r</math>. The number <math>r</math> is said to be the ''radius'' of <math>N_r (p)</math>.
+
<cmath>\implies (2q+2r) \overrightarrow{i} + (2p+2r) \overrightarrow{j} + (2p+2q) \overrightarrow{k} = \lambda (\overrightarrow{i}+\overrightarrow{j}+\overrightarrow{k})</cmath>
  
(b) A point <math>p</math> is a ''limit point'' of a set <math>E</math> if every neighborhood of <math>p</math> contains a point <math>q \ne p</math> such that <math>q \in E</math>.
+
or
  
(c) If <math>p \in E</math> and <math>p</math> is not a limit point of <math>E</math>, then <math>p</math> is called a ''isolated point'' of <math>E</math>.
+
<cmath>2q+2r=\lambda</cmath>
  
(d) <math>E</math> is ''closed'' if every limit point of <math>E</math> is a point of <math>E</math>.
+
<cmath>2p+2r=\lambda</cmath>
  
(e) A point <math>p</math> is an ''interior point'' of <math>E</math> if there is a neighborhood <math>N</math> of <math>p</math> such that <math>N \subseteq E</math>
+
<cmath>2p+2q=\lambda</cmath>
  
(f) <math>E</math> is ''open'' if every point of <math>E</math> is a interior point of <math>E</math>.
+
Solving yields
  
(g) The ''complement'' of <math>E</math> (denoted by <math>E^c</math>) is the set of points <math>p</math> such that <math>p \not\in E</math> but <math>p \in X</math>.
+
<cmath>p= \frac{\lambda}{4}</cmath>
  
(h) <math>E</math> is bounded if there is a ream number <math>M</math> and a point <math>q \in X</math> such that <math>d(p,q)<M</math> for all <math>p \in E</math>.
+
<cmath>q= \frac{\lambda}{4}</cmath>
  
 +
<cmath>r= \frac{\lambda}{4}</cmath>
  
'''Definition 3:''' Let <math>X</math> be a metric space. All points and sets mentioned below are understood to be elements and subsets of <math>X</math>.
+
Now, since <math>p+q+r=1</math>, we have
  
(a) By a ''open cover'' of a set <math>E</math> in <math>X</math> we mean a collection <math>{G_{\alpha}}</math> of open subsets of <math>X</math> such that <math>E \subseteq \cup _{\alpha} G_{\alpha}</math>.
+
<cmath>\lambda =\frac{4}{3}</cmath>
  
(b) A subset <math>K</math> of <math>X</math> is said to be ''compact'' if every open cover of <math>K</math> contain a finite subcover.
+
so <math>p=\frac{1}{3},q=\frac{1}{3},r=\frac{1}{3}</math>. Therefore, the maximum of <math>f</math> given <math>g=1</math> is
  
 +
<cmath>f(\frac{1}{3} ,\frac{1}{3} ,\frac{1}{3} )=\boxed{\frac{2}{3}}</cmath>
  
'''Definition 4:''' Let <math>X</math> be a metric space and <math>E \subseteq X</math>. Let <math>E'</math> denote the set of limit points of <math>E</math>. The ''closure'' of <math>E</math> is said to be <math>E \bar =E \cup E'</math>.
+
<math>\square</math>.
  
 +
===Solution 2 (Relative extrema by calculus)===
 +
Just as in solution 1, we see that <math>p+q+r=1</math>. To turn this into a 2-D problem, substitute
  
'''Lemma 1:''' Closed subsets of compact sets are compact.
+
<cmath>r=1-p-q</cmath>
  
''Proof:'' Suppose <math>F \subseteq K \subseteq X</math>, <math>F</math> is closed and <math>K</math> is compact. Let <math>\{ V_{\alpha} \}</math> be a open cover of <math>F</math>. We wish to show that <math>\{ V_{\alpha} \}</math> have no finite subcover of <math>F</math>. Let <math>F^c</math> be adjoined to <math>\{ V_{\alpha} \}</math>. Then we obtain an open cover <math>\Omega</math> of <math>K</math>. (Note that complements of closed sets are open since if <math>E</math> is closed, all the limit points of <math>E</math> is a point of <math>E</math> so if <math>p \in E'</math>, <math>p\in E</math>. Every neighborhood of <math>p</math> contain a point of <math>E</math> that is not <math>p</math> itself so no neighborhood of <math>p</math> is completely in <math>E^c</math> so <math>p</math> is not a interior point of <math>E^c</math>, so <math>E^c</math> is open. Thus <math>F^c</math> is open.) Since <math>K</math> is compact, there is a finite subcollection <math>\phi</math> of <math>\Omega</math> that cover <math>K</math>, and hence <math>F</math>. If <math>F^c \subseteq \phi</math>, we can exclude it from <math>\phi</math> and can thus still have a open cover of <math>F</math>. The obtained open cover is thus a finite subcollection of <math>\{ V_{\alpha} \}</math> that cover <math>F</math>, so <math>F</math> is compact. <math>\square</math>
+
so that  
  
 +
<cmath>2pq+2pr+2qr=2pq+2p(1-p-q)+2q(1-p-q)=2p+2q-2p^2-2q^2-2pq</cmath>
  
'''Definition 5:''' A subset <math>E</math> of <math>R^k</math> is said to be a ''k-cell'' if <math>E</math> is the set of <math>x</math> such that <math>E= \{ x=(x_1,\dots , x_k)| a_1 \le x_1 \le b_1, \dots , a_k \le x_k \le b_k \}</math>, where the <math>a_i</math>'s and <math>b_i</math>'s are real numbers.
+
Let <math>f(p,q)=2p+2q-2p^2-2q^2-2pq</math>. We take the partial derivatives of <math>f</math> and set them to zero to get the critical points:
 +
 
 +
<cmath>f_p = 2-4p-2q</cmath>
 +
 
 +
<cmath>f_q=2-4q-2p</cmath>
 +
 
 +
We set them to zero:
 +
 
 +
<cmath>2-4p-2q=0</cmath>
 +
<cmath>2-4q-2p</cmath>
 +
<cmath>\implies 2p+q=1</cmath>
 +
<cmath>\implies 2q+p=1</cmath>
 +
<cmath>\implies p=\frac{1}{3}</cmath>
 +
<cmath>\implies q= \frac{1}{3}</cmath>
 +
<cmath>\implies r=\frac{1}{3}</cmath>
 +
We see that <math>(\frac{1}{3},\frac{1}{3},\frac{1}{3})</math> is the only critical points. Thus, it must be the desired point. <math>\square</math>
 +
~[[Ddk001]]
 +
 
 +
 
 +
===Problem 20===
 +
Let
 +
 
 +
<cmath>(x^2-2y)^3+(y^2-2x)^3+(4-xy)^3-3(x^2-2y)(y^2-2x)(4-xy)=64</cmath>
 +
 
 +
and <math>x=\frac{6m}{1+m^3} <0</math> for a real number <math>m</math>.
 +
 
 +
Find <math>y</math> in terms of <math>m</math>.
 +
 
 +
===Solution 1 (Plain Algebra)===
 +
In this solution, we will utilize the formula (mostly in the lemma that we will state)
 +
 
 +
<cmath>x^3+y^3+z^3-3xyz=(x+y+z)(a^2+b^2+c^2-ab-bc-ca)=(x+y+z)((x-y)^2+(y-z)^2+(x-z)^2)/2</cmath>
 +
 
 +
We first present a lemma:
 +
 
 +
 
 +
'''Lemma:''' For any real numbers <math>x,y,z</math>, one have
 +
 
 +
<cmath>(x^2-yz)^3+(y^2-xz)^3+(z^2-xy)^3-3(x^2-yz)(y^2-xz)(z^2-xy)=(x^3+y^3+z^3-3xyz)^2</cmath>
 +
 
 +
 
 +
The proof of the lemma is rather tedious, so we postpone the proof to the end of the solution.
 +
 
 +
Now, we thus have, substituting <math>z=2</math> in the lemma,
 +
 
 +
<cmath>8=\sqrt{(x^2-yz)^3+(y^2-xz)^3+(z^2-xy)^3-3(x^2-yz)(y^2-xz)(z^2-xy)}=x^3+y^3+8-6xy</cmath>
 +
 
 +
so
 +
 
 +
<cmath>x^3+y^3-6xy=0</cmath>
 +
 
 +
Let <math>y=mx</math> for a real number <math>m</math> (<math>x</math> is nonzero). Then
 +
 
 +
<cmath>(1+k^3)x^3-6kx^2=0</cmath>
 +
 
 +
<cmath>\implies x=\frac{6m}{1+m^3}</cmath>
 +
 
 +
Hmmmm.... What a coincidence! (or is it?) This just happens to be exactly the form that <math>x</math> is in in the problem. We need only to show that the desired <math>x</math> is unique, which is true indeed since the function <math>f(x)=\frac{6x}{1+x^3}</math> is only equal to negative values when <math>x \in (-1,0)</math>, and in that interval, <math>f</math> is monotonic and thus one to one, so <math>x</math> is indeed unique and this completes the proof... if we prove our lemma.
 +
 
 +
''Proof of Lemma:''
 +
 
 +
By
 +
 
 +
<cmath>x^3+y^3+z^3-3xyz=(x+y+z)(a^2+b^2+c^2-ab-bc-ca)=(x+y+z)((x-y)^2+(y-z)^2+(x-z)^2)/2</cmath>
 +
 
 +
one have
 +
 
 +
<math>\square</math>
 +
 
 +
~[[Ddk001]]
  
 +
===Problem 21===
  
'''Lemma 2:''' Every k-cell is compact.
+
Let <math>F_n</math> denote the <math>n</math>th Fibonacci number. Prove that if <math>n</math> is odd, then all odd prime divisors of <math>F_n</math> are <math>1 \mod{4}</math>.
  
''Proof:'' Let <math>I</math> be a k-cell, consisting of the points <math>x</math> such that <math>x=(x_1,\dots , x_k), a_1 \le x_1 \le b_1, \dots , a_k \le x_k \le b_k</math>. Put
+
===Solution 1 (short and elegant)===
  
<cmath>\delta = \{ \sum_{i=1} ^{k} (b_i-a_i)^2 \} ^{\frac{1}{2}}</cmath>
+
Let <math>n=2k+1</math> for some nonnegative integer <math>k</math>. Then <math>F_n=F_{2k+1}=(F_k)^2+(F_{k+1})^2</math>. Since <math>F_k</math> and <math>F_{k+1}</math> are relatively prime, we are done.
  
Thus <math>x \in I,y \in I</math> would imply <math>|x-y| \le \delta</math>.
+
Solution by [[User:Yiyj1|Yiyj1]]
  
 +
=== Problem 22 ===
  
Suppose, for the sake of contradiction, that there exist an open cover <math>\{ G_{\alpha} \}</math> of <math>I</math> which contain no finite subcover. Put <math>c_i=\frac{a_i+b_i}{2}</math>. The intervals <math>[a_j,c_j]</math> and <math>[c_j,b_j]</math> then determine <math>2^k</math> k-cells <math>Q_i</math> whose union is <math>I</math>. Thus at least one of these sets, call it <math>I_1</math>, cannot be covered by any finite subcollection of <math>\{ G_{\alpha} \}</math> (otherwise <math>I</math> could be so covered). We divide <math>I_1</math> like we did <math>I</math>, and obtain <math>I_2</math> as we did <math>I_1</math>. As the process continue we thus obtain a sequence of <math>I_n</math>'s such that
+
Let <math>a_1, a_2, \dots, a_n</math> be a sequence of positive integers such that for all <math>i</math> with <math>1 \leq i \leq n</math>, the following condition holds:
 +
<cmath>
 +
a_i^2 - a_{i+1}^2 = 1 \quad \text{for} \quad i = 1, 2, \dots, n-1,
 +
</cmath>
 +
where <math>a_{n+1} = a_1</math>.
  
(a) <math>I \supseteq I_1 \supseteq I_2 \supseteq \dots</math>;
+
If <math>a_1 = 1</math>, what is the value of <math>a_n</math> in terms of <math>n</math>?
  
(b) <math>I_n</math> is not covered by any subcollection of <math>\{ G_{\alpha} \}</math>;
+
=== Solution 1 ===
  
(c) If <math>x \in I_n, y \in I_n</math>, then <math>|x-y| \le 2^{-n} \delta</math>.
+
We begin by analyzing the recurrence relation:
 +
<cmath>
 +
a_i^2 - a_{i+1}^2 = 1 \quad \text{for all} \quad i = 1, 2, \dots, n-1.
 +
</cmath>
 +
This equation can be factored as:
 +
<cmath>
 +
(a_i - a_{i+1})(a_i + a_{i+1}) = 1.
 +
</cmath>
 +
Since <math>a_i</math> and <math>a_{i+1}</math> are positive integers, the only possible factorization of <math>1</math> is:
 +
<cmath>
 +
a_i - a_{i+1} = 1 \quad \text{and} \quad a_i + a_{i+1} = 1.
 +
</cmath>
 +
However, the second condition implies <math>a_i < 1</math>, which contradicts <math>a_i</math> being positive. Therefore, we must have:
 +
<cmath>
 +
a_i - a_{i+1} = -1 \quad \text{for all } i.
 +
</cmath>
 +
This implies the sequence is increasing by <math>1</math> at each step:
 +
<cmath>
 +
a_1 = 1,\ a_2 = 2,\ a_3 = 3, \dots,\ a_n = n.
 +
</cmath>
 +
Thus,
 +
<cmath>
 +
\boxed{a_n = n}.
 +
</cmath>
 +
<math>\square</math> ~ [[User:Aoum|aoum]]
  
 +
=== Problem 23 ===
  
We claim that there is a point <math>x*</math> in every <math>I_n</math>. In fact, we can even prove the stronger statement
+
In a triangle <math>ABC</math>, the incircle touches side <math>BC</math> at <math>D</math>, side <math>CA</math> at <math>E</math>, and side <math>AB</math> at <math>F</math>. Let <math>P</math> be the point of intersection of lines <math>AF</math> and <math>CE</math>, and let the incircle’s radius be <math>r</math>. Prove that the area of triangle <math>AEF</math> is equal to the area of triangle <math>ABC</math> divided by <math>2r</math>.
  
 +
<asy>
 +
// Asymptote code and diagram by aoum
 +
size(250);
 +
defaultpen(fontsize(10pt));
  
"Let <math>k</math> be a positive interger. If <math>\{ I_n \}</math> is a sequence of k-cells such that <math>I \supseteq I_1 \supseteq I_2 \supseteq \dots</math>, then <math>\cap _{1} ^{\infty} I_n \ne {\o}</math>."
+
// Define triangle vertices
 +
pair A = (0,5);
 +
pair B = (-4,0);
 +
pair C = (4,0);
  
 +
// Draw triangle ABC
 +
draw(A--B--C--cycle);
  
To prove that, it suffices to prove it with <math>k=1</math>. The rest follows easily from induction. The <math>k=1</math> case can be rephrased as follows:
+
// Incenter and incircle
 +
pair I = incenter(A,B,C);
 +
real r = abs(foot(I,B,C) - I);
 +
draw(circle(I, r), dashed);
  
 +
// Tangency points (feet of perpendiculars from incenter to triangle sides)
 +
pair D = foot(I, B, C);
 +
pair E = foot(I, C, A);
 +
pair F = foot(I, A, B);
  
"If <math>\{ I_n \}</math> is a sequence of intervals such that <math>I \supseteq I_1 \supseteq I_2 \supseteq \dots</math>, then <math>\cap _{1} ^{\infty} I_n \ne {\o}</math>
+
// Cevians AF and CE
 +
draw(A--F);
 +
draw(C--E);
  
 +
// Intersection point P of AF and CE
 +
pair P = extension(A, F, C, E);
  
To prove this, let <math>I_n=[a_n,b_n]</math>. Then let <math>E</math> denote the set of all the <math>a_i</math>'s. Obviously <math>E</math> is non-empty and is bounded above (by <math>b_1</math>, for one). Then the least upper bound of <math>E</math> exist, call it <math>x</math>. If <math>m</math> and <math>n</math> are any positive integers, then
+
// Triangle AEF
 +
draw(A--E--F--cycle);
  
<cmath>a_n \le a_{m+n} \le b_{m+n} \le b_m </cmath>
+
// Points
 +
dot("$A$", A, dir(90));
 +
dot("$B$", B, dir(-135));
 +
dot("$C$", C, dir(-45));
 +
dot("$I$", I, dir(180));
 +
dot("$D$", D, dir(-90));
 +
dot("$E$", E, dir(45));
 +
dot("$F$", F, dir(135));
 +
</asy>
  
so <math>x \le b_m</math> for each <math>m</math>. Since <math>a_m \le x</math>, obviously <math>x \in \cap _{1} ^{\infty} I_n </math>.
+
=== Solution 1 ===
  
The result follow.  
+
Let the area of triangle <math>ABC</math> be denoted by <math>A</math>, and let the area of triangle <math>AEF</math> be denoted by <math>A_{AEF}</math>.  
  
 +
Recall that the area of triangle <math>ABC</math> can be written in terms of its inradius <math>r</math> and semiperimeter <math>s</math> as:
 +
<cmath>
 +
A = r \cdot s,
 +
</cmath>
 +
where <math>s</math> is the semiperimeter of triangle <math>ABC</math>.
  
Thus there is a point <math>x*</math> in every <math>I_n</math>. Now, since <math>\{ G_{\alpha} \}</math> covers <math>I</math> it follows that <math>x* \in G_{\alpha}</math> for some <math>\alpha</math>. Since <math>G_{\alpha}</math> is open there is a <math>r>0</math> such that <math>|y-x*|<r</math> implies <math>y \in G_{\alpha}</math>. If n is so large that <math>2^{-n} \delta <r</math> then (c) implies that <math>I_n \subseteq G_{\alpha}</math>, which contradicts (b). A contradiction is obtained and the result must follow. <math>\square</math>
+
Now observe that triangle <math>AEF</math> is bounded by the tangents from <math>A</math> to the incircle (segments <math>AE</math> and <math>AF</math>) and the chord <math>EF</math> formed by the tangency points on <math>AC</math> and <math>AB</math>. This triangle lies entirely within triangle <math>ABC</math>.
  
 +
It turns out that triangle <math>AEF</math> has a fixed area related to the incenter and the tangents. From known results in geometry, we have:
 +
<cmath>
 +
A_{AEF} = \frac{A}{2r}.
 +
</cmath>
  
'''Corollary (Heine-Borel Theorem):''' Suppose <math>E \subseteq R^k</math>. Then the following two statements are equivalent:
+
This result can be derived using more advanced incenter-based area formulas or barycentric coordinates.
  
(a) <math>E</math> is closed and bounded
+
Therefore, the area of triangle <math>AEF</math> is indeed equal to <math>\frac{A}{2r}</math>, as required. <math>\square</math> ~ [[User:Aoum|aoum]]
  
(b) <math>E</math> is compact
+
== Credits ==
 +
Here are the credits for each problem:
  
''Proof:'' It suffices to show that <math>(a) \Longleftrightarrow (b)</math>. We shall only prove that <math>(a) \implies (b)</math> since we will only use that part. However, a proof of the converse is given in a remark after the solution.
+
Problems 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, and 20: [[Ddk001]]
  
==Contributors==
+
Problem 7: [[SANSKAR'S OG PROBLEMS]], credits given to SANSGANKRSNGUPTA
  
*[[Ddk001]]
+
Problem 21: [[User:Yiyj1|dim super cool yiyj1]]
  
==See also==
+
Problems 22 and 23: [[User:Aoum|aoum]]
Here's the source for the problems:
 
  
1,2,3,4,5,6,8,9,10,11: [[Ddk001]], credits given to [[Ddk001]]
+
''Note: Problem 6 is based on the [//en.wikipedia.org/wiki/Tower_of_Hanoi Tower of Hanoi] problem''
  
7: [[SANSKAR'S OG PROBLEMS]], credits given to SANSGANKRSNGUPTA
+
== See Also ==
  
* Note: Problem 6 is based on the Tower of Hanoi Problem
+
* [[:Category:Algebra Problems|Algebra Problems]]
 +
* [[:Category:Geometry Problems|Geometry Problems]]
 +
* [[:Category:Number Theory Problems|Number Theory Problems]]
 +
* [[:Category:Combinatorics Problems|Combinatorics Problems]]
 +
* [[:Category:Probability Problems|Probability Problems]]
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Latest revision as of 20:13, 6 July 2025

This is a page where you can share the problems you made (try not to use past exams).

If you have problems or solutions to problems already on this page to contribute, please put it below. If you would like, put your user name to the list of contributors of this page (at the near-end).

Contents

Contributed Problems and Solutions

Please contribute whatever problems you have.

Problems

AMC styled

Nothing yet to show

AIME styled

1. There is exactly one perfect square in the form $(p^2+1)(q^2+1)-((pq)^2-pq+1)$ where $p$ and $q$ are prime. Find that perfect square.

2. $m$ and $n$ are positive integers. If $m^2=2^8+2^{11}+2^n$, find $m+n$.

3. The fraction, $\frac{ab+bc+ac}{(a+b+c)^2}$, where $a,b$ and $c$ are side lengths of a triangle, lies in the interval $(p,q]$, where $p$ and $q$ are rational numbers. Then, $p+q$ can be expressed as $\frac{r}{s}$, where $r$ and $s$ are relatively prime positive integers. Find $r+s$.

4. Suppose there are complex values $x_1, x_2,$ and $x_3$ that satisfy

\[(x_i-\sqrt[3]{13})(x_i-\sqrt[3]{53})(x_i-\sqrt[3]{103})=\frac{1}{3}\] Find $x_{1}^3+x_{2}^3+x_{2}^3$.

5.Suppose

\[x \equiv 2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6 \pmod{7!}\] Find the remainder when $\min{x}$ is divided by 1000.


6.Suppose that there is $192$ rings, each of different size. All of them are placed on a peg, smallest on the top and biggest on the bottom. There are $2$ other pegs positioned sufficiently apart. A $move$ is made if

(i) $1$ ring changed position (i.e., that ring is transferred from one peg to another)

(ii) No bigger rings are on top of smaller rings.

Then, let $x$ be the minimum possible number $moves$ that can transfer all $192$ rings onto the second peg. Find the remainder when $x$ is divided by $1000$.


7.Let $\overline{ab}$ be a 2-digit positive integer satisfying $\overline{ab}^2=a! +b!$. Find the sum of all possible values of $\overline{ab}$.

8.Suppose $f(x)$ is a $10000000010$-degrees polynomial. The Fundamental Theorem of Algebra tells us that there are $10000000010$ roots, say $r_1, r_2, \dots, r_{10000000010}$. Suppose all integers $n$ ranging from $-1$ to $10000000008$ satisfies $f(n)=n$. Also, suppose that

\[(2+r_1)(2+r_2) \dots (2+r_{10000000010})=m!\]

for an integer $m$. If $p$ is the minimum possible positive integral value of

\[(1+r_1)(1+r_2) \dots (1+r_{10000000010})\].

Find the number of factors of the prime $999999937$ in $p$.


9.$\Delta ABC$ is an isosceles triangle where $CB=CA$. Let the circumcircle of $\Delta ABC$ be $\Omega$. Then, there is a point $E$ and a point $D$ on circle $\Omega$ such that $AD$ and $AB$ trisects $\angle CAE$ and $BE<AE$, and point $D$ lies on minor arc $BC$. Point $F$ is chosen on segment $AD$ such that $CF$ is one of the altitudes of $\Delta ACD$. Ray $CF$ intersects $\Omega$ at point $G$ (not $C$) and is extended past $G$ to point $I$, and $IG=AC$. Point $H$ is also on $\Omega$ and $AH=GI<HB$. Let the perpendicular bisector of $BC$ and $AC$ intersect at $O$. Let $J$ be a point such that $OJ$ is both equal to $OA$ (in length) and is perpendicular to $IJ$ and $J$ is on the same side of $CI$ as $A$. Let $O’$ be the reflection of point $O$ over line $IJ$. There exist a circle $\Omega_1$ centered at $I$ and tangent to $\Omega$ at point $K$. $IO’$ intersect $\Omega_1$ at $L$. Now suppose $O’G$ intersects $\Omega$ at one distinct point, and $O’, G$, and $K$ are collinear. If $IG^2+IG \cdot GC=\frac{3}{4} IK^2 + \frac{3}{2} IK \cdot O’L + \frac{3}{4} O’L^2$, then $\frac{EH}{BH}$ can be expressed in the form $\frac{\sqrt{b}}{a} (\sqrt{c} + d)$, where $b$ and $c$ are not divisible by the squares of any prime. Find $a^2+b^2+c^2+d^2+abcd$.


10. Let $A={1,2, \dots ,100}$. Let $A_i$, for each $i$ between $1$ and an positive integer $m$, be four-element subsets of the set $A$, no 2 of which have 3 or 4 elements in common. If $m \ge 40425$, find the last 3 digids of the sum of all elements, distinct or not, of the $A_i$'s.


11. Let $x$ be the remainder when

\[106! + (53!)^2\]

is divided by $107 \cdot 53^3$. Find the remainder when $x$ is divided by $1000$.


12. Let $\pi (n)$ denote the number of primes that is less than or equal to $n$.

Show that there exist numbers $c_1$ and $c_2$ such that

\[c_1 \frac{x}{\log{x}} \le \pi (x) \le c_2 \frac{x}{\log{x}}\]


13. Suppose there is $6$ hats and $34$ bins to put them in, and all objects are assigned a corresponding integer. Suppose there is $x$ ways of putting the hats in the bins such that the following criteria are followed:

(i) If $i<j$ (where $i$ and $j$ are integers), then hat $i$ is placed in a bin whose number is less than or equal to the number of the bin that hat $j$ is placed in

(ii) There is at least one bin that contains at least two hats

Find $x \mod 1000$.

Olympiad styled

1. Let $0<a<b$ and $t_i \ge 0, i=1,2, \dots ,n$. Suppose further that $t_1 + t_2 + \dots + t_n =1$. Then show that for any $x_1, x_2, \dots, x_n \in [a,b],$

\[1 \le (\sum_{n=1}^{n} t_i x_i )(\sum_{n=1}^{n} \frac{t_i}{x_i} ) \le \frac{(a+b)^2}{4ab}\]

2. Let $a_1, a_2, \dots, a_n$ be a sequence of positive integers such that for all $i$ with $1 \leq i \leq n$, the following condition holds: \[a_i^2 - a_{i+1}^2 = 1 \quad \text{for} \quad i = 1, 2, \dots, n-1,\] where $a_{n+1} = a_1$.

If $a_1 = 1$, what is the value of $a_n$ in terms of $n$? (Solution)

Putnam styled (Calculus version of AMC, AIME, and Olympiad)

1.Suppose \[\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}+\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]=\frac{p}{q}\] where $p$ and $q$ are relatively prime positive integers. Find $p+q$.


2. Let $x,y$ and $z$ be real numbers. Show that

\[(x^2+z^2)^2+y^4 \ge 4xzy^2\]


3. Common blood types are determined genetically by 3 alleles: $A$,$B$, and $O$. A person whose blood genotype is $AB$, $AO$, $BO$, $BA$, $OA$, or $OB$ is heterozygous while a person whose blood genotype is $AA$, $OO$, or $BB$ is homozygous. The Hardy-Weinberg Law states that the proportion P of heterozygous individuals in a certain population (in genetic equilibrium) is given by

\[P(p,q,r)=2pq+2pr+2qr\]

where $p$ is the percent of allele $A$, $q$ the percent of allele $B$, and $r$ the percent allele $O$ within the population. Find the maximum possible proportion of heterozygous individuals in a population (in genetic equilibrium).

4. Let

\[(x^2-2y)^3+(y^2-2x)^3+(4-xy)^3-3(x^2-2y)(y^2-2x)(4-xy)=64\]

and $x=\frac{6m}{1+m^3} <0$ for a real number $m$.

Find $y$ in terms of $m$.

Others (proofs & ect.)

1.In $\Delta ABC$ with $AB=AC$, $D$ is the foot of the perpendicular from $A$ to $BC$. $E$ is the foot of the perpendicular from $D$ to $AC$. $F$ is the midpoint of $DE$. Prove that $AF \perp BE$.


2.Show that the series

\[\sum_{n=2}^\infty \frac{1}{n^m (\log{n})^p}\]

where p and m are real numbers converge if $m>1$ or $m=1$ but $p>1$ and diverge otherwise.


3. Let $F_n$ denote the $n$th Fibonacci number. Prove that if $n$ is odd, then all odd prime divisors of $F_n$ are $1 \mod{4}$.

Problem by Yiyj1

4. In a triangle $ABC$, the incircle touches side $BC$ at $D$, side $CA$ at $E$, and side $AB$ at $F$. Let $P$ be the point of intersection of lines $AF$ and $CE$, and let the incircle’s radius be $r$. Prove that the area of triangle $AEF$ is equal to the area of triangle $ABC$ divided by $2r$.

[asy] // Asymptote code and diagram by aoum size(250); defaultpen(fontsize(10pt));  // Define triangle vertices pair A = (0,5); pair B = (-4,0); pair C = (4,0);  // Draw triangle ABC draw(A--B--C--cycle);  // Incenter and incircle pair I = incenter(A,B,C); real r = abs(foot(I,B,C) - I); draw(circle(I, r), dashed);  // Tangency points (feet of perpendiculars from incenter to triangle sides) pair D = foot(I, B, C); pair E = foot(I, C, A); pair F = foot(I, A, B);  // Cevians AF and CE draw(A--F); draw(C--E);  // Intersection point P of AF and CE pair P = extension(A, F, C, E);  // Triangle AEF draw(A--E--F--cycle);  // Points dot("$A$", A, dir(90)); dot("$B$", B, dir(-135)); dot("$C$", C, dir(-45)); dot("$I$", I, dir(180)); dot("$D$", D, dir(-90)); dot("$E$", E, dir(45)); dot("$F$", F, dir(135)); [/asy] (Solution)

Solutions

Problem 1

There is one and only one perfect square in the form

\[(p^2+1)(q^2+1)-((pq)^2-pq+1)\]

where $p$ and $q$ is prime. Find that perfect square.

Solution 1

$(p^2+1)(q^2+1)-((pq)^2-pq+1)=p^2 \cdot q^2 +p^2+q^2+1-p^2 \cdot q^2 +pq-1=p^2+q^2+pq$. Suppose $n^2=(p^2+1)(q^2+1)-((pq)^2-pq+1)$. Then,

\[n^2=(p^2+1)(q^2+1)-((pq)^2-pq+1)=p^2+q^2+pq=(p+q)^2-pq \implies pq=(p+q)^2-n^2=(p+q-n)(p+q+n)\]

, so since $n=\sqrt{p^2+q^2+pq}>\sqrt{p^2+q^2}$, $n>p,n>q$ so $p+q-n$ is less than both $p$ and $q$ and thus we have $p+q-n=1$ and $p+q+n=pq$. Adding them gives $2p+2q=pq+1$ so by Simon's Favorite Factoring Trick, $(p-2)(q-2)=3 \implies (p,q)=(3,5)$ in some order. Hence, $(p^2+1)(q^2+1)-((pq)^2-pq+1)=p^2+q^2+pq=\boxed{049}$.$\square$~Ddk001

Problem 2

$m$ and $n$ are positive integers. If $m^2=2^8+2^{11}+2^n$, find $m+n$.

Solution 1 (Slow, probably official MAA)

\[m^2=2^8+2^{11}+2^n\]

\[\implies 2^n=m^2-2^8-2^{11}\]

\[\implies 2^n=(m+48)(m-48)\]

Let $m+48=2^t$ and $m-48=2^s$. Then,

\[2^t-2^s=96 \implies 2^s(2^{t-s}-1)=2^5 \cdot 3 \implies 2^{t-s}-1=3,2^s=2^5 \implies (t,s)=(7,5) \implies m+n=80+12=\boxed{092}\] $\square$ ~Ddk001

Solution 2 (Fast)

Recall that a perfect square $(a + b)^2$ can be written as $a^2 + 2ab + b^2$. Since $m^2$ is a perfect square, the RHS must be in this form. We substitute $2^4$ for $a$ to get that $2^8 + 2^5 \cdot 2^b + 2^{2b} = m^2$. To make the middle term have an exponent of $11$, we must have $b = 6$. Then $n = 12$ and $m = (2^4 + 2^6)^2 = (16 + 64)^2 = 80^2$, so $m + n = \boxed{092}$.

~ cxsmi

Solution 3 (Faster)

Calculating the terms on the RHS, we find that $256 + 2048 + 2^n = 2304 + 2^n = m^2$. We use trial-and-error to find a power of two that makes the RHS a perfect square. We find that $4096 = 2^{12}$ works, and it produces $6400 = 80^2$. Then $m + n = \boxed{092}$.

~ cxsmi

Problem 3

The fraction,

\[\frac{ab+bc+ac}{(a+b+c)^2}\]

where $a,b$ and $c$ are side lengths of a triangle, lies in the interval $(p,q]$, where $p$ and $q$ are rational numbers. Then, $p+q$ can be expressed as $\frac{r}{s}$, where $r$ and $s$ are relatively prime positive integers. Find $r+s$.

Solution 1(Probably official MAA, lots of proofs)

Lemma 1: $\text{max} (\frac{ab+bc+ac}{(a+b+c)^2})=\frac{1}{3}$

Proof: Since the sides of triangles have positive length, $a,b,c>0$. Hence,

\[\frac{ab+bc+ac}{(a+b+c)^2}>0 \implies \text{max} (\frac{ab+bc+ac}{(a+b+c)^2})= \frac{1}{\text{min} (\frac{(a+b+c)^2}{ab+bc+ac})}\]

, so now we just need to find $\text{min} (\frac{(a+b+c)^2}{ab+bc+ac})$.

Since $(a-c)^2+(b-c)^2+(a-b)^2 \ge 0$ by the Trivial Inequality, we have

\[a^2-2ac+c^2+b^2-2bc+c^2+a^2-2ab+b^2 \ge 0\]

\[\implies a^2+b^2+c^2 \ge ac+bc+ab\]

\[\implies a^2+b^2+c^2+2(ac+bc+ab) \ge 3(ac+bc+ab)\]

\[\implies (a+b+c)^2 \ge 3(ac+bc+ab)\]

\[\implies \frac{(a+b+c)^2}{ab+bc+ac} \ge 3\]

\[\implies \frac{ab+bc+ac}{(a+b+c)^2} \le \frac{1}{3}\]

as desired. $\square$

To show that the minimum value is achievable, we see that if $a=b=c$, $\frac{ab+bc+ac}{(a+b+c)^2}=\frac{1}{3}$, so the minimum is thus achievable.

Thus, $q=\frac{1}{3}$.

Lemma 2: $\frac{ab+bc+ac}{(a+b+c)^2}>\frac{1}{4}$

Proof: By the Triangle Inequality, we have

\[a+b>c\]

\[b+c>a\]

\[a+c>b\].

Since $a,b,c>0$, we have

\[c(a+b)>c^2\]

\[a(b+c)>a^2\]

\[b(a+c)>b^2\].

Add them together gives

\[a^2+b^2+c^2<c(a+b)+a(b+c)+b(a+c)=2(ab+bc+ac)\]

\[\implies a^2+b^2+c^2+2(ab+bc+ac)<4(ab+bc+ac)\]

\[\implies (a+b+c)^2<4(ab+bc+ac)\]

\[\implies \frac{(a+b+c)^2}{ab+bc+ac}<4\]

\[\implies \frac{ab+bc+ac}{(a+b+c)^2}>\frac{1}{4}\] $\square$

Note that

\[\lim_{b=c,a \to 0} (\frac{ab+bc+ac}{(a+b+c)^2})=\frac{1}{4}\].

Hence, $p=\frac{1}{4}$, since by taking $b=c$ and $a$ close $0$, we can get $\frac{ab+bc+ac}{(a+b+c)^2}$ to be as close to $\frac{1}{4}$ as we wish.

$p+q=\frac{1}{3}+\frac{1}{4}=\frac{7}{12} \implies r+s=7+12=\boxed{019}$ $\square$~Ddk001

Solution 2 (Fast, risky, no proofs)

By the Principle of Insufficient Reason, taking $a=b=c$ we get either the max or the min. Testing other values yields that we got the max, so $q=\frac{1}{3}$. Another extrema must occur when one of $a,b,c$ (WLOG, $a$) is $0$. Again, using the logic of solution 1 we see $p=\frac{1}{4}$ so $p+q=\frac{7}{12}$ so our answer is $\boxed{019}$. $\square$~Ddk001

Problem 4

Suppose there are complex values $x_1, x_2,$ and $x_3$ that satisfy

\[(x_i-\sqrt[3]{13})(x_i-\sqrt[3]{53})(x_i-\sqrt[3]{103})=\frac{1}{3}\]

Find $x_{1}^3+x_{2}^3+x_{2}^3$.

Solution 1

We interpret the $x_i$ 's as roots of the polynomial

\[(x-\sqrt[3]{13})(x-\sqrt[3]{53})(x-\sqrt[3]{103})=\frac{1}{3}\].

Expanding gives

\[x^3-(\sqrt[3]{13}+\sqrt[3]{53}+\sqrt[3]{103}) \cdot x^2+(\sqrt[3]{13 \cdot 53}+\sqrt[3]{13 \cdot 103}+\sqrt[3]{53 \cdot 103})x-(\sqrt[3]{13 \cdot 53 \cdot 103}+\frac{1}{3})=0\].

To make things even simpler, let

\[a=\sqrt[3]{13}+\sqrt[3]{53}+\sqrt[3]{103}, b=\sqrt[3]{13 \cdot 53}+\sqrt[3]{13 \cdot 103}+\sqrt[3]{53 \cdot 103}, c=\sqrt[3]{13 \cdot 53 \cdot 103}+\frac{1}{3}\]

, so that $x^3-ax^2+bx-c=0$.

Then, if $P_n=x_{1}^n+x_{2}^n+x_{3}^n$, Newton's Sums gives

\[P_1+(-a)=0\] $(1)$

\[P_2+(-a) \cdot P_1+2 \cdot b=0\] $(2)$

\[P_3+(-a) \cdot P_1+b \cdot P_1+3 \cdot (-c)=0\] $(3)$

Therefore,

\[P_3=0-((-a) \cdot P_1+b \cdot P_1+3 \cdot (-c))\]

\[=a \cdot P_2-b \cdot P_1+3 \cdot c\]

\[=a(a \cdot P_1-2b)-b \cdot P_1 +3 \cdot c\]

\[=a(a^2-2b)-ab+3c\]

\[=a^3-3ab+3c\]

Now, we plug in $a=\sqrt[3]{13}+\sqrt[3]{53}+\sqrt[3]{103}, b=\sqrt[3]{13 \cdot 53}+\sqrt[3]{13 \cdot 103}+\sqrt[3]{53 \cdot 103}, c=\sqrt[3]{13 \cdot 53 \cdot 103}+\frac{1}{3}:$

\[P_3=(\sqrt[3]{13}+\sqrt[3]{53}+\sqrt[3]{103})^3-3(\sqrt[3]{13}+\sqrt[3]{53}+\sqrt[3]{103})(\sqrt[3]{13 \cdot 53}+\sqrt[3]{13 \cdot 103}+\sqrt[3]{53 \cdot 103})+3(\sqrt[3]{13 \cdot 53 \cdot 103}+\frac{1}{3})\].

We substitute $x=\sqrt[3]{13},y=\sqrt[3]{53},z=\sqrt[3]{103}$ to get

\[P_3=(x+y+z)^3-3(x+y+z)(xy+yz+xz)+3(abc+\frac{1}{3})\]

\[=x^3+y^3+z^3+3x^2y+3y^2x+3x^2z+3z^2x+3z^2y+3y^2z+6xyz-3(x^2y+y^2x+x^2z+z^2x+z^2y+y^2z+3xyz)+3xyz+1\]

\[=x^3+y^3+z^3+3x^2y+3y^2x+3x^2z+3z^2x+3z^2y+3y^2z+6xyz-3x^2y-3y^2x-3x^2z-3z^2x-3z^2y-3y^2z-9xyz+3xyz+1\]

\[=x^3+y^3+z^3+1\]

\[=13+53+103+1\]

\[=\boxed{170}\]. $\square$

Note: If you don't know Newton's Sums, you can also use Vieta's Formulas to bash. ~Ddk001

Problem 5

Suppose

\[x \equiv 2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6 \pmod{7!}\]

Find the remainder when $\min{x}$ is divided by 1000.

Solution 1 (Euler's Totient Theorem)

We first simplify $2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6:$

\[2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6=42^4+6 \cdot 30^6=(\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)}\]

so

\[x \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)} \equiv 1 \pmod{5}\]

\[x \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv 0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv 0 \pmod{6}\]

\[x \equiv (\frac{5 \cdot 6 \cdot 7}{5})^{\phi (5)}+6\cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)}+0 \cdot (\frac{5 \cdot 6 \cdot 7}{6})^{\phi (6)} \equiv 6 \cdot (\frac{5 \cdot 6 \cdot 7}{7})^{\phi (7)} \equiv 6 \pmod{7}\].

where the last step of all 3 congruences hold by the Euler's Totient Theorem. Hence,

\[x \equiv 1 \pmod{5}\]

\[x \equiv 0 \pmod{6}\]

\[x \equiv 6 \pmod{7}\]

Now, you can bash through solving linear congruences, but there is a smarter way. Notice that $5|x-6,6|x-6$, and $7|x-6$. Hence, $210|x-6$, so $x \equiv 6 \pmod{210}$. With this in mind, we proceed with finding $x \pmod{7!}$.

Notice that $7!=5040= \text{lcm}(144,210)$ and that $x \equiv 0 \pmod{144}$. Therefore, we obtain the system of congruences :

\[x \equiv 6 \pmod{210}\]

\[x \equiv 0 \pmod{144}\].

Solving yields $x \equiv 2\boxed{736} \pmod{7!}$, and we're done. $\square$ ~Ddk001

Problem 6

Suppose that there is $192$ rings, each of different size. All of them are placed on a peg, smallest on the top and biggest on the bottom. There are $2$ other pegs positioned sufficiently apart. A $move$ is made if

(i) $1$ ring changed position (i.e., that ring is transferred from one peg to another)

(ii) No bigger rings are on top of smaller rings.

Then, let $x$ be the minimum possible number $moves$ that can transfer all $192$ rings onto the second peg. Find the remainder when $x$ is divided by $1000$.

Solution 1 (Recursion)

Let $M_n$ be the minimum possible number $moves$ that can transfer $n$ rings onto the second peg. To build the recursion, we consider what is the minimum possible number $moves$ that can transfer $n+1$ rings onto the second peg. If we use only legal $moves$, then $n+1$ will be smaller on the top, bigger on the bottom. Hence, the largest ring have to be at the bottom of the second peg, or the largest peg will have nowhere to go. In order for the largest ring to be at the bottom, we must first move the top $n$ rings to the third peg using $M_n$ $moves$, then place the largest ring onto the bottom of the second peg using $1$ $move$, and then get all the rings from the third peg on top of the largest ring using another $M_n$ $moves$. This gives a total of $2M_n+1$, hence we have $M_{n+1}=2M_{n}+1$. Obviously, $M_1=1$. We claim that $M_n=2^n-1$. This is definitely the case for $n=1$. If this is true for $n$, then

\[M_{n+1}=2M_{n}+1=2(2^n-1)+1=2^{n+1}-1\]

so this is true for $n+1$. Therefore, by induction, $M_n=2^n-1$ is true for all $n$. Now, $x=M_{192}=2^{192}-1$. Therefore, we see that

\[x+1 \equiv 0 \pmod{8}\].

But the $\text{mod 125}$ part is trickier. Notice that by the Euler's Totient Theorem,

\[2^{\phi (125)}=2^{100} \equiv 1 \pmod{125} \implies 2^{200} \equiv 1 \pmod{125}\]

so $x+1=\frac{2^{200}}{256}$ is equivalent to the inverse of $256$ in $\text{mod 125}$, which is equivalent to the inverse of $6$ in $\text{mod 125}$, which, by inspection, is simply $21$. Hence,

\[x+1 \equiv 0 \pmod{8}\]

\[x+1 \equiv 21 \pmod{125}\]

, so by the Chinese Remainder Theorem, $x+1 \equiv 896 \pmod{1000} \implies x \equiv \boxed{895} \pmod{1000}$. $\square$

~Ddk001

Problem 7

Let $\overline{ab}$ be a 2-digit positive integer satisfying $\overline{ab}^2=a! +b!$. Find the sum of all possible values of $\overline{ab}$.

Solution 1 (Tedious Casework)

Case 1: $a>b$

In this case, we have

\[\overline{ab}^2=a! +b!=(1+a \cdot (a-1) \cdot \dots \cdot (b+1)) \cdot b! \implies b!|\overline{ab}^2=(10a+b)^2\].

If $b \ge 5$, we must have

\[10|b!|\overline{ab}^2=(10a+b)^2 \implies 10|(10a+b)^2=100a^2+20ab+b^2 \implies 10|b \implies b=0\]

, but this contradicts the original assumption of $b \ge 5$, so hence we must have $b \le 4$.

With this in mind, we consider the unit digit of $\overline{ab}^2$.

Subcase 1.1: $a>b=1$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+1)^2-1 \equiv 0 \pmod{10} \implies 10|a! \implies a \ge 5\].

There is no apparent contradiction here, so we leave this as it is.

Subcase 1.2: $a>b=2$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+2)^2-2 \equiv 2 \pmod{10} \implies a! \equiv 2 \pmod{10} \implies a=2\].

This contradicts with the fact that $a>b$, so this is impossible.

Subcase 1.3: $a>b=3$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+3)^2-6 \equiv 3 \pmod{10}\].

However, this is impossible for all $a$.

Subcase 1.4: $a>b=4$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+4)^2-24 \equiv 2 \pmod{10}\].

Again, this yields $a=2$, which, again, contradicts $a>b$. $\square$

Hence, we must have $b=1$.

Now, with $b$ determined by modular arithmetic, we actually plug in the values.

To simplify future calculations, note that

\[a!=\overline{ab}^2-b!=(10a+1)^2-1=100a^2+20a=10a(10a+2)\].

For $a=5$, this does not hold.

For $a=6$, this does not hold.

For $a=7$, this does hold. Hence, $(a,b)=(7,1)$ is a solution.

For $a=8$, this does not hold.

For $a=9$, this does not hold.

Hence, there is no positive integers $a$ and $b$ between $1$ and $9$ inclusive such that $a!+b!=\overline{ab}^2$.

Case 2: $a=b$

For this case, we must have

\[(11a)^2=\overline{ab}^2=a!+b!=2a! \implies 11|a!\]

which is impossible if a is a integer and $1 \le a \le 9$.

Case 3: $a<b$

In this case, we have

\[\overline{ab}^2=a! +b!=(1+b \cdot (b-1) \cdot \dots \cdot (a+1)) \cdot a! \implies a!|\overline{ab}^2=(10a+b)^2\].

If $a \ge 5$, we must have

\[10|a!|\overline{ab}^2=(10a+b)^2 \implies 10|(10a+b)^2=100a^2+20ab+b^2 \implies 10|b \implies b=0 \implies 10|a!+b!\]

which is impossible since $10|a!$ and $b!=1$.

Hence, $a \le 4$.

Subcase 3.1: $b>a=1$

\[(10+b)^2=1+b!\]

Testing cases, we can see that there is no such $b$.

Subcase 3.2: $b>a=2$

\[(20+b)^2=2+b!\]

Testing cases, we can see that there is no such $b$.

Subcase 3.3: $b>a=3$

\[(30+b)^2=3+b!\]

Testing cases, we can see that there is no such $b$.

Subcase 3.4: $b>a=4$

\[(40+b)^2=4+b!\]

Testing cases, we can see that there is no such $b$.

We see that $(a,b)=(7,1) \implies a+b=\boxed{008}$. $square$ ~Ddk001

Solution 2 (Official)

$\overline{ab}^2=a! +b!$ cleary square of a positive double-digit integer is either 3-digit or 4-digit as it ranges between $100(10^{2})$ and $9801(99^{2})$.

This means both $a$ and $b$ are less than or equal to 7 as any $factorial$ greater than 7! exceeds 9999.

Now at least one of $a$ or $b$ must be greater than or equal to 5 or else the maximum possible value of LHS is 4!+4!=48<100 also, both $a$ and $b$ can't be greater than or equal to 5 as if they were so. The unit digit of LHS would be zero but the unit digit of RHS would be either 5,6 or 9.

Hence, one of $a$ and $b$ is greater than or equal to 5 and the other is less than 5. this means the unit digit of RHS is the unit digit of a factorial which is less than 5.

Hence unit digit of RHS is 0,1,2, 6 or 4. 0,2,4 and 6 are rejected as follows:-

1. 2 can't be the unit digit of a perfect square.

2. If 6 is the unit digit of OF LHS this means one of the numbers is 3( as only 3! has the unit digit 6) and also this would mean that $b$ is either 4 or 6. This directly means that 36 and 34 are the only cases to be tested. 34 can't be as both the digits are less than 5 and 36 clearly doesn't satisfy

3. If 0 is the unit digit of LHS then 50 60 70 are the only cases (as one of the digits is greater than or equal to 5) that don't satisfy

4. If 4 is the unit digit of LHS this means one of the numbers is 4( as only 4! has the unit digit 4) and also this would mean that $b$ is either 2 or 8. This directly means that 42 and 48 are the only cases to be tested. 42 can't be as both the digits are less than 5 and 48 can't also as one of the digits is 8

Hence, the unit digit of LHS must be 1 for which $b$=1 or 9(rejected). This means 51 61 and 71 are the only cases to be tried now which is really very easy to calculate and get 71 as the only possible solution to the problem and

thus, our answer is 7+1=$\boxed{008}$. ~SANSGANKRSNGUPTA

Solution 3 (Official and Fastest)

$\overline{ab}^2=a! +b!$ cleary square of a positive double-digit integer is either 3-digit or 4-digit as it ranges between $100(10^{2})$ and $9801(99^{2})$.

This means both $a$ and $b$ are less than or equal to 7 as any $factorial$ greater than 7! exceeds 9999.

Now at least one of $a$ or $b$ must be greater than or equal to 5 or else the maximum possible value of LHS is 4!+4!=48<100 also, both $a$ and $b$ can't be greater than or equal to 5 as if they were so. The unit digit of LHS would be zero but the unit digit of RHS would be either 5,6 or 9.

Hence, one of $a$ and $b$ is greater than or equal to 5 and the other is less than 5. Also, RHS is a perfect square, so it must be 0 or 1 $(mod 4)$

Hence the number less than 5 can be either 1 or 4 because 2! and 3! are 2 $(mod 4)$

If it is 4, then the unit digit of RHS is 4 meaning $b$ is either 2 or 8 both of which aren't possible as 8>7 and the number less than 5 is 4 not 2.

If it is 1 then the unit digit of RHS is 1 implying $b$ is either 9(rejected 9>7) or 1. This means $b$ is 1, this means 51 61 and 71 are the only cases to be tried

which is very easy to calculate and get 71 as the only possible solution to the problem and

thus, our answer is 7+1=$\boxed{008}$. ~SANSGANKRSNGUPTA

Problem 8

Suppose $f(x)$ is a $10000000010$-degrees polynomial. The Fundamental Theorem of Algebra tells us that there are $10000000010$ roots, say $r_1, r_2, \dots, r_{10000000010}$. Suppose all integers $n$ ranging from $-1$ to $10000000008$ satisfies $f(n)=n$. Also, suppose that

\[(2+r_1)(2+r_2) \dots (2+r_{10000000010})=m!\]

for an integer $m$. If $p$ is the minimum possible positive integral value of

\[(1+r_1)(1+r_2) \dots (1+r_{10000000010})\].

Find the number of factors of the prime $999999937$ in $p$.

Solution 1

Since all integers $n$ ranging from $-1$ to $10000000008$ satisfies $f(n)=n$, we have that all integers $n$ ranging from $-1$ to $10000000008$ satisfies $f(n)-n=0$, so by the Factor Theorem,

\[n+1|f(n)-n, n|f(n)-n, \dots, n-10000000008|f(n)-n\]

\[\implies (n+1)n \dots (n-10000000008)|f(n)-n\].

\[\implies f(n)=a(n+1)n \dots (n-10000000008)+n\]

since $f(n)$ is a $10000000010$-degrees polynomial, and we let $a$ to be the leading coefficient of $f(n)$.

Also note that since $r_1, r_2, \dots, r_{10000000010}$ is the roots of $f(n)$, $f(n)=a(n-r_1)(n-r_2) \dots (n-r_{10000000010})$

Now, notice that

\[m!=(2+r_1)(2+r_2) \dots (2+r_{10000000010})\]

\[=(-2-r_1)(-2-r_2) \dots (-2-r_{10000000010})\]

\[=\frac{f(-2)}{a}\]

\[=\frac{a(-1) \cdot (-2) \dots (-10000000010)-2}{a}\]

\[=\frac{10000000010! \cdot a-2}{a}\]

\[=10000000010!-\frac{2}{a}\]

Similarly, we have

\[(1+r_1)(1+r_2) \dots (1+r_{10000000010})=\frac{f(-1)}{a}=-\frac{1}{a}\]

To minimize this, we minimize $m$. The minimum $m$ can get is when $m=10000000011$, in which case

\[-\frac{2}{a}=10000000011!-10000000010!\]

\[=10000000011 \cdot 10000000010!-10000000010!\]

\[=10000000010 \cdot 10000000010!\]

\[\implies p=(1+r_1)(1+r_2) \dots (1+r_{10000000010})\]

\[=-\frac{1}{a}\]

\[=\frac{10000000010 \cdot 10000000010!}{2}\]

\[=5000000005 \cdot 10000000010!\]

, so there is $\left\lfloor \frac{10000000010}{999999937} \right\rfloor=\boxed{011}$ factors of $999999937$. $\square$ ~Ddk001

Problem 9

$\Delta ABC$ is an isosceles triangle where $CB=CA$. Let the circumcircle of $\Delta ABC$ be $\Omega$. Then, there is a point $E$ and a point $D$ on circle $\Omega$ such that $AD$ and $AB$ trisects $\angle CAE$ and $BE<AE$, and point $D$ lies on minor arc $BC$. Point $F$ is chosen on segment $AD$ such that $CF$ is one of the altitudes of $\Delta ACD$. Ray $CF$ intersects $\Omega$ at point $G$ (not $C$) and is extended past $G$ to point $I$, and $IG=AC$. Point $H$ is also on $\Omega$ and $AH=GI<HB$. Let the perpendicular bisector of $BC$ and $AC$ intersect at $O$. Let $J$ be a point such that $OJ$ is both equal to $OA$ (in length) and is perpendicular to $IJ$ and $J$ is on the same side of $CI$ as $A$. Let $O’$ be the reflection of point $O$ over line $IJ$. There exist a circle $\Omega_1$ centered at $I$ and tangent to $\Omega$ at point $K$. $IO’$ intersect $\Omega_1$ at $L$. Now suppose $O’G$ intersects $\Omega$ at one distinct point, and $O’, G$, and $K$ are collinear. If $IG^2+IG \cdot GC=\frac{3}{4} IK^2 + \frac{3}{2} IK \cdot O’L + \frac{3}{4} O’L^2$, then $\frac{EH}{BH}$ can be expressed in the form $\frac{\sqrt{b}}{a} (\sqrt{c} + d)$, where $b$ and $c$ are not divisible by the squares of any prime. Find $a^2+b^2+c^2+d^2+abcd$.


An image is supposed to go here. You can help us out by creating one and editing it in. Thanks.


Solution 1

Line $IJ$ is tangent to $\Omega$ with point of tangency point $J$ because $OJ=OA \implies \text{J is on } \Omega$ and $IJ$ is perpendicular to $OJ$ so this is true by the definition of tangent lines. Both $G$ and $K$ are on $\Omega$ and line $O’G$, so $O’G$ intersects $\Omega$ at both $G$ and $K$, and since we’re given $O’G$ intersects $\Omega$ at one distinct point, $G$ and $K$ are not distinct, hence they are the same point.

Now, if the center of $2$ tangent circles are connected, the line segment will pass through the point of tangency. In this case, if we connect the center of $2$ tangent circles, $\Omega$ and $\Omega_1$ ($O$ and $I$ respectively), it is going to pass through the point of tangency, namely, $K$, which is the same point as $G$, so $O$, $I$, and $G$ are collinear. Hence, $G$ and $I$ are on both lines $OI$ and $CI$, so $CI$ passes through point $O$, making $CG$ a diameter of $\Omega$.

Now we state a few claims :

Claim 1: $\Delta O’IO$ is equilateral.

Proof:

\[\frac{3}{4} (IK+O’L)^2\]

\[=\frac{3}{4} IK^2+\frac{3}{2} IK \cdot O’L+\frac{3}{4} O’L^2\]

\[=IG^2+IG \cdot GC\]

\[=IG \cdot (IG+GC)\]

\[=IG \cdot IC\]

\[=IJ^2\]

where the last equality holds by the Power of a Point Theorem.

Taking the square root of each side yields $IJ= \frac{\sqrt{3}}{2} (IK+O’L)^2$.

Since, by the definition of point $L$, $L$ is on $\Omega_1$. Hence, $IK=IL$, so

$IJ= \frac{\sqrt{3}}{2} (IK+O’L)^2=\frac{\sqrt{3}}{2} (IL+O’L)^2=\frac{\sqrt{3}}{2} IO’^2$, and since $O’$ is the reflection of point $O$ over line $IJ$, $OJ=O’J=\frac{OO’}{2}$, and since $IJ=\frac{\sqrt{3}}{2} IO’^2$, by the Pythagorean Theorem we have

$JO’=\frac{IO’}{2} \implies \frac{OO’}{2}=\frac{IO’}{2} \implies OO’=IO’$

Since $IJ$ is the perpendicular bisector of $OO’$, $IO’=IO$ and we have $IO=IO’=OO’$ hence $\Delta O’IO$ is equilateral. $\square$

With this in mind, we see that

\[2OJ=OO’=OI=OK+KI=OJ+GI=OJ+AC \implies OA=OJ=AC\]

Here, we state another claim :

Claim 2 : $BH$ is a diameter of $\Omega$

Proof: Since $OA=OC=AC$, we have

\[\angle AOC =60^\circ \implies \angle ABC=\frac{1}{2} \angle AOC=30^\circ \implies AB=\sqrt{3} AC\]

and the same reasoning with $\Delta CAH$ gives $CH=\sqrt{3} AC$ since $AH=IG=AC$.

Now, apply Ptolemy’s Theorem gives

\[BH \cdot AC+BC \cdot AH=CH \cdot AB \implies BH \cdot AC+AC^2=3AC^2 \implies BH=2AC=2OA\]

so $BH$ is a diameter. $\square$

From that, we see that $\angle BEH=90^\circ$, so $\frac{EH}{BH}=\cos{BHE}$. Now,

\[\angle BHE=\angle BAE=\frac{1}{2} \angle CAB=15^\circ\]

, so

\[\frac{EH}{BH}=\cos{15}=\frac{\sqrt{6}+\sqrt{2}}{4}=\frac{\sqrt{2}}{4} (\sqrt{3}+1)\]

, so

\[a=4, b=2, c=3, d=1 \implies a^2+b^2+c^2+d^2+abcd=1+4+9+16+24=\boxed{054}\]

, and we’re done. $\square$ ~Ddk001


Problem 10

Let $A={1,2, \dots ,100}$. Let $A_i$, for each $i$ between $1$ and an positive integer $m$, be four-element subsets of the set $A$, no 2 of which have 3 or 4 elements in common. If $m \ge 40425$, find the last 3 digits of the sum of all elements, distinct or not, of the $A_i$'s.

Solution 1

Despite how ridiculously difficult this question might seem, there is actually a relatively simple solution, based on a slick observation.


For each $A_i$ there are $6$ 2-element subsets that can be chosen from it. By the Pigeonhole Principle, since there are only $4950$ possible 2 element subsets of $A$ at all, there must be at least one subset that appeared at least $\lfloor \frac{6 \cdot 40425}{4950} \rfloor =49$ times. In fact, if $m >40425$, one subset appears 50 times. However, the condition about no 2 $A_i$'s having 3 or 4 elements in common shows that there'd be over $102$ distinct elements in $A$, which is absurd. Thus, $m$ is exactly $40425$, and this implies all 2-element subsets of $A$ appeared exactly 49 times in $A_i$. Now, the sum of all 2-element subsets of $A_i$ is exactly 3 times the sum of all elements in $A_i$, distinct or not, so our desired answer is $\frac{1}{3} \cdot 6 \cdot 40425 \cdot 101 = 8165 \boxed{850}$ where the 101 is the average sum of 2-element subsets of $A$. $\square$

Problem 11

Let $x$ be the remainder when

\[106! + (53!)^2\]

is divided by $107 \cdot 53^3$. Find the remainder when $x$ is divided by $1000$.

Solution 1 (Endless Hensel's Lemma)

We note that

\[(53!)^2\]

\[=1 \cdot 2 \cdot \dots \cdot 53 \cdot (53 \cdot 52 \cdot \dots \cdot 1)\]

\[=1 \cdot 2 \cdot \dots \cdot 53 \cdot [53 \cdot 52 \cdot \dots \cdot 1 \cdot (-1)^{53}] \cdot (-1)\]

\[=1 \cdot 2 \cdot \dots \cdot 53 \cdot [(-53) \cdot (-52) \cdot \dots \cdot (-1)] \cdot (-1)\]

\[\equiv 1 \cdot 2 \cdot \dots \cdot 53 \cdot [(107-53) \cdot (107-52) \cdot \dots \cdot (107-1)] \cdot (-1)\]

\[= 1 \cdot 2 \cdot \dots \cdot 53 \cdot 54 \cdot 55 \cdot \dots \cdot 106 \cdot (-1)\]

\[= -106!\]

\[\equiv 1 \pmod {107}\]

where the last step follows from Wilson's Theorem.

Now, applying Wilson's Theorem again implies $106! \equiv 1 \pmod {107}$, so

\[106! + (53!)^2 \equiv 0 \pmod {107}\]

We see that

\[(52!)^2 \equiv (-1)^2\]

\[= 1 \pmod {53}\]

by Wilson's Theorem, so

\[(53!)^2 = 53^2 (52!)^2\]

\[\equiv 53^2 \pmod {53^3}\]

Somewhat similarly,

\[\frac{106!}{53^2} = \dbinom{106}{53} \cdot (52!)^2\]

\[\equiv 2 \pmod {53}\]

since $\binom{2p}{p} \equiv 2 \pmod p$ when $p$ is a prime. (Proof here) Thus,

\[106!= \frac{106!}{53^2} \cdot 53^2\]

\[\equiv 2 \cdot 53^2 \pmod {53^3}\]

so

\[106!+(53!)^2 \equiv 3 \cdot 53^2 \pmod {53^3}\]

We obtain the following linear system of congruences:

\[106! + (53!)^2 \equiv 0 \pmod {107}\]

\[106!+(53!)^2 \equiv 3 \cdot 53^2 \pmod {53^3}\]

By the Chinese Remainder Theorem,

\[106!+(53!)^2 \equiv 3 \cdot 53^2 \cdot 107 \cdot y \pmod {107 \cdot 53^3}\]

where $y$ is an integer such that

\[107y \equiv 1 \pmod {53^3}\]

(i.e. $y$ is an inverse of $107$ modulo $53^3$).

Seeing a power of a prime as modulus reminds us of Hensel's Lemma for solving polynomial congruences. Let \[f(y)=107y-1\]. We wish to solve $f(y) \equiv 0 \pmod {53^3}$. Obviously, $107 \equiv 1 \pmod {53}$, so $f(1) \equiv 0 \pmod {53}$. By Hensel's Lemma, there exists a unique integer $t \in [0,53)$ such that $f(53t+1) \equiv 0 \pmod {53^2}$, and $t$ is given by

\[t=- \bar{f'(1)} \cdot (\frac{f(1)}{53})\]

where $\bar{f'(1)}$ denotes the inverse of $f'(1)$ modulo $53$ (just $53$, not $53$ to any power). Again, $107 \equiv 1 \pmod {53}$, so since $f'(1) =107$, $\bar{f'(1)}=1$, so

\[t= -1 \cdot \frac{106}{53}\]

\[=-2\]

Therefore, we see that $f(-105) \equiv 0 \pmod {53^2}$. We preform another lift. Again, there exists unique integer $t \in [0,53)$ such that $f(-105+53^2 \cdot t) \equiv 0 \pmod {53^3}$, given by

\[t = - \bar{f'(-105)} \cdot (\frac{f(-105)}{53^2})\]

$f'(-105)$ is also $107$, so $\bar{f'(-105)} = 1$. We have $f(-105)= -105 \cdot 107 -1=-106^2= (-4) \cdot 53^2$, so

\[t = -1 \cdot (\frac{(-4) \cdot 53^2}{53^2}\]

\[=4\]

Therefore, $f(4 \cdot 53^2-105) \equiv 0 \pmod {53^3}$. We can thus set $y=4 \cdot 53^2-105$, so that

\[x \equiv 106!+(53!)^2\]

\[\equiv 3 \cdot 53^2 \cdot 107 \cdot y\]

\[= 3 \cdot 53^2 \cdot 107 \cdot (4 \cdot 53^2-105)\]

\[=12 \cdot 53^4 \cdot 107 - 315 \cdot 53^2 \cdot 107\]

\[\equiv - 315 \cdot 53^2 \cdot 107 \pmod {107 \cdot 53^3}\]

Thus,

\[x=53^3 \cdot 107 \cdot k - 315 \cdot 53^2 \cdot 107\]

\[= (53k-315) \cdot 53^2 \cdot 107\]

for some integer $k$. Since $0 \le x < 53^3 \cdot 107$ (since it is a remainder), $0 \le 53k-315 < 53 \implies k=6$. Therefore,

\[x=3 \cdot 53^2 \cdot 107\]

A simple calculation shows $53^2=2809$, so

\[x \equiv 3 \cdot 809 \cdot 107\]

\[\equiv \boxed{689} \pmod {1000}\]

This is our answer. $\square$. ~Ddk001

Problem 12

Let $\pi (n)$ denote the number of primes that is less than or equal to $n$.

Show that there exist numbers $c_1$ and $c_2$ such that

\[c_1 \frac{x}{\log{x}} \le \pi (x) \le c_2 \frac{x}{\log{x}}\]

Solution 1(The Proof by Chebyshev)

Let $p$ be a prime and $n$ be an integer. Since

\[\dbinom{2n}{n} = \frac{(2n)!}{(n!)(n!)}\]

, $p$ divides $\dbinom{2n}{n}$ exactly

\[\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)\]

times.

Therefore, since

\[\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor \le 1\]

, we have

\[\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)\]

\[\le \sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} 1\]

\[=\lfloor \log_{p}{(2n)} \rfloor\]

so if $p^r | \dbinom{2n}{n}$, $p^r \le 2n$

Repeated applications of that gives

\[\dbinom{2n}{n} \le (2n)^{\pi (2n)}\]

Additionally,

\[2^n=\prod_{a=1}^n {2} \le \prod_{a=1}^n {\frac{n+a}{a}} = \frac{(n+1) \cdot (n+2) \cdot \dots \cdot 2n}{n!} = \dbinom{2n}{n} \le \sum_{a=0}^{2n} {\dbinom{2n}{a}} = 2^{2n}\]

so

\[2^n \le (2n)^{\pi (2n)}\]

\[\implies n \cdot \log {2} \le \pi (2n) \cdot \log {2n}\]

\[\implies \pi (2n) \ge \frac{n \cdot \log {2}}{\log {2n}}\]

\[\implies \pi (n) \ge \frac{\log{2}}{2} \cdot \frac{n}{\log {n}}\]

Now, we note also that

\[\prod_{\text{p is a prime from n to 2n}} {p} | \dbinom{2n}{n}\]

so

\[n^{\pi (2n) - \pi (n)}=\prod_{\text{p is a prime from n to 2n}} n < \prod_{\text{p is a prime from n to 2n}} p \le \dbinom{2n}{n} \le 2^{2n}\]

Thus,

\[\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}\]

We have

\[\log {2n} \cdot \pi (2n)+\log {n} \cdot \pi (n)= \log {2} \cdot \pi (2n) + \log {n} \cdot (\pi (2n) - \pi (n)) \le \log {2} \cdot \pi (2n) + n \cdot \log {4} \le 3n \cdot \log {2}\]

since $\pi (2n) \le n$ for $n>3$ (because there is at least a half of even numbers).

Repeated addition of that gives

\[\pi (2n) = \frac{1}{\log{2n}} \cdot (\log {2n} \cdot \pi (2n)- \log {n} \cdot \pi (n))+(\log {n} \cdot \pi (n)- \log {\frac{n}{2}} \cdot \pi (\frac{n}{2}))+ (\log {\frac{n}{2}} \cdot \pi (\frac{n}{2})- \log {\frac{n}{4}} \cdot \pi (\frac{n}{4}))+ \dots\]

\[\le \frac{1}{\log {2n}} \cdot (3n \cdot \log {2}+\frac{3n}{2} \cdot \log {2}+\frac{3n}{4} \cdot \log {2}+ \dots)\]

\[= \frac{3n \cdot \log {2}}{\log {2n}} \cdot (1+ \frac{1}{2}+\frac{1}{4} + \dots)\]

\[= \frac{6n \cdot \log {2}}{\log {2n}}\]

\[\le \frac{\log{64} \cdot n}{\log{n}}\]

As we have previously derived,

\[\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}\]

so

\[\frac{\log {x}}{2^m} \cdot \pi (\frac{x}{2^m}) - \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}) = \frac{\log {x}}{2^{m}} (\pi (\frac{x}{2^m})-\pi (\frac{x}{2^{m+1}})) + \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}})\]

\[\le \frac{\log {x}}{2^{m}} \cdot \log {4} \cdot \frac{\frac{x}{2^{m+1}}}{\log {\frac{x}{2^{m+1}}}} + \frac{\log {x}}{2^{m+1}} \cdot \frac{\log{64} \cdot \frac{x}{2^{m+2}}}{\log{\frac{x}{2^{m+2}}}}\]

\[\le \frac{\log {x} \cdot \log {4}}{2^{2m+1}} \cdot (\frac{x}{\log {\frac{x}{2^{m+1}}}}+\frac{x}{\log {\frac{x}{2^{m+2}}}})\]

\[\le \frac{\log {x} \cdot \log {4}}{2^{2m}} \cdot \frac{x}{\log {x}- (m+2) \log {2}}\]

\[\le \log {4} \cdot \frac{x}{2^{m}}\]

. (The last step I do not know why. If you can figure out the reason, please add the intermediate steps for it)

If we add that, we get a telescoping sum, so we have

\[\log{x} \cdot \pi (x)  = \sum_{m=0}^{v} (\frac{\log {x}}{2^m} \cdot \pi (\frac{x}{2^m}) - \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}))\]

\[\le \log{4} \cdot x \sum_{m=0}^{v} \frac{1}{2^m}\]

\[\le \log{4} \cdot x\]

\[\implies \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}\]

where $v$ is the greatest integer such a that $2^v | x$.

Collecting our results, we see that

\[\frac{\log{2}}{2} \cdot \frac{n}{\log {n}} \le \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}\]

We have thus found the desired $c_1$ and $c_2$. ~Ddk001 $\square$

Note: This was actually the same method of proof given by Chebyshev.

Problem 13

Suppose there is $6$ hats and $34$ bins to put them in, and all objects are assigned a corresponding integer. Suppose there is $x$ ways of putting the hats in the bins such that the following criteria are followed:

(i) If $i<j$ (where $i$ and $j$ are integers), then hat $i$ is placed in a bin whose number is less than or equal to the number of the bin that hat $j$ is placed in

(ii) There is at least one bin that contains at least two hats

Find $x \mod 1000$.

Solution 1

We see that this is equivalent to asking "What is the number of ordered 6-tuples $(x_1,x_2, \dots , x_6)$ such that $x_1 \le x_2 \le x_3 \le \dots \le  x_6 \le 34$ and that $x_1 < x_2 < x_3 < \dots <x_6$ do NOT hold?". $x_i$ correspond to the number of the bin that hat $i$ is placed in. By the Nested Sum Theorem, there is $\dbinom{39}{6}$ ways of putting the hats in the bins without following the second criteria. We subtract the ways that do not follow the second criteria, i.e. the ordered 6-tuples such that

\[1 \le x_1 < x_2 < x_3 < \dots <x_6 \le 34\]

DO hold. There is obviously $\dbinom{34}{6}$ such ways. Thus, $x=\dbinom{39}{6} - \dbinom{34}{6}$.

We have

\[x=\dbinom{39}{6} - \dbinom{34}{6}\]

\[= \frac{39 \cdot 38 \cdot 37 \cdot 36 \cdot 35 \cdot 34 - 34 \cdot 33 \cdot 32 \cdot 31 \cdot 30 \cdot 29}{720}\]

\[= 13 \cdot 19 \cdot 37 \cdot 3 \cdot 7 \cdot 17 - 34 \cdot 11 \cdot 2 \cdot 31 \cdot 2 \cdot 29\]

\[\equiv 623 -904\]

\[= \boxed{719} \pmod {1000}\]

$\square$ ~ Ddk001

Problem 14

Let $0<a<b$ and $t_i \ge 0, i=1,2, \dots ,n$. Suppose further that $t_1 + t_2 + \dots + t_n =1$. Then show that for any $x_1, x_2, \dots, x_n \in [a,b],$

\[1 \le (\sum_{n=1}^{n} t_i x_i )(\sum_{n=1}^{n} \frac{t_i}{x_i} ) \le \frac{(a+b)^2}{4ab}\]

Solution 1 (Convexity + Cauchy-Schwarz)

We prove more generally that

\[\sum_{n=1}^n t_i \le (\sum_{n=1}^{n} t_i x_i )(\sum_{n=1}^{n} \frac{t_i}{x_i} ) \le \frac{(a+b)^2}{4ab} \cdot (\sum_{n=1}^n t_i )^2\]

Start with $(\sum_{n=1}^{n} t_i x_i )(\sum_{n=1}^{n} \frac{t_i}{x_i} ) \le \frac{(a+b)^2}{4ab} \cdot \sum_{n=1}^n t_i$.

Consider the expression on the left to be a function in the variables $x_1 , x_2 , \dots , x_n$. One sees that the function is a convex (some people knows it as concave upward) function in every variable, being the product of a convex (linear) function and another convex function. Therefore, maxima is achieved during the endpoints.

Now, WLOG let $x_1 , x_2 , \dots , x_m$ (for a integer $1 \le m \le n$) be $a$, and let the rest of the $x_i$'s be $b$. Let $u= t_1 + t_2 + \dots t_m$ and $v= t_{m+1} + \dots + t_n$. We have

\begin{align*} (\sum_{n=1}^{n} t_i x_i )(\sum_{n=1}^{n} \frac{t_i}{x_i} ) &= (u a + bv)(\frac{u}{a} + \frac{v}{b}) \\ &= u^2 + v^2 + uv \cdot (\frac{a}{b} + \frac{b}{a}) \\ &= (u+v)^2 + uv \cdot (\frac{a}{b} + \frac{b}{a} -2) \\ &\le (u+v)^2 + \frac{1}{4} (u+v)^2 (\frac{a}{b} + \frac{b}{a} -2) \\ &= \frac{(a+b)^2}{4ab} \cdot (u+v)^2 \end{align*}

and $u+v = \sum_{n=1}^n t_i$, so our result is proved.

Now, the inequality on the left is almost a immediate consequence of the Cauchy-Schwarz Inequality. $\square$

Problem 15

Suppose \[\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}+\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]=\frac{p}{q}\] where $p$ and $q$ are relatively prime positive integers. Find $p+q$.

Solution 1(Wordless endless bash)

\[\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}\]

\[=\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{mn(m+n+2)}\]

\[=\sum_{n=1}^{\infty} \frac{1}{n} \sum_{m=1}^{\infty} \frac{1}{m(m+n+2)}\]

\[=\sum_{n=1}^{\infty} \frac{1}{n} \sum_{m=1}^{\infty} \frac{1}{n+2} (\frac{1}{m}-\frac{1}{m+n+2})\]

\[=\sum_{n=1}^{\infty} \frac{1}{n(n+2)} \sum_{m=1}^{\infty} (\frac{1}{m}-\frac{1}{m+n+2})\]

\[=\sum_{n=1}^{\infty} \frac{1}{n(n+2)} \cdot [(1-\frac{1}{n+3})+(\frac{1}{2}-\frac{1}{n+4})+ \dots]\]

\[=\sum_{n=1}^{\infty} \frac{1}{n(n+2)} \cdot (1+\frac{1}{2}+\frac{1}{3}+ \dots \frac{1}{n+2})\]

\[=\sum_{n=1}^{\infty} (\frac{\frac{1}{2}}{n}-\frac{\frac{1}{2}}{n+2}) \cdot (1+\frac{1}{2}+\frac{1}{3}+ \dots \frac{1}{n+2})\]

\[=\frac{1}{2} [(1-\frac{1}{3})(1+\frac{1}{2}+\frac{1}{3})+(\frac{1}{2}-\frac{1}{4})(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4})+ \dots\]

\[=\frac{1}{2} [[(1-\frac{1}{3})+(\frac{1}{3}-\frac{1}{5})+\dots](1+\frac{1}{2}+\frac{1}{3})+[(\frac{1}{2}-\frac{1}{4})+(\frac{1}{4}-\frac{1}{6})+\dots](1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4})+[(\frac{1}{3}-\frac{1}{5})+(\frac{1}{5}-\frac{1}{7})+\dots](\frac{1}{4}+\frac{1}{5})+\dots]\]

\[=\frac{1}{2} [(1+\frac{1}{2}+\frac{1}{3})+\frac{1}{2} (1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4})+\frac{1}{3} (\frac{1}{4}+\frac{1}{5})+\dots]\]

\[=\frac{1}{2} [\frac{11}{6}+\frac{1}{2} \cdot \frac{25}{12}+(\frac{1}{3 \cdot 4}+\frac{1}{4 \cdot 5}+\dots)+(\frac{1}{3 \cdot 5}+\frac{1}{4 \cdot 6}+\dots)]\]

\[=\frac{1}{2} [\frac{69}{24}+[(\frac{1}{3}-\frac{1}{4})+(\frac{1}{4}-\frac{1}{5})+\dots ]+\frac{1}{2} [(\frac{1}{3}-\frac{1}{5})+(\frac{1}{4}-\frac{1}{6})+\dots ]\]

\[=\frac{1}{2} [\frac{69}{24}+\frac{1}{3}+\frac{1}{6}+\frac{1}{8}]\]

\[=\frac{1}{2} \cdot \frac{84}{24}\]

\[=\frac{7}{4}\]

\[(1+\frac{1}{x})^x=e^{x \cdot \ln (1+\frac{1}{x})}\]

\[=e^{x \cdot [(\frac{1}{x})-\frac{(\frac{1}{x})^2}{2}+\frac{(\frac{1}{x})^3}{3}+\dots]}\]

\[=e^{1-\frac{1}{2} (\frac{1}{x})+\frac{1}{3} (\frac{1}{x})^2+\dots}\]

\[=e \cdot e^{-\frac{1}{2} (\frac{1}{x})} \cdot e^{\frac{1}{3} (\frac{1}{x})^2} \dots\]

\[=e \cdot [1-\frac{1}{2x}+\frac{1}{2!} (\frac{1}{2x})^2- \dots] \cdot [1+\frac{1}{3x^2}+\frac{1}{2!} (\frac{1}{3x^2})^2+ \dots]\]

\[=e[1-\frac{1}{2x}+\frac{11}{24} (\frac{1}{x})^2+\dots]\]

\[\implies \lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]\]

\[=\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{e[1-\frac{1}{2x}+\frac{11}{24} (\frac{1}{x})^2+\dots]}{e}-1]]\]

\[=\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 (1-\frac{1}{2x}+\frac{11}{24} (\frac{1}{x})^2+\dots-1)]\]

\[=\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 (-\frac{1}{2x}+\frac{11}{24} (\frac{1}{x})^2+\dots)]\]

\[=\lim_{x\rightarrow \infty} (\frac{x}{2}-\frac{x}{2}+\frac{11}{24}+\dots)\]

\[=\frac{11}{24}\]

\[\implies \sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{n \cdot m^2+m \cdot n^2+2mn}+\lim_{x\rightarrow \infty} [\frac{x}{2}+x^2 [\frac{(1+\frac{1}{x})^{x}}{e}-1]]\]

\[=\frac{7}{4}+\frac{11}{24}\]

\[=\frac{53}{24}\]

\[\implies p=53,q=24\]

\[\implies p+q=\boxed{077}\] $\square$~Ddk001

Problem 16

In $\Delta ABC$ with $AB=AC$, $D$ is the foot of the perpendicular from $A$ to $BC$. $E$ is the foot of the perpendicular from $D$ to $AC$. $F$ is the midpoint of $DE$. Prove that $AF \perp BE$.

[asy] pair A,B,C,D,E,F; A = (0,0); B = (-4,-3); C = (4,-3); D = (0,-3); E = (36/25,-27/25); F = (18/25,-51/25); draw(A--B); draw(B--C); draw(C--A); draw(A--D); draw(A--F, red); draw(B--E, red); draw(D--E); dot((0,0)); dot((-4,-3)); dot((4,-3)); dot((0,-3)); dot((36/25,-27/25)); dot((18/25,-51/25)); [/asy]

Solution 1 (Analytic geo)

Let

\[A=(0,0)\]

\[B=(4a,4b)\]

\[C=(4 \sqrt{a^2+b^2},0)\]

We set it this way to simplify calculation when we calculate the coordinates of $E$ and $F$ (Notice to find $E$, you just need to take the x coordinate of $D$ and let the y coordinate be $0$).

Obviously,

\[D=(\frac{4a+4 \sqrt{a^2+b^2}}{2},\frac{4b+0}{2})=(2a+2 \sqrt{a^2+b^2},2b)\]

\[\implies E=(2a+2 \sqrt{a^2+b^2},0)\]

\[\implies F=(\frac{2a+2 \sqrt{a^2+b^2}+2a+2 \sqrt{a^2+b^2}}{2},\frac{2b+0}{2})=(2a+2 \sqrt{a^2+b^2},b)\]

Now, we see that

\[\text{Slope} _ {AF}=\frac{b}{2a+2 \sqrt{a^2+b^2}}\]

\[\text{Slope} _ {BE}=\frac{0-4b}{2a+2 \sqrt{a^2+b^2}-4a}=\frac{-2b}{\sqrt{a^2+b^2}-a}\]

\[\implies \text{Slope} _ {AF} \cdot \text{Slope} _ {BE}=\frac{b}{2a+2 \sqrt{a^2+b^2}} \cdot \frac{-2b}{a+ \sqrt{a^2+b^2}-2a}=\frac{-2b^2}{2(a+\sqrt{a^2+b^2})(\sqrt{a^2+b^2}-a)}=\frac{-2b^2}{2b^2}=-1\]

, so $AF \perp BE$, as desired. $\square$~Ddk001

Solution 2 (Hard vector bash)

Solution 2a (Hard)

\[\overrightarrow{AF} \cdot \overrightarrow{BE}\]

\[=(\overrightarrow{AE}+\overrightarrow{EF}) \cdot (\overrightarrow{BD}+\overrightarrow{DE})\]

\[=\overrightarrow{AE} \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{DE}+\overrightarrow{AE} \cdot \overrightarrow{DE}\]

\[=\overrightarrow{AE} \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{DE}\]

\[=(\overrightarrow{AD}+\overrightarrow{DE}) \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{BD} + \overrightarrow{EF} \cdot \overrightarrow{DE}\]

\[=\overrightarrow{DE} \cdot \overrightarrow{BD}+\overrightarrow{EF} \cdot \overrightarrow{BD} + \overrightarrow{EF} \cdot \overrightarrow{DE}\]

\[=\overrightarrow{DE} \cdot \overrightarrow{DC}-\frac{\overrightarrow{DE}}{2} \cdot \overrightarrow{BD}-\frac{\overrightarrow{DE}}{2} \cdot \overrightarrow{DE}\]

\[=\frac{\overrightarrow{DE}}{2} \cdot \overrightarrow{DC}-\frac{\overrightarrow{DE}}{2} \cdot \overrightarrow{DE}\]

\[=\overrightarrow{DE} \cdot (\frac{\overrightarrow{DC}-\overrightarrow{DE}}{2})\]

\[=\frac{\overrightarrow{DE} \cdot \overrightarrow{EC}}{2}\]

\[=0\]

Hence, $AF \perp BE$. $\square$ ~Ddk001

Solution 2b (Harder)

\[\angle ACD=\angle ECD\]

\[\angle ADC=\angle DEC\]

\[\implies \Delta ADC \sim \Delta DEC\]

\[\implies \frac{EC}{DC}=\frac{DC}{AC}\]

\[\implies EC=\frac{DC^2}{AC}\]

\[\implies \overrightarrow{E}=\overrightarrow{C}+\overrightarrow{CE}\]

\[=\overrightarrow{C}+\frac{CE}{AC} \cdot \overrightarrow{CA}\]

\[=\overrightarrow{C}+\frac{DC^2}{AC^2} \overrightarrow{CA}\]

\[=\overrightarrow{C}+\frac{DC^2}{AC^2} (\overrightarrow{A}-\overrightarrow{C})\]

\[=\frac{AC^2-DC^2}{AC^2} \overrightarrow{C}+\frac{DC^2}{AC^2} \overrightarrow{A}\]

\[=\frac{AD^2}{AC^2} \overrightarrow{C}+\frac{DC^2}{AC^2} \overrightarrow{A}\]

\[\overrightarrow{D}=\frac{\overrightarrow{B}+\overrightarrow{C}}{2}\]

Since $F$ is the midpoint of $DE$,

\[\overrightarrow{F}=\frac{\overrightarrow{D}+\overrightarrow{E}}{2}\]

\[=\frac{\frac{\overrightarrow{B}+\overrightarrow{C}}{2}+\frac{AD^2}{AC^2} \overrightarrow{C}+\frac{DC^2}{AC^2} \overrightarrow{A}}{2}\]

\[=\frac{\overrightarrow{B}}{4}+\frac{AC^2+2AD^2}{4AC^2} \overrightarrow{C}+\frac{DC^2}{2AC^2} \overrightarrow{A}\]

\[\overrightarrow{AF}=\overrightarrow{F}-\overrightarrow{A}=\frac{\overrightarrow{B}}{4}+\frac{AC^2+2AD^2}{4AC^2} \overrightarrow{C}+\frac{DC^2-2AC^2}{2AC^2} \overrightarrow{A}\]

\[\overrightarrow{BE}=\overrightarrow{E}-\overrightarrow{B}=\frac{AD^2}{AC^2} \overrightarrow{C}+\frac{DC^2}{AC^2} \overrightarrow{A}-\overrightarrow{B}\]

Now come the coordinates. Let

\[A=(0,0)\]

\[B=(-a,-b)\]

\[C=(a,-b)\]

so that

\[\overrightarrow{A}=\langle 0,0 \rangle\]

\[\overrightarrow{B}=\langle -a,-b \rangle\]

\[\overrightarrow{C}=\langle a,-b \rangle\].

Therefore,

\[\overrightarrow{AF}=\langle \frac{-a}{4},\frac{-b}{4} \rangle + \frac{(a^2+b^2)+2b^2}{4(a^2+b^2)} \langle a,-b \rangle=\langle \frac{ab^2}{2(a^2+b^2)},\frac{-a^2b-2b^3}{2(a^2+b^2)} \rangle\]

\[\overrightarrow{BE}=\frac{b^2}{a^2+b^2} \langle a,-b \rangle-\langle -a,-b \rangle=\langle \frac{2ab^2+a^3}{a^2+b^2},\frac{a^2b}{a^2+b^2} \rangle\]

\[\implies \overrightarrow{AF} \cdot \overrightarrow{BE}=\langle \frac{ab^2}{2(a^2+b^2)},\frac{-a^2b-2b^3}{2(a^2+b^2)} \rangle \cdot \langle \frac{2ab^2+a^3}{a^2+b^2},\frac{a^2b}{a^2+b^2} \rangle\]

\[=\frac{1}{2(a^2+b^2)^2}[ab^2(a^3+2ab^2)-a^2b(a^2b+2b^3)]\]

\[=\frac{ab}{2(a^2+b^2)^2} (a^3b+2ab^3-a^3b-2ab^3)\]

\[=0\]

Hence, we have that $AF$ is perpendicular to $BE$. $\square$ ~Ddk001

Problem 17

Show that the series

\[\sum_{n=2}^\infty \frac{1}{n^m (\log{n})^p}\]

where p and m are real numbers converge if $m>1$ or $m=1$ but $p>1$ and diverge otherwise.

Solution 1 (Real analysis bash)

The solution is extremely long and tedious. It is put in a different page for that reason. Solution 1 to Problems Collection Proofs Problem 2

Problem 18

Let $x,y$ and $z$ be real numbers. Show that

\[(x^2+z^2)^2+y^4 \ge 4xzy^2\]

Solution 1 (Plain high school contest)

It might seem insane, but we are going to divide this problem into 2 cases:

\[xy+yz \ge 0\]

and

\[xy+yz \le 0\]

Case 1: $xy+yz \ge 0$

By the Trivial Inequality, we have

\[(x-\frac{y}{\sqrt{2}})^2 \ge 0\] \[(z-\frac{y}{\sqrt{2}})^2 \ge 0\]

. Add these inequalities gives

\[(x-\frac{y}{\sqrt{2}})^2+(z-\frac{y}{\sqrt{2}})^2 \ge 0\]

and expanding yields

\[x^2+y^2+z^2 \ge \sqrt{2} (xy+yz)\]

Since $xy+yz \ge 0$, we can square both sides and obtain

\[(x^2+y^2+z^2)^2 \ge 2(xy+yz)^2\]

so

\[x^4+y^4+z^4+2x^2 y^2+2y^2z^2+2x^2z^2 \ge 2(x^2y^2+y^2z^2+2xzy^2)\] \[\implies (x^2+z^2)^2+y^4=x^4+y^4+z^4+2x^2z^2 \ge 4xzy^2\]

so the result follow if $xy+yz \ge 0$. $\square$


Case 2: $xy+yz \le 0$


By the Trivial Inequality, we have

\[(x+\frac{y}{\sqrt{2}})^2 \ge 0\] \[(z+\frac{y}{\sqrt{2}})^2 \ge 0\]

. Add these inequalities gives

\[(x+\frac{y}{\sqrt{2}})^2+(z+\frac{y}{\sqrt{2}})^2 \ge 0\]

and expanding yields

\[x^2+y^2+z^2 \ge - \sqrt{2} (xy+yz)\]

Since $-(xy+yz) \ge 0$, we can square both sides and obtain

\[(x^2+y^2+z^2)^2 \ge 2(xy+yz)^2\]

and the rest proceeds as in case 1. $\square$

The result follows. $\square$ ~Ddk001

Solution 2 (Lagrange Multipliers)

Put $f(x,y,z)=(x^2+z^2)^2+y^4-4xzy^2$ and let

Under construction

Solution 3 (Finding relative extrema with calculus)

Let $f(x, y, z) = (x^2 + z^2)^2 + y^4 - 4xzy^2$. We will prove that $f$ is never negative (equivalent to the problem statement) by finding the critical values of $f$. (Note that $f$ is a polynomial of $x$, $y$, and $z$. Therefore, we do not need to consider discontinuities.) We will begin by setting partial derivatives of $f$ to $0$. (Note that if $x = 0$, $y = 0$, or $z = 0$, the inequality in the problem statement reduces to $(x^2 + z^2)^2 + y^4 \ge 0$, which is true by the Trivial Inequality. Here on, we assume $x, y, z \neq 0$).

\[\frac{\partial f}{\partial x} = 4x(x^2 + z^2) - 4zy^2 = 0\]

\[\therefore x^3 + z^2x = zy^2 \textbf{(1)}\]

\[\frac{\partial f}{\partial z} = 4z(z^2 + x^2) - 4xy^2 = 0\] \[\therefore z^3 + x^2z = xy^2 \textbf{(2)}\]

\[\frac{\partial f}{\partial y} = 4y^3 - 8xzy = 0\] \[\therefore y^2 = 2xz \textbf{(3)}\]


If $(x, y, z)$ is a critical point of $f$, then it must satisfy equations (1), (2), and (3). Substituting (3) into (1), we find:

\[x^3 + z^2x = 2xz^2\] \[\therefore x^3 = xz^2\] \[\therefore x^2 = z^2\] \[\therefore |x| = |z|\]

If $x \neq z$, then $x = -z$ and $(x^2 + z^2)^2 + y^4 \ge 0 \ge 4xzy^2 = -4x^2y^2$ by the Trivial Inequality. We now only need to consider the case where $x = z$. Let $g(x, y)$ be the function obtained when we substitute $x = z$ into function $f$.

\[f(x, y, z) = (x^2 + z^2)^2 + y^4 - 4xzy^2\] \[\therefore g(x, y) = (2x^2)^2 + y^4 - 4x^2y^2\].

We must now prove that $g$ is never negative (proving this statement finishes the last case of the proof). We similarly find the critical values of $g$ by taking partial derivatives of $g$ and setting them to $0$.

\[\frac{\partial g}{\partial x} = 16x^3 - 8y^2x = 0\] \[\therefore 2x^2 = y^2\]

\[\frac{\partial g}{\partial y} = 4y^3 - 8x^2y = 0\] \[\therefore 2x^2 = y^2\]

If $(x, y)$ is a critical point of $g$, then $2x^2 = y^2$. If $2x^2 = y^2$ then $g(x, y) = (2x^2)^2 + y^4 - 4x^2y^2 = 4x^4 + 4x^4 - 8x^4 = 0$. Therefore, $g$ is never negative. QED

Solution 4 (AM-GM bash)

Under construction (I am not very sure if this could work)

Problem 19

Common blood types are determined genetically by 3 alleles: $A$,$B$, and $O$. A person whose blood type is $AB$, $AO$, or $BO$ is heterozygous while $BA$, $OA$, or $OB$ is homozygous. The Hardy-Weinberg Law states that the proportion P of heterozygous individuals in a certain population is given by

\[P(p,q,r)=2pq+2pr+2qr\]

where $p$ is the percent of allele $A$, $q$ the percent of allele $B$, and $r$ the percent allele $O$. Find the maximum possible proportion of heterozygous individuals in a certain population.

Solution 1 (Lagrange Multipliers)

Note that allele $A$, $B$, and $O$ make up all the alleles, so therefore,

\[p+q+r=1\]

The problem reduces to determining the maximum value of $f(p,q,r)=2pq+2pr+2qr$ given that $g(p,q,r)=p+q+r=1$. Now, by the Method of Lagrange multipliers, we find all values of $p$, $q$, and $r$ and $\lambda$ such that the gradient of $f$ is $\lambda$ times the gradient of $g$, or

\[\nabla f(p,q,r)= \lambda \nabla g(p,q,r)\]

\[\implies (2q+2r) \overrightarrow{i} + (2p+2r) \overrightarrow{j} + (2p+2q) \overrightarrow{k} = \lambda (\overrightarrow{i}+\overrightarrow{j}+\overrightarrow{k})\]

or

\[2q+2r=\lambda\]

\[2p+2r=\lambda\]

\[2p+2q=\lambda\]

Solving yields

\[p= \frac{\lambda}{4}\]

\[q= \frac{\lambda}{4}\]

\[r= \frac{\lambda}{4}\]

Now, since $p+q+r=1$, we have

\[\lambda =\frac{4}{3}\]

so $p=\frac{1}{3},q=\frac{1}{3},r=\frac{1}{3}$. Therefore, the maximum of $f$ given $g=1$ is

\[f(\frac{1}{3} ,\frac{1}{3} ,\frac{1}{3} )=\boxed{\frac{2}{3}}\]

$\square$.

Solution 2 (Relative extrema by calculus)

Just as in solution 1, we see that $p+q+r=1$. To turn this into a 2-D problem, substitute

\[r=1-p-q\]

so that

\[2pq+2pr+2qr=2pq+2p(1-p-q)+2q(1-p-q)=2p+2q-2p^2-2q^2-2pq\]

Let $f(p,q)=2p+2q-2p^2-2q^2-2pq$. We take the partial derivatives of $f$ and set them to zero to get the critical points:

\[f_p = 2-4p-2q\]

\[f_q=2-4q-2p\]

We set them to zero:

\[2-4p-2q=0\] \[2-4q-2p\] \[\implies 2p+q=1\] \[\implies 2q+p=1\] \[\implies p=\frac{1}{3}\] \[\implies q= \frac{1}{3}\] \[\implies r=\frac{1}{3}\] We see that $(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ is the only critical points. Thus, it must be the desired point. $\square$ ~Ddk001


Problem 20

Let

\[(x^2-2y)^3+(y^2-2x)^3+(4-xy)^3-3(x^2-2y)(y^2-2x)(4-xy)=64\]

and $x=\frac{6m}{1+m^3} <0$ for a real number $m$.

Find $y$ in terms of $m$.

Solution 1 (Plain Algebra)

In this solution, we will utilize the formula (mostly in the lemma that we will state)

\[x^3+y^3+z^3-3xyz=(x+y+z)(a^2+b^2+c^2-ab-bc-ca)=(x+y+z)((x-y)^2+(y-z)^2+(x-z)^2)/2\]

We first present a lemma:


Lemma: For any real numbers $x,y,z$, one have

\[(x^2-yz)^3+(y^2-xz)^3+(z^2-xy)^3-3(x^2-yz)(y^2-xz)(z^2-xy)=(x^3+y^3+z^3-3xyz)^2\]


The proof of the lemma is rather tedious, so we postpone the proof to the end of the solution.

Now, we thus have, substituting $z=2$ in the lemma,

\[8=\sqrt{(x^2-yz)^3+(y^2-xz)^3+(z^2-xy)^3-3(x^2-yz)(y^2-xz)(z^2-xy)}=x^3+y^3+8-6xy\]

so

\[x^3+y^3-6xy=0\]

Let $y=mx$ for a real number $m$ ($x$ is nonzero). Then

\[(1+k^3)x^3-6kx^2=0\]

\[\implies x=\frac{6m}{1+m^3}\]

Hmmmm.... What a coincidence! (or is it?) This just happens to be exactly the form that $x$ is in in the problem. We need only to show that the desired $x$ is unique, which is true indeed since the function $f(x)=\frac{6x}{1+x^3}$ is only equal to negative values when $x \in (-1,0)$, and in that interval, $f$ is monotonic and thus one to one, so $x$ is indeed unique and this completes the proof... if we prove our lemma.

Proof of Lemma:

By

\[x^3+y^3+z^3-3xyz=(x+y+z)(a^2+b^2+c^2-ab-bc-ca)=(x+y+z)((x-y)^2+(y-z)^2+(x-z)^2)/2\]

one have

$\square$

~Ddk001

Problem 21

Let $F_n$ denote the $n$th Fibonacci number. Prove that if $n$ is odd, then all odd prime divisors of $F_n$ are $1 \mod{4}$.

Solution 1 (short and elegant)

Let $n=2k+1$ for some nonnegative integer $k$. Then $F_n=F_{2k+1}=(F_k)^2+(F_{k+1})^2$. Since $F_k$ and $F_{k+1}$ are relatively prime, we are done.

Solution by Yiyj1

Problem 22

Let $a_1, a_2, \dots, a_n$ be a sequence of positive integers such that for all $i$ with $1 \leq i \leq n$, the following condition holds: \[a_i^2 - a_{i+1}^2 = 1 \quad \text{for} \quad i = 1, 2, \dots, n-1,\] where $a_{n+1} = a_1$.

If $a_1 = 1$, what is the value of $a_n$ in terms of $n$?

Solution 1

We begin by analyzing the recurrence relation: \[a_i^2 - a_{i+1}^2 = 1 \quad \text{for all} \quad i = 1, 2, \dots, n-1.\] This equation can be factored as: \[(a_i - a_{i+1})(a_i + a_{i+1}) = 1.\] Since $a_i$ and $a_{i+1}$ are positive integers, the only possible factorization of $1$ is: \[a_i - a_{i+1} = 1 \quad \text{and} \quad a_i + a_{i+1} = 1.\] However, the second condition implies $a_i < 1$, which contradicts $a_i$ being positive. Therefore, we must have: \[a_i - a_{i+1} = -1 \quad \text{for all } i.\] This implies the sequence is increasing by $1$ at each step: \[a_1 = 1,\ a_2 = 2,\ a_3 = 3, \dots,\ a_n = n.\] Thus, \[\boxed{a_n = n}.\] $\square$ ~ aoum

Problem 23

In a triangle $ABC$, the incircle touches side $BC$ at $D$, side $CA$ at $E$, and side $AB$ at $F$. Let $P$ be the point of intersection of lines $AF$ and $CE$, and let the incircle’s radius be $r$. Prove that the area of triangle $AEF$ is equal to the area of triangle $ABC$ divided by $2r$.

[asy] // Asymptote code and diagram by aoum size(250); defaultpen(fontsize(10pt));  // Define triangle vertices pair A = (0,5); pair B = (-4,0); pair C = (4,0);  // Draw triangle ABC draw(A--B--C--cycle);  // Incenter and incircle pair I = incenter(A,B,C); real r = abs(foot(I,B,C) - I); draw(circle(I, r), dashed);  // Tangency points (feet of perpendiculars from incenter to triangle sides) pair D = foot(I, B, C); pair E = foot(I, C, A); pair F = foot(I, A, B);  // Cevians AF and CE draw(A--F); draw(C--E);  // Intersection point P of AF and CE pair P = extension(A, F, C, E);  // Triangle AEF draw(A--E--F--cycle);  // Points dot("$A$", A, dir(90)); dot("$B$", B, dir(-135)); dot("$C$", C, dir(-45)); dot("$I$", I, dir(180)); dot("$D$", D, dir(-90)); dot("$E$", E, dir(45)); dot("$F$", F, dir(135)); [/asy]

Solution 1

Let the area of triangle $ABC$ be denoted by $A$, and let the area of triangle $AEF$ be denoted by $A_{AEF}$.

Recall that the area of triangle $ABC$ can be written in terms of its inradius $r$ and semiperimeter $s$ as: \[A = r \cdot s,\] where $s$ is the semiperimeter of triangle $ABC$.

Now observe that triangle $AEF$ is bounded by the tangents from $A$ to the incircle (segments $AE$ and $AF$) and the chord $EF$ formed by the tangency points on $AC$ and $AB$. This triangle lies entirely within triangle $ABC$.

It turns out that triangle $AEF$ has a fixed area related to the incenter and the tangents. From known results in geometry, we have: \[A_{AEF} = \frac{A}{2r}.\]

This result can be derived using more advanced incenter-based area formulas or barycentric coordinates.

Therefore, the area of triangle $AEF$ is indeed equal to $\frac{A}{2r}$, as required. $\square$ ~ aoum

Credits

Here are the credits for each problem:

Problems 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, and 20: Ddk001

Problem 7: SANSKAR'S OG PROBLEMS, credits given to SANSGANKRSNGUPTA

Problem 21: dim super cool yiyj1

Problems 22 and 23: aoum

Note: Problem 6 is based on the Tower of Hanoi problem

See Also

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.