Difference between revisions of "Problems Collection"
m (Fixed typo) |
m (→Sources) |
||
(106 intermediate revisions by 3 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). | ||
− | ==AMC styled== | + | 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). |
− | ==AIME styled== | + | |
− | 1. There is one and only one perfect square in the form | + | ==Contributed Problems and Solutions== |
+ | |||
+ | |||
+ | Please contribute whatever problems you have. | ||
+ | |||
+ | ==Problems== | ||
+ | ===AMC styled=== | ||
+ | Nothing yet to show | ||
+ | ===AIME styled=== | ||
+ | 1.There is one and only one perfect square in the form | ||
<cmath>(p^2+1)(q^2+1)-((pq)^2-pq+1)</cmath> | <cmath>(p^2+1)(q^2+1)-((pq)^2-pq+1)</cmath> | ||
− | where <math>p</math> and <math>q</math> | + | where <math>p</math> and <math>q</math> is prime. Find that perfect square. |
− | 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>. | + | 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>. |
Line 20: | Line 29: | ||
− | 4. Suppose there | + | 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>. | Find <math>x_{1}^3+x_{2}^3+x_{2}^3</math>. | ||
− | 5. Suppose | + | 5.Suppose |
<cmath>x \equiv 2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6 \pmod{7!}</cmath> | <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>. | 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>. | + | 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 | |
− | 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> | <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 | + | 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>. | <cmath>(1+r_1)(1+r_2) \dots (1+r_{10000000010})</cmath>. | ||
Line 58: | Line 64: | ||
− | 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>. | + | 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>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>. | ||
+ | |||
+ | |||
+ | 11. 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> | ||
+ | |||
+ | |||
+ | 12. 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 | ||
+ | |||
+ | Find <math>x \mod 1000</math>. | ||
+ | |||
+ | ===Olympiad styled=== | ||
+ | |||
+ | ===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>. | ||
+ | |||
+ | |||
+ | 2. 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> | ||
+ | |||
+ | |||
+ | 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> | ||
+ | |||
+ | 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). | ||
+ | |||
+ | ===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>. | ||
+ | |||
+ | |||
+ | 2.Show that the series | ||
− | + | <cmath>\sum_{n=2}^\infty \frac{1}{n^m (\log{n})^p}</cmath> | |
+ | |||
+ | 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>. | |
− | + | Problem by [[User:Yiyj1|Yiyj1]] ([[User talk:Yiyj1|talk]]) 23:44, 3 December 2024 (EST) | |
− | |||
==Solutions== | ==Solutions== | ||
Line 171: | Line 224: | ||
<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> | ||
− | + | 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 189: | Line 242: | ||
===Solution 1=== | ===Solution 1=== | ||
− | + | We interpret the <math>x_i</math> 's as roots of the polynomial | |
− | |||
<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 613: | Line 666: | ||
===Problem 10=== | ===Problem 10=== | ||
+ | |||
+ | 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>. | ||
+ | |||
+ | ===Solution 1 (Hensel's Lemma)=== | ||
+ | |||
+ | We note that | ||
+ | |||
+ | <cmath>(53!)^2</cmath> | ||
+ | |||
+ | <cmath>=1 \cdot 2 \cdot \dots \cdot 53 \cdot (53 \cdot 52 \cdot \dots \cdot 1)</cmath> | ||
+ | |||
+ | <cmath>=1 \cdot 2 \cdot \dots \cdot 53 \cdot [53 \cdot 52 \cdot \dots \cdot 1 \cdot (-1)^{53}] \cdot (-1)</cmath> | ||
+ | |||
+ | <cmath>=1 \cdot 2 \cdot \dots \cdot 53 \cdot [(-53) \cdot (-52) \cdot \dots \cdot (-1)] \cdot (-1)</cmath> | ||
+ | |||
+ | <cmath>\equiv 1 \cdot 2 \cdot \dots \cdot 53 \cdot [(107-53) \cdot (107-52) \cdot \dots \cdot (107-1)] \cdot (-1)</cmath> | ||
+ | |||
+ | <cmath>= 1 \cdot 2 \cdot \dots \cdot 53 \cdot 54 \cdot 55 \cdot \dots \cdot 106 \cdot (-1)</cmath> | ||
+ | |||
+ | <cmath>= -106!</cmath> | ||
+ | |||
+ | <cmath>\equiv 1 \pmod {107} </cmath> | ||
+ | |||
+ | where the last step follows from [[Wilson's Theorem]]. | ||
+ | |||
+ | Now, applying [[Wilson's Theorem]] again implies <math>106! \equiv 1 \pmod {107}</math>, so | ||
+ | |||
+ | <cmath>106! + (53!)^2 \equiv 0 \pmod {107}</cmath> | ||
+ | |||
+ | We see that | ||
+ | |||
+ | <cmath>(52!)^2 \equiv (-1)^2</cmath> | ||
+ | |||
+ | <cmath>= 1 \pmod {53}</cmath> | ||
+ | |||
+ | by [[Wilson's Theorem]], so | ||
+ | |||
+ | <cmath>(53!)^2 = 53^2 (52!)^2</cmath> | ||
+ | |||
+ | <cmath>\equiv 53^2 \pmod {53^3}</cmath> | ||
+ | |||
+ | Somewhat similarly, | ||
+ | |||
+ | <cmath>\frac{106!}{53^2} = \dbinom{106}{53} \cdot (52!)^2</cmath> | ||
+ | |||
+ | <cmath>\equiv 2 \pmod {53}</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>106!= \frac{106!}{53^2} \cdot 53^2</cmath> | ||
+ | |||
+ | <cmath>\equiv 2 \cdot 53^2 \pmod {53^3}</cmath> | ||
+ | |||
+ | so | ||
+ | |||
+ | <cmath>106!+(53!)^2 \equiv 3 \cdot 53^2 \pmod {53^3}</cmath> | ||
+ | |||
+ | We obtain the following linear system of congruences: | ||
+ | |||
+ | <cmath>106! + (53!)^2 \equiv 0 \pmod {107}</cmath> | ||
+ | |||
+ | <cmath>106!+(53!)^2 \equiv 3 \cdot 53^2 \pmod {53^3}</cmath> | ||
+ | |||
+ | By the [[Chinese Remainder Theorem]], | ||
+ | |||
+ | <cmath>106!+(53!)^2 \equiv 3 \cdot 53^2 \cdot 107 \cdot y \pmod {107 \cdot 53^3}</cmath> | ||
+ | |||
+ | where <math>y</math> is an integer such that | ||
+ | |||
+ | <cmath>107y \equiv 1 \pmod {53^3}</cmath> | ||
+ | |||
+ | (i.e. <math>y</math> is an inverse of <math>107</math> modulo <math>53^3</math>). | ||
+ | |||
+ | 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>t=- \bar{f'(1)} \cdot (\frac{f(1)}{53})</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>t= -1 \cdot \frac{106}{53}</cmath> | ||
+ | |||
+ | <cmath>=-2</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>t = - \bar{f'(-105)} \cdot (\frac{f(-105)}{53^2})</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 | ||
+ | |||
+ | <cmath>t = -1 \cdot (\frac{(-4) \cdot 53^2}{53^2}</cmath> | ||
+ | |||
+ | <cmath>=4</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>x \equiv 106!+(53!)^2</cmath> | ||
+ | |||
+ | <cmath>\equiv 3 \cdot 53^2 \cdot 107 \cdot y</cmath> | ||
+ | |||
+ | <cmath>= 3 \cdot 53^2 \cdot 107 \cdot (4 \cdot 53^2-105)</cmath> | ||
+ | |||
+ | <cmath>=12 \cdot 53^4 \cdot 107 - 315 \cdot 53^2 \cdot 107</cmath> | ||
+ | |||
+ | <cmath>\equiv - 315 \cdot 53^2 \cdot 107 \pmod {107 \cdot 53^3}</cmath> | ||
+ | |||
+ | Thus, | ||
+ | |||
+ | <cmath>x=53^3 \cdot 107 \cdot k - 315 \cdot 53^2 \cdot 107</cmath> | ||
+ | |||
+ | <cmath>= (53k-315) \cdot 53^2 \cdot 107</cmath> | ||
+ | |||
+ | 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, | ||
+ | |||
+ | <cmath>x=3 \cdot 53^2 \cdot 107</cmath> | ||
+ | |||
+ | A simple calculation shows <math>53^2=2809</math>, so | ||
+ | |||
+ | <cmath>x \equiv 3 \cdot 809 \cdot 107</cmath> | ||
+ | |||
+ | <cmath>\equiv \boxed{689} \pmod {1000}</cmath> | ||
+ | |||
+ | This is our answer. <math>\square</math>. ~ [[Ddk001]] | ||
+ | |||
+ | |||
+ | ===Problem 11=== | ||
+ | |||
+ | 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> | ||
+ | |||
+ | ===Solution 1(The Proof by Chebyshev)=== | ||
+ | |||
+ | Let <math>p</math> be a prime and <math>n</math> be an integer. Since | ||
+ | |||
+ | <cmath>\dbinom{2n}{n} = \frac{(2n)!}{(n!)(n!)}</cmath> | ||
+ | |||
+ | , <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> | ||
+ | |||
+ | times. | ||
+ | |||
+ | Therefore, since | ||
+ | |||
+ | <cmath>\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor \le 1</cmath> | ||
+ | |||
+ | , we have | ||
+ | |||
+ | <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> | ||
+ | |||
+ | <cmath>=\lfloor \log_{p}{(2n)} \rfloor</cmath> | ||
+ | |||
+ | so if <math>p^r | \dbinom{2n}{n}</math>, <math>p^r \le 2n</math> | ||
+ | |||
+ | Repeated applications of that gives | ||
+ | |||
+ | <cmath>\dbinom{2n}{n} \le (2n)^{\pi (2n)}</cmath> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | so | ||
+ | |||
+ | <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> | ||
+ | |||
+ | so | ||
+ | |||
+ | <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>\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> | ||
+ | |||
+ | <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>\le \frac{\log {x} \cdot \log {4}}{2^{2m}} \cdot \frac{x}{\log {x}- (m+2) \log {2}}</cmath> | ||
+ | |||
+ | <cmath>\le \log {4} \cdot \frac{x}{2^{m}}</cmath> | ||
+ | |||
+ | . (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 | ||
+ | |||
+ | <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>\le \log{4} \cdot x \sum_{m=0}^{v} \frac{1}{2^m}</cmath> | ||
+ | |||
+ | <cmath>\le \log{4} \cdot x</cmath> | ||
+ | |||
+ | <cmath>\implies \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}</cmath> | ||
+ | |||
+ | where <math>v</math> is the greatest integer such a that <math>2^v | x</math>. | ||
+ | |||
+ | Collecting our results, we see that | ||
+ | |||
+ | <cmath>\frac{\log{2}}{2} \cdot \frac{n}{\log {n}} \le \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}</cmath> | ||
+ | |||
+ | We have thus found the desired <math>c_1</math> and <math>c_2</math>. ~[[Ddk001]] <math>\blacksquare</math> | ||
+ | |||
+ | Note: This was actually the same method of proof given by Chebyshev. | ||
+ | |||
+ | ===Problem 12=== | ||
+ | |||
+ | 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 | ||
+ | |||
+ | Find <math>x \mod 1000</math>. | ||
+ | |||
+ | ===Solution 1=== | ||
+ | |||
+ | 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 | ||
+ | |||
+ | <cmath>1 \le x_1 < x_2 < x_3 < \dots <x_6 \le 34</cmath> | ||
+ | |||
+ | DO hold. There is obviously <math>\dbinom{34}{6}</math> such ways. Thus, <math>x=\dbinom{39}{6} - \dbinom{34}{6}</math>. | ||
+ | |||
+ | We have | ||
+ | |||
+ | <cmath>x=\dbinom{39}{6} - \dbinom{34}{6}</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>= 13 \cdot 19 \cdot 37 \cdot 3 \cdot 7 \cdot 17 - 34 \cdot 11 \cdot 2 \cdot 31 \cdot 2 \cdot 29</cmath> | ||
+ | |||
+ | <cmath>\equiv 623 -904</cmath> | ||
+ | |||
+ | <cmath>= \boxed{719} \pmod {1000}</cmath> | ||
+ | |||
+ | <math>\square</math> ~ [[Ddk001]] | ||
+ | |||
+ | |||
+ | ===Problem 13=== | ||
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 682: | Line 1,017: | ||
<cmath>\implies p+q=\boxed{077}</cmath> <math>\square</math>~[[Ddk001]] | <cmath>\implies p+q=\boxed{077}</cmath> <math>\square</math>~[[Ddk001]] | ||
− | ===Problem | + | ===Problem 14=== |
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>. | ||
Line 807: | Line 1,142: | ||
Hence, we have that <math>AF</math> is perpendicular to <math>BE</math>. <math>\square</math> ~[[Ddk001]] | Hence, we have that <math>AF</math> is perpendicular to <math>BE</math>. <math>\square</math> ~[[Ddk001]] | ||
+ | ===Problem 15=== | ||
+ | Show that the series | ||
+ | |||
+ | <cmath>\sum_{n=2}^\infty \frac{1}{n^m (\log{n})^p}</cmath> | ||
+ | |||
+ | 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 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 16=== | ||
+ | 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>\blacksquare</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 | ||
+ | |||
+ | ===Solution 4 (AM-GM bash)=== | ||
+ | Under construction (I am not very sure if this could work) | ||
+ | |||
+ | ===Problem 17=== | ||
+ | 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 | ||
+ | |||
+ | <cmath>P(p,q,r)=2pq+2pr+2qr</cmath> | ||
+ | |||
+ | 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. | ||
+ | |||
+ | ===Solution 1 (Lagrange Multipliers)=== | ||
+ | Note that allele <math>A</math>, <math>B</math>, and <math>O</math> make up all the alleles, so therefore, | ||
+ | |||
+ | <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 | ||
+ | |||
+ | <cmath>\nabla f(p,q,r)= \lambda \nabla g(p,q,r)</cmath> | ||
+ | |||
+ | <cmath>\implies (2q+2r) \overrightarrow{i} + (2p+2r) \overrightarrow{j} + (2p+2q) \overrightarrow{k} = \lambda (\overrightarrow{i}+\overrightarrow{j}+\overrightarrow{k})</cmath> | ||
+ | |||
+ | or | ||
+ | |||
+ | <cmath>2q+2r=\lambda</cmath> | ||
+ | |||
+ | <cmath>2p+2r=\lambda</cmath> | ||
+ | |||
+ | <cmath>2p+2q=\lambda</cmath> | ||
+ | |||
+ | Solving yields | ||
+ | |||
+ | <cmath>p= \frac{\lambda}{4}</cmath> | ||
+ | |||
+ | <cmath>q= \frac{\lambda}{4}</cmath> | ||
+ | |||
+ | <cmath>r= \frac{\lambda}{4}</cmath> | ||
+ | |||
+ | Now, since <math>p+q+r=1</math>, we have | ||
+ | |||
+ | <cmath>\lambda =\frac{4}{3}</cmath> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | <math>\blacksquare</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 | ||
+ | |||
+ | <cmath>r=1-p-q</cmath> | ||
+ | |||
+ | so that | ||
+ | |||
+ | <cmath>2pq+2pr+2qr=2pq+2p(1-p-q)+2q(1-p-q)=2p+2q-2p^2-2q^2-2pq</cmath> | ||
+ | |||
+ | 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. ~[[Ddk001]] <math>\square</math> | ||
+ | |||
+ | ===Problem 18=== | ||
+ | |||
+ | 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>. | ||
+ | |||
+ | ===Solution 1 (short and elegant)=== | ||
+ | |||
+ | 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. | ||
+ | |||
+ | Solution by [[User:Yiyj1|Yiyj1]] ([[User talk:Yiyj1|talk]]) 23:48, 3 December 2024 (EST) | ||
+ | |||
+ | ==Contributors== | ||
+ | |||
+ | *[[Ddk001]] | ||
+ | *[[User:Yiyj1|Yiyj1]] | ||
+ | |||
+ | ==Sources== | ||
Here's the source for the problems: | Here's the source for the problems: | ||
− | 1,2,3,4,5,6,8,9,10,11: | + | 1,2,3,4,5,6,8,9,10,11,12,13,14,15,16,17: [[Ddk001]] |
7: [[SANSKAR'S OG PROBLEMS]], credits given to SANSGANKRSNGUPTA | 7: [[SANSKAR'S OG PROBLEMS]], credits given to SANSGANKRSNGUPTA | ||
+ | |||
+ | 18: [[User:Yiyj1|dim super cool yiyj1]] | ||
* Note: Problem 6 is based on the Tower of Hanoi Problem | * Note: Problem 6 is based on the Tower of Hanoi Problem | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | * [[Number Theory Problems and Results]] | ||
+ | |||
+ | * [[Algebra Problems and Results]] | ||
+ | |||
+ | * [[Geometry Problems and Results]] | ||
+ | |||
+ | * [[Probability and Combinatics Problems and Results]] | ||
+ | |||
+ | * [[More Categorized Problem Collection]] | ||
+ | |||
+ | |||
+ | {{alternate solutions}} |
Latest revision as of 21:50, 9 January 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
[hide]- 1 Contributed Problems and Solutions
- 2 Problems
- 3 Solutions
- 3.1 Problem 1
- 3.2 Solution 1
- 3.3 Problem 2
- 3.4 Solution 1 (Slow, probably official MAA)
- 3.5 Solution 2 (Fast)
- 3.6 Solution 3 (Faster)
- 3.7 Problem 3
- 3.8 Solution 1(Probably official MAA, lots of proofs)
- 3.9 Solution 2 (Fast, risky, no proofs)
- 3.10 Problem 4
- 3.11 Solution 1
- 3.12 Problem 5
- 3.13 Solution 1 (Euler's Totient Theorem)
- 3.14 Problem 6
- 3.15 Solution 1 (Recursion)
- 3.16 Problem 7
- 3.17 Solution 1 (Tedious Casework)
- 3.18 Solution 2 (Official)
- 3.19 Solution 3 (Official and Fastest)
- 3.20 Problem 8
- 3.21 Solution 1
- 3.22 Problem 9
- 3.23 Solution 1
- 3.24 Problem 10
- 3.25 Solution 1 (Hensel's Lemma)
- 3.26 Problem 11
- 3.27 Solution 1(The Proof by Chebyshev)
- 3.28 Problem 12
- 3.29 Solution 1
- 3.30 Problem 13
- 3.31 Solution 1(Wordless endless bash)
- 3.32 Problem 14
- 3.33 Solution 1 (Analytic geo)
- 3.34 Solution 2 (Hard vector bash)
- 3.35 Problem 15
- 3.36 Solution 1 (Real analysis bash)
- 3.37 Problem 16
- 3.38 Solution 1 (Plain high school contest)
- 3.39 Solution 2 (Lagrange Multipliers)
- 3.40 Solution 3 (Finding relative extrema with calculus)
- 3.41 Solution 4 (AM-GM bash)
- 3.42 Problem 17
- 3.43 Solution 1 (Lagrange Multipliers)
- 3.44 Solution 2 (Relative extrema by calculus)
- 3.45 Problem 18
- 3.46 Solution 1 (short and elegant)
- 4 Contributors
- 5 Sources
- 6 See Also
Contributed Problems and Solutions
Please contribute whatever problems you have.
Problems
AMC styled
Nothing yet to show
AIME styled
1.There is one and only one perfect square in the form
where and
is prime. Find that perfect square.
2. and
are positive integers. If
, find
.
3.The fraction,
where and
are side lengths of a triangle, lies in the interval
, where
and
are rational numbers. Then,
can be expressed as
, where
and
are relatively prime positive integers. Find
.
4.Suppose there are complex values and
that satisfy
Find
.
5.Suppose
Find the remainder when
is divided by 1000.
6.Suppose that there is rings, each of different size. All of them are placed on a peg, smallest on the top and biggest on the bottom. There are
other pegs positioned sufficiently apart. A
is made if
(i) 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 be the minimum possible number
that can transfer all
rings onto the second peg. Find the remainder when
is divided by
.
7.Let be a 2-digit positive integer satisfying
. Find the sum of all possible values of
.
8.Suppose is a
-degrees polynomial. The Fundamental Theorem of Algebra tells us that there are
roots, say
. Suppose all integers
ranging from
to
satisfies
. Also, suppose that
for an integer . If
is the minimum possible positive integral value of
.
Find the number of factors of the prime in
.
9. is an isosceles triangle where
. Let the circumcircle of
be
. Then, there is a point
and a point
on circle
such that
and
trisects
and
, and point
lies on minor arc
. Point
is chosen on segment
such that
is one of the altitudes of
. Ray
intersects
at point
(not
) and is extended past
to point
, and
. Point
is also on
and
. Let the perpendicular bisector of
and
intersect at
. Let
be a point such that
is both equal to
(in length) and is perpendicular to
and
is on the same side of
as
. Let
be the reflection of point
over line
. There exist a circle
centered at
and tangent to
at point
.
intersect
at
. Now suppose
intersects
at one distinct point, and
, and
are collinear. If
, then
can be expressed in the form
, where
and
are not divisible by the squares of any prime. Find
.
10. Let be the remainder when
is divided by . Find the remainder when
is divided by
.
11. Let denote the number of primes that is less than or equal to
.
Show that there exist numbers and
such that
12. Suppose there is hats and
bins to put them in, and all objects are assigned a corresponding integer. Suppose there is
ways of putting the hats in the bins such that the following criteria are followed:
(i) If (where
and
are integers), then hat
is placed in a bin whose number is less than or equal to the number of the bin that hat
is placed in
(ii) There is at least one bin that contains at least two hats
Find .
Olympiad styled
Putnam styled (Calculus version of AMC, AIME, and Olympiad)
1.Suppose where
and
are relatively prime positive integers. Find
.
2. Let and
be real numbers. Show that
3. Common blood types are determined genetically by 3 alleles: ,
, and
. A person whose blood genotype is
,
,
,
,
, or
is heterozygous while a person whose blood genotype is
,
, or
is homozygous. The Hardy-Weinberg Law states that the proportion P of heterozygous individuals in a certain population (in genetic equilibrium) is given by
where is the percent of allele
,
the percent of allele
, and
the percent allele
within the population. Find the maximum possible proportion of heterozygous individuals in a population (in genetic equilibrium).
Others (proofs & ect.)
1.In with
,
is the foot of the perpendicular from
to
.
is the foot of the perpendicular from
to
.
is the midpoint of
. Prove that
.
2.Show that the series
where p and m are real numbers converge if or
but
and diverge otherwise.
3. Let denote the
th Fibonacci number. Prove that if
is odd, then all odd prime divisors of
are
.
Problem by Yiyj1 (talk) 23:44, 3 December 2024 (EST)
Solutions
Problem 1
There is one and only one perfect square in the form
where and
is prime. Find that perfect square.
Solution 1
.
Suppose
.
Then,
, so since ,
so
is less than both
and
and thus we have
and
. Adding them gives
so by Simon's Favorite Factoring Trick,
in some order. Hence,
.
~Ddk001
Problem 2
and
are positive integers. If
, find
.
Solution 1 (Slow, probably official MAA)
Let and
. Then,
Solution 2 (Fast)
Recall that a perfect square can be written as
. Since
is a perfect square, the RHS must be in this form. We substitute
for
to get that
. To make the middle term have an exponent of
, we must have
. Then
and
, so
.
~ cxsmi
Solution 3 (Faster)
Calculating the terms on the RHS, we find that . We use trial-and-error to find a power of two that makes the RHS a perfect square. We find that
works, and it produces
. Then
.
~ (also) cxsmi
Problem 3
The fraction,
where and
are side lengths of a triangle, lies in the interval
, where
and
are rational numbers. Then,
can be expressed as
, where
and
are relatively prime positive integers. Find
.
Solution 1(Probably official MAA, lots of proofs)
Lemma 1:
Proof: Since the sides of triangles have positive length, . Hence,
, so now we just need to find .
Since by the Trivial Inequality, we have
as desired.
To show that the minimum value is achievable, we see that if ,
, so the minimum is thus achievable.
Thus, .
Lemma 2:
Proof: By the Triangle Inequality, we have
.
Since , we have
.
Add them together gives
Note that
.
Hence, , since by taking
and
close
, we can get
to be as close to
as we wish.
Solution 2 (Fast, risky, no proofs)
By the Principle of Insufficient Reason, taking we get either the max or the min. Testing other values yields that we got the max, so
. Another extrema must occur when one of
(WLOG,
) is
. Again, using the logic of solution 1 we see
so
so our answer is
.
~Ddk001
Problem 4
Suppose there are complex values and
that satisfy
Find .
Solution 1
We interpret the 's as roots of the polynomial
.
Expanding gives
.
To make things even simpler, let
, so that .
Then, if , Newton's Sums gives
Therefore,
Now, we plug in
.
We substitute to get
.
Note: If you don't know Newton's Sums, you can also use Vieta's Formulas to bash.~Ddk001
Problem 5
Suppose
Find the remainder when is divided by 1000.
Solution 1 (Euler's Totient Theorem)
We first simplify
so
.
where the last step of all 3 congruences hold by the Euler's Totient Theorem. Hence,
Now, you can bash through solving linear congruences, but there is a smarter way. Notice that , and
. Hence,
, so
. With this in mind, we proceed with finding
.
Notice that and that
. Therefore, we obtain the system of congruences :
.
Solving yields , and we're done.
~Ddk001
Problem 6
Suppose that there is rings, each of different size. All of them are placed on a peg, smallest on the top and biggest on the bottom. There are
other pegs positioned sufficiently apart. A
is made if
(i) 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 be the minimum possible number
that can transfer all
rings onto the second peg. Find the remainder when
is divided by
.
Solution 1 (Recursion)
Let be the minimum possible number
that can transfer
rings onto the second peg. To build the recursion, we consider what is the minimum possible number
that can transfer
rings onto the second peg. If we use only legal
, then
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
rings to the third peg using
, then place the largest ring onto the bottom of the second peg using
, and then get all the rings from the third peg on top of the largest ring using another
. This gives a total of
, hence we have
. Obviously,
. We claim that
. This is definitely the case for
. If this is true for
, then
so this is true for . Therefore, by induction,
is true for all
. Now,
. Therefore, we see that
.
But the part is trickier. Notice that by the Euler's Totient Theorem,
so is equivalent to the inverse of
in
, which is equivalent to the inverse of
in
, which, by inspection, is simply
. Hence,
, so by the Chinese Remainder Theorem, .
Problem 7
Let be a 2-digit positive integer satisfying
. Find the sum of all possible values of
.
Solution 1 (Tedious Casework)
Case 1:
In this case, we have
.
If , we must have
, but this contradicts the original assumption of , so hence we must have
.
With this in mind, we consider the unit digit of .
Subcase 1.1:
In this case, we have that
.
There is no apparent contradiction here, so we leave this as it is.
Subcase 1.2:
In this case, we have that
.
This contradicts with the fact that , so this is impossible.
Subcase 1.3:
In this case, we have that
.
However, this is impossible for all .
Subcase 1.4:
In this case, we have that
.
Again, this yields , which, again, contradicts
.
Hence, we must have .
Now, with determined by modular arithmetic, we actually plug in the values.
To simplify future calculations, note that
.
For , this does not hold.
For , this does not hold.
For , this does hold. Hence,
is a solution.
For , this does not hold.
For , this does not hold.
Hence, there is no positive integers and
between
and
inclusive such that
.
Case 2:
For this case, we must have
which is impossible if a is a integer and .
Case 3:
In this case, we have
.
If , we must have
which is impossible since and
.
Hence, .
Subcase 3.1:
Testing cases, we can see that there is no such .
Subcase 3.2:
Testing cases, we can see that there is no such .
Subcase 3.3:
Testing cases, we can see that there is no such .
Subcase 3.4:
Testing cases, we can see that there is no such .
We see that .
~Ddk001
Solution 2 (Official)
cleary square of a positive double-digit integer is either 3-digit or 4-digit as it ranges between
and
.
This means both and
are less than or equal to 7 as any
greater than 7! exceeds 9999.
Now at least one of or
must be greater than or equal to 5 or else the maximum possible value of LHS is 4!+4!=48<100
also, both
and
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 and
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 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 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 =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=.~ SANSGANKRSNGUPTA
Solution 3 (Official and Fastest)
cleary square of a positive double-digit integer is either 3-digit or 4-digit as it ranges between
and
.
This means both and
are less than or equal to 7 as any
greater than 7! exceeds 9999.
Now at least one of or
must be greater than or equal to 5 or else the maximum possible value of LHS is 4!+4!=48<100
also, both
and
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 and
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
Hence the number less than 5 can be either 1 or 4 because 2! and 3! are 2
If it is 4, then the unit digit of RHS is 4 meaning 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 is either 9(rejected 9>7) or 1. This means
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=.~ SANSGANKRSNGUPTA
Problem 8
Suppose is a
-degrees polynomial. The Fundamental Theorem of Algebra tells us that there are
roots, say
. Suppose all integers
ranging from
to
satisfies
. Also, suppose that
for an integer . If
is the minimum possible positive integral value of
.
Find the number of factors of the prime in
.
Solution 1
Since all integers ranging from
to
satisfies
, we have that all integers
ranging from
to
satisfies
, so by the Factor Theorem,
.
since is a
-degrees polynomial, and we let
to be the leading coefficient of
.
Also note that since is the roots of
,
Now, notice that
Similarly, we have
To minimize this, we minimize . The minimum
can get is when
, in which case
, so there is factors of
.
~Ddk001
Problem 9
is an isosceles triangle where
. Let the circumcircle of
be
. Then, there is a point
and a point
on circle
such that
and
trisects
and
, and point
lies on minor arc
. Point
is chosen on segment
such that
is one of the altitudes of
. Ray
intersects
at point
(not
) and is extended past
to point
, and
. Point
is also on
and
. Let the perpendicular bisector of
and
intersect at
. Let
be a point such that
is both equal to
(in length) and is perpendicular to
and
is on the same side of
as
. Let
be the reflection of point
over line
. There exist a circle
centered at
and tangent to
at point
.
intersect
at
. Now suppose
intersects
at one distinct point, and
, and
are collinear. If
, then
can be expressed in the form
, where
and
are not divisible by the squares of any prime. Find
.
Someone mind making a diagram for this?
Solution 1
Line is tangent to
with point of tangency point
because
and
is perpendicular to
so this is true by the definition of tangent lines. Both
and
are on
and line
, so
intersects
at both
and
, and since we’re given
intersects
at one distinct point,
and
are not distinct, hence they are the same point.
Now, if the center of tangent circles are connected, the line segment will pass through the point of tangency. In this case, if we connect the center of
tangent circles,
and
(
and
respectively), it is going to pass through the point of tangency, namely,
, which is the same point as
, so
,
, and
are collinear. Hence,
and
are on both lines
and
, so
passes through point
, making
a diameter of
.
Now we state a few claims :
Claim 1: is equilateral.
Proof:
where the last equality holds by the Power of a Point Theorem.
Taking the square root of each side yields .
Since, by the definition of point ,
is on
. Hence,
, so
, and since
is the reflection of point
over line
,
, and since
, by the Pythagorean Theorem we have
Since is the perpendicular bisector of
,
and we have
hence
is equilateral.
With this in mind, we see that
Here, we state another claim :
Claim 2 : is a diameter of
Proof: Since , we have
and the same reasoning with gives
since
.
Now, apply Ptolemy’s Theorem gives
so is a diameter.
From that, we see that , so
. Now,
, so
, so
, and we’re done. ~Ddk001
Problem 10
Let be the remainder when
is divided by . Find the remainder when
is divided by
.
Solution 1 (Hensel's Lemma)
We note that
where the last step follows from Wilson's Theorem.
Now, applying Wilson's Theorem again implies , so
We see that
by Wilson's Theorem, so
Somewhat similarly,
since when
is a prime. (Proof here) Thus,
so
We obtain the following linear system of congruences:
By the Chinese Remainder Theorem,
where is an integer such that
(i.e. is an inverse of
modulo
).
Seeing a power of a prime as modulus reminds us of Hensel's Lemma for solving polynomial congruences. Let . We wish to solve
. Obviously,
, so
. By Hensel's Lemma, there exists a unique integer
such that
, and
is given by
where denotes the inverse of
modulo
(just
, not
to any power). Again,
, so since
,
, so
Therefore, we see that . We preform another lift. Again, there exists unique integer
such that
, given by
is also
, so
. We have
, so
Therefore, . We can thus set
, so that
Thus,
for some integer . Since
(since it is a remainder),
. Therefore,
A simple calculation shows , so
This is our answer. . ~ Ddk001
Problem 11
Let denote the number of primes that is less than or equal to
.
Show that there exist numbers and
such that
Solution 1(The Proof by Chebyshev)
Let be a prime and
be an integer. Since
, divides
exactly
times.
Therefore, since
, we have
so if ,
Repeated applications of that gives
Additionally,
so
Now, we note also that
so
Thus,
We have
since for
(because there is at least a half of even numbers).
Repeated addition of that gives
As we have previously derived,
so
. (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
where is the greatest integer such a that
.
Collecting our results, we see that
We have thus found the desired and
. ~Ddk001
Note: This was actually the same method of proof given by Chebyshev.
Problem 12
Suppose there is hats and
bins to put them in, and all objects are assigned a corresponding integer. Suppose there is
ways of putting the hats in the bins such that the following criteria are followed:
(i) If (where
and
are integers), then hat
is placed in a bin whose number is less than or equal to the number of the bin that hat
is placed in
(ii) There is at least one bin that contains at least two hats
Find .
Solution 1
We see that this is equivalent to asking "What is the number of ordered 6-tuples such that
and that
do NOT hold?".
correspond to the number of the bin that hat
is placed in. By the Nested Sum Theorem, there is
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
DO hold. There is obviously such ways. Thus,
.
We have
~ Ddk001
Problem 13
Suppose where
and
are relatively prime positive integers. Find
.
Solution 1(Wordless endless bash)
Problem 14
In with
,
is the foot of the perpendicular from
to
.
is the foot of the perpendicular from
to
.
is the midpoint of
. Prove that
.
Solution 1 (Analytic geo)
Let
We set it this way to simplify calculation when we calculate the coordinates of and
(Notice to find
, you just need to take the x coordinate of
and let the y coordinate be
).
Obviously,
Now, we see that
, so , as desired.
~Ddk001
Solution 2 (Hard vector bash)
Solution 2a (Hard)
Hence, .
~Ddk001
Solution 2b (Harder)
Since is the midpoint of
,
Now come the coordinates. Let
so that
.
Therefore,
Hence, we have that is perpendicular to
.
~Ddk001
Problem 15
Show that the series
where p and m are real numbers converge if or
but
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 16
Let and
be real numbers. Show that
Solution 1 (Plain high school contest)
It might seem insane, but we are going to divide this problem into 2 cases:
and
Case 1:
By the Trivial Inequality, we have
. Add these inequalities gives
and expanding yields
Since , we can square both sides and obtain
so
so the result follow if .
Case 2:
By the Trivial Inequality, we have
. Add these inequalities gives
and expanding yields
Since , we can square both sides and obtain
and the rest proceeds as in case 1.
The result follows. ~Ddk001
Solution 2 (Lagrange Multipliers)
Put and let
Under construction
Solution 3 (Finding relative extrema with calculus)
Let . We will prove that
is never negative (equivalent to the problem statement) by finding the critical values of
. (Note that
is a polynomial of
,
, and
. Therefore, we do not need to consider discontinuities.) We will begin by setting partial derivatives of
to
. (Note that if
,
, or
, the inequality in the problem statement reduces to
, which is true by the Trivial Inequality. Here on, we assume
).
If is a critical point of
, then it must satisfy equations (1), (2), and (3). Substituting (3) into (1), we find:
If , then
and
by the Trivial Inequality. We now only need to consider the case where
. Let
be the function obtained when we substitute
into function
.
.
We must now prove that is never negative (proving this statement finishes the last case of the proof). We similarly find the critical values of
by taking partial derivatives of
and setting them to
.
If is a critical point of
, then
. If
then
. Therefore,
is never negative. QED
Solution 4 (AM-GM bash)
Under construction (I am not very sure if this could work)
Problem 17
Common blood types are determined genetically by 3 alleles: ,
, and
. A person whose blood type is
,
, or
is heterozygous while
,
, or
is homozygous. The Hardy-Weinberg Law states that the proportion P of heterozygous individuals in a certain population is given by
where is the percent of allele
,
the percent of allele
, and
the percent allele
. Find the maximum possible proportion of heterozygous individuals in a certain population.
Solution 1 (Lagrange Multipliers)
Note that allele ,
, and
make up all the alleles, so therefore,
The problem reduces to determining the maximum value of given that
. Now, by the Method of Lagrange multipliers, we find all values of
,
, and
and
such that the gradient of
is
times the gradient of
, or
or
Solving yields
Now, since , we have
so . Therefore, the maximum of
given
is
.
Solution 2 (Relative extrema by calculus)
Just as in solution 1, we see that . To turn this into a 2-D problem, substitute
so that
Let . We take the partial derivatives of
and set them to zero to get the critical points:
We set them to zero:
We see that is the only critical points. Thus, it must be the desired point. ~Ddk001
Problem 18
Let denote the
th Fibonacci number. Prove that if
is odd, then all odd prime divisors of
are
.
Solution 1 (short and elegant)
Let for some nonnegative integer
. Then
. Since
and
are relatively prime, we are done.
Solution by Yiyj1 (talk) 23:48, 3 December 2024 (EST)
Contributors
Sources
Here's the source for the problems:
1,2,3,4,5,6,8,9,10,11,12,13,14,15,16,17: Ddk001
7: SANSKAR'S OG PROBLEMS, credits given to SANSGANKRSNGUPTA
- 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.