Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "User:Ddk001"

m (→‎Problems Sharing Contest)
m
Line 63: Line 63:
 
Someone mind making a diagram for this?
 
Someone mind making a diagram for this?
  
−
==Answer key & solution to the problems==
+
 
 
I will leave a big gap below this sentence so you won't see the answers accidentally.  
 
I will leave a big gap below this sentence so you won't see the answers accidentally.  
  
Line 137: Line 137:
 
fsd
 
fsd
  
−
===Answer key===
+
==Answer key==
  
 
1. 049
 
1. 049
Line 149: Line 149:
 
5. 054
 
5. 054
  
−
===Solutions===
+
==Solutions==
  
−
====Problem 1====
+
===Problem 1===
 
There is one and only one perfect square in the form
 
There is one and only one perfect square in the form
  
Line 158: Line 158:
 
where <math>p</math> and <math>q</math> is prime. Find that perfect square.
 
where <math>p</math> and <math>q</math> is prime. Find that perfect square.
  
−
====Solution 1====
+
===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>.  
 
<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>.
 
Suppose <math>n^2=(p^2+1)(q^2+1)-((pq)^2-pq+1)</math>.
 
Then, <math>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)</math>, 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>
 
Then, <math>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)</math>, 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====
+
===Problem 2===
 
Suppose there are complex values <math>x_1, x_2,</math> and <math>x_3</math> that satisfy
 
Suppose there are complex values <math>x_1, x_2,</math> and <math>x_3</math> that satisfy
  
Line 169: Line 169:
  
 
Find <math>x_{1}^3+x_{2}^3+x_{2}^3</math>.
 
Find <math>x_{1}^3+x_{2}^3+x_{2}^3</math>.
−
====Solution 1====
+
===Solution 1===
 
To make things easier, instead of saying <math>x_i</math>, we say <math>x</math>.
 
To make things easier, instead of saying <math>x_i</math>, we say <math>x</math>.
  
Line 221: Line 221:
 
Note: If you don't know [[Newton's Sums]], you can also use [[Vieta's Formulas]] to bash.
 
Note: If you don't know [[Newton's Sums]], you can also use [[Vieta's Formulas]] to bash.
  
−
====Problem 3====
+
===Problem 3===
 
Suppose
 
Suppose
  
Line 228: Line 228:
 
Find the remainder when <math>\min{x}</math> is divided by 1000.
 
Find the remainder when <math>\min{x}</math> is divided by 1000.
  
−
====Solution 1 (Euler's Totient Theorem)====
+
===Solution 1 (Euler's Totient Theorem)===
 
We first simplify <math>\cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6:</math>
 
We first simplify <math>\cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6:</math>
  
Line 260: Line 260:
 
Solving yields <math>x \equiv 2\boxed{736} \pmod{7!}</math>, and we're done. <math>\square</math>
 
Solving yields <math>x \equiv 2\boxed{736} \pmod{7!}</math>, and we're done. <math>\square</math>
  
−
====Problem 4====
+
===Problem 4===
 
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 271: Line 271:
 
Find the number of factors of the prime <math>999999937</math> in <math>p</math>.
 
Find the number of factors of the prime <math>999999937</math> in <math>p</math>.
  
−
====Solution 1====
+
===Solution 1===
 
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]],  
 
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]],  
  
Line 320: Line 320:
 
, so there is <math>\left\lfloor \frac{10000000010}{999999937} \right\rfloor=\boxed{011}</math> factors of <math>999999937</math>. <math>\square</math>
 
, so there is <math>\left\lfloor \frac{10000000010}{999999937} \right\rfloor=\boxed{011}</math> factors of <math>999999937</math>. <math>\square</math>
  
−
====Problem 5====
+
===Problem 5===
 
<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?
 
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.  
 
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.  
  

Revision as of 16:33, 6 January 2024

User Counts

If this is you first time visiting this page, please change the number below by one. (Add 1, do NOT subtract 1)

$\boxed{\boxed{\boxed{\boxed{\boxed{\boxed{1}}}}}}$

(Please don't mess with the user count)

Doesn't that look like a number on a pyramid?

Cool asyptote graphs

Asymptote is fun! [asy]draw((0,0)----(0,6));draw((0,-3)----(-3,3));draw((3,0)----(-3,6));draw((6,-6)----(-6,3));draw((6,0)----(-6,0));[/asy]

[asy]draw(circle((0,0),1));draw((1,0)----(0,1));draw((1,0)----(0,2));draw((0,-1)----(0,2));draw(circle((0,3),2));draw(circle((0,4),3));draw(circle((0,5),4));draw(circle((0,2),1));draw((0,9)----(0,18));[/asy]


Problems Sharing Contest

Here, you can post all the math problem that you made, not copied problems from past exams. Everyone will try to come up with a appropriate solution. The person with the first solution will post the next problem. I'll start:

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$ are prime. Find that perfect square. (DO NOT LOOK AT MY SOLUTIONS)

Problems I made

1. (Much easier) 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$ are prime. Find that perfect square.

2. Suppose there is 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$.

3. 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.

4. 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$.

5. (Much harder) $\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$.

Someone mind making a diagram for this?


I will leave a big gap below this sentence so you won't see the answers accidentally.






























dsf






fsd

Answer key

1. 049

2. 170

3. 736

4. 011

5. 054

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$

Problem 2

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

To make things easier, instead of saying $x_i$, we say $x$.

Now, we have $(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})$.

As we have done many times before, 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.

Problem 3

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 $\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$

Problem 4

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$

Problem 5

$\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$.

Someone mind making a diagram for this?

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 concurrent. 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 \implies \angle ABC=\frac{1}{2} \angle AOC=30 \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$, so $\frac{EH}{BH}=\cos{BHE}$. Now,

$\angle BHE=\angle BAE=\frac{1}{2} \angle CAB=15$

, 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. $\blacksquare$

Note: All angle measures are in degrees

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=User:Ddk001&oldid=210065"