|
|
| Line 67: |
Line 67: |
| | | | |
| | Errata: Problem 6 - There exists at least <math>\textbf{one unordered triplet}</math>... | | Errata: Problem 6 - There exists at least <math>\textbf{one unordered triplet}</math>... |
| − |
| |
| − | ==Solutions==
| |
| − | These are solutions for the problems above. <math>\textbf{Scroll down at your own risk!}</math>
| |
| − |
| |
| − | ===Problem 1 Solutions===
| |
| − | ====Solution 1====
| |
| − | We split the condition into two separate conditions, as listed below.
| |
| − |
| |
| − |
| |
| − | <math>\frac{20^{23}}{n} + \frac{24^{23}}{n} = \lfloor{\frac{20^{23}}{n}+\frac{24^{23}}{n}}\rfloor</math>
| |
| − |
| |
| − | <math>\frac{20^{23}}{n} + \frac{24^{23}}{n} \neq \lfloor{\frac{20^{23}}{n}}\rfloor + \lfloor{\frac{24^{23}}{n}}\rfloor</math>
| |
| − |
| |
| − |
| |
| − | Rearranging the conditions, we find that
| |
| − |
| |
| − |
| |
| − | <math>\frac{20^{23}+24^{23}}{n} - \lfloor \frac{20^{23}+24^{23}}{n}\rfloor = 0</math>
| |
| − |
| |
| − | <math>(\frac{20^{23}}{n} - \lfloor \frac{20^{23}}{n} \rfloor) + (\frac{24^{23}}{n} - \lfloor \frac{24^{23}}{n} \rfloor) \neq 0</math>
| |
| − |
| |
| − |
| |
| − | Recalling that <math>x - \lfloor {x} \rfloor = frac(x)</math> where <math>frac(x)</math> represents the fractional part of <math>x</math>, we rewrite once more.
| |
| − |
| |
| − |
| |
| − | <math>frac(\frac{20^{23}+24^{23}}{n}) = 0</math> <math>\textbf{(1)}</math>
| |
| − |
| |
| − | <math>frac(\frac{20^{23}}{n}) + frac(\frac{24^{23}}{n}) \neq 0</math> <math>\textbf{(2)}</math>
| |
| − |
| |
| − |
| |
| − | We now gain some valuable insight. From <math>\textbf{(1)}</math>, we find that <math>n</math> must divide <math>20^{23} + 24^{23}</math>. From <math>\textbf{(2)}</math>, we find that <math>n</math> cannot divide both <math>20^{23}</math> and <math>24^{23}</math>. It is impossible for <math>n</math> to divide only <math>1</math> of <math>20^{23}</math> and <math>24^{23}</math>, as this would make <math>\textbf{(1)}</math> false. It must be that <math>n</math> divides neither <math>20^{23}</math> nor <math>24^{23}</math>. For both this and <math>\textbf{(1)}</math> to be true simultaneously, we must have that if <math>20^{23} \equiv a \bmod n</math>, then <math>24^{23} \equiv -a \bmod n</math>. By inspection, this occurs when <math>n = 22</math>.We now test the factors of <math>22</math> to see if we can find a smaller value. As both <math>20^{23}</math> and <math>24^{23}</math> are congruent to <math>0</math> mod <math>2</math>, <math>n = 2</math> is not a valid solution. However, with <math>n = 11</math>, <math>20^{23} \equiv (-2)^{23} \bmod 11</math>, while <math>24^{23} \equiv 2^{23} \bmod 11</math>. Clearly, <math>-(-2)^{23} = 2^{23}</math>, so our final answer is <math>\boxed{011}</math>.
| |
| − |
| |
| − | ===Problem 2 Solutions===
| |
| − | ====Solution 1====
| |
| − | First, we note the statements below.
| |
| − |
| |
| − |
| |
| − | <math>f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n - 2023) + f(n-2024)</math> <math>\textbf{(1)}</math>
| |
| − | <math>f(n-1) = f(n-2) + f(n-3) + f(n-4) + ... + f(n - 2024) + f(n - 2025)</math> <math>\textbf{(2)}</math>
| |
| − |
| |
| − |
| |
| − | We notice that most of the terms telescope if we subtract <math>\textbf{(2)}</math> from <math>\textbf{(1)}</math>. <cmath>f(n) - f(n-1) = f(n-1) - f(n-2025) \implies f(n)=2f(n-1) - f(n-2025) </cmath>. By adding <math>f(n-1)</math> to both sides, we find that <math>f(n) = 2f(n-1) - f(n-2025)</math>. From here, we can consider <math>f(4049)</math>. We note that for all <math>2026 \leq n \leq 4049</math>, the second part of our definition (the <math>f(n-2025)</math> term) is equal to one. From here, we can list out a few definitions for <math>f(4049)</math> using our formula.
| |
| − |
| |
| − |
| |
| − | <math>f(4049) = 2f(4048)-1 = 2^1f(4048) - (2^1-1)</math>
| |
| − |
| |
| − | <math>= 2(2f(4047)-1)-1 = 4f(4047) - 3 = 2^2f(4047) - (2^2 - 1)</math>
| |
| − |
| |
| − | <math>= 2(2(2f(4046)-1)-1)-1 = 8f(4046) - 7 = 2^3f(4046) - (2^3 - 1)</math>
| |
| − |
| |
| − | <math>= 2(2(2(2f(4045)-1)-1)-1)-1 = 16f(4045) - 15 = 2^4f(4045) - (2^4-1)</math>
| |
| − |
| |
| − |
| |
| − | It appears that on the interval <math>2025 \leq n \leq 4049</math>, <math>f(4049) = 2^{4049-n}f(n) - (2^{4049-n} - 1) = 2^{4049-n}(f(n)-1) + 1</math>. (<math>2025</math> is the upper bound because if we tried to calculate <math>f(2025)</math> using our alternate definition, we'd get <math>2f(2024) - f(0)</math>, and <math>f(0)</math> is undefined.) We attempt to maximize the value of <math>2^{4049-n}</math>, as this will make finding the prime factorization easier. This value is maximized when we choose the lower bound. We take <math>n = 2025</math>; then <cmath>f(4049) = 2^{2024}(f(2025)-1)+1</cmath> and <cmath>f(4049) - 1 = 2^{2024}(f(2025)-1)</cmath>. From our original definition, <math>f(2025) = 2024</math>. Thus, <cmath>f(4049)-1=2023 \cdot 2^{2024}</cmath>. We prime factorize <math>2023</math>; by trying divisibility tests until one works, we find that <math>2023 = 7 \cdot 289</math>. Recalling that <math>289 = 17^2</math>, we find that <cmath>f(4049)-1 = 2^{2024} \cdot 7
| |
| − | \cdot 17^{2}</cmath>. Then the desired sum is <cmath>2 \cdot 2024 + 7 \cdot 1 + 17 \cdot 2 = 4089</cmath>, and the remainder when this is divided by <math>1000</math> is <math>\boxed{089}</math>.
| |
| − |
| |
| − | ===Problem 3 Solutions===
| |
| − | ====Solution 1====
| |
| − | <asy>
| |
| − | unitsize(1inch);
| |
| − | draw((0,0)--(0,2));
| |
| − | draw((0,2)--(2,0));
| |
| − | draw((2,0)--(0,0));
| |
| − | draw(circle((0.586,0.586),0.586));
| |
| − | draw((0,0)--(0,1.172),red);
| |
| − | draw((0,1.172)--(1.172,1.172));
| |
| − | draw((1.172,1.172)--(1.172,0));
| |
| − | draw((1.172,0)--(0,0),red);
| |
| − | draw((0,1.172)--(0.828,1.172),red);
| |
| − | draw((0.828,1.172)--(1.172,0.828),red);
| |
| − | draw((1.172,0.828)--(1.172,0),red);
| |
| − | draw((0,0.1)--(0.1,0.1));
| |
| − | draw((0.1,0.1)--(0.1,0));
| |
| − | label("$A$",(0,2.1));
| |
| − | label("$B$",(0,-0.1));
| |
| − | label("$C$",(2,-0.1));
| |
| − | label("$2024$",(-0.2,1));
| |
| − | label("$2024$",(1,-0.2));
| |
| − | label("$D$",(1.272, 1.272));
| |
| − | label("$E$",(0.928,1.272));
| |
| − | label("$F$",(1.272,0.928));
| |
| − | </asy>
| |
| − |
| |
| − | We can use coordinate bashing. We may assume the legs of the triangle have side length <math>2</math> for ease of computation, and we can multiply by <math>1012</math> on our final answer to get our result. We place <math>B</math> at the origin; in this case, <math>A</math> has coordinates <math>(0,2)</math>, <math>B</math> has coordinates <math>(0, 0)</math>, and <math>C</math> has coordinates <math>(2, 0)</math>. Then line segment <math>\overline{\rm AC}</math> is on the line that has slope <math>\frac{0-2}{2-0} = -1</math> and <math>y</math>-intercept <math>2</math>, so the line's equation is <math>y = 2 - x</math>. Using the distance formula on <math>A</math> and <math>C</math> or noting that <math>\triangle ABC</math> is a <math>45-45-90</math> triangle, we find that the length of <math>\overline{\rm AC}</math> is <math>2\sqrt{2}</math>. The area of <math>\triangle ABC</math> is <math>\frac{1}{2}(2)(2) = 2</math>, and its semiperimeter is <math>\frac{2+2+2\sqrt{2}}{2} = 2 + \sqrt{2}</math>. Since <math>rs = A</math> or <math>r = \frac{A}{s}</math>, the inradius of <math>\triangle ABC</math> is <math>\frac{2}{2+\sqrt{2}} = 2-\sqrt{2}</math>. Also, because the side length of the square circumscribed around <math>\triangle ABC</math> is equal to the length of the diameter of the incircle of <math>\triangle ABC</math>, the square has side length <math>4 - 2\sqrt{2}</math>. From here, we can find that the vertices of the square are, starting at the bottom left and going clockwise, <math>(0,0)</math>, <math>(0, 4 - 2\sqrt{2})</math>, <math>(4 - 2\sqrt{2}, 4 - 2\sqrt{2})</math>, and <math>(4 - 2\sqrt{2}, 0)</math>. We label the top-right vertex of the square as <math>D</math>, the leftmost of the two intersection points of the square with the triangle as <math>E</math>, and the other intersection point as <math>F</math>. <math>D</math> is directly above <math>F</math>, so they must share an x-coordinate. Since <math>F</math> lies on the line <math>y = 2 - x</math>, we take <math>x = 4 - 2\sqrt{2}</math> to find that <math>F</math> has coordinates <math>(4 - 2\sqrt{2}, 2 - (4 - 2\sqrt{2}))</math> or <math>(4 - 2\sqrt{2}, 2\sqrt{2} - 2)</math>. Using similar logic, <math>E</math> has coordinates <math>(2\sqrt{2} - 2, 4 - 2\sqrt{2})</math>. The distance from <math>D</math> to <math>F</math> is just the positive difference of their y-coordinates, which is <math>4 - 2\sqrt{2} - (2\sqrt{2} - 2) = 6 - 4\sqrt{2}</math>. Similarly, the distance from <math>D</math> to <math>E</math> is the same. Since <math>\triangle DEF</math> is an isosceles right triangle, the length of <math>\overline{\rm EF}</math> is <math>\sqrt{2}</math> times the length of one of the legs, which happens to be <math>6\sqrt{2} - 8</math>. The perimeter of the diamond is equal to the perimeter of the square minus the lengths of <math>\overline{\rm ED}</math> and <math>\overline{\rm DF}</math> plus the length of <math>\overline{\rm EF}</math>, which is <math>4(4 - 2\sqrt{2}) - 2(6 - 4\sqrt{2}) + (6\sqrt{2} - 8) = 6\sqrt{2} - 4</math>. We multiply this by <math>1012</math> to scale the triangle to a side length of <math>2024</math>, resulting in a perimeter of <math>6072\sqrt{2} - 4048</math>. Thus, <math>a + b + c = 10122</math>, and the remainder when this is divided by <math>1000</math> is <math>\boxed{122}</math>.
| |
| − |
| |
| − | ===Problem 4 Solutions===
| |
| − | I have not written a solution yet, but the answer is <math>\boxed{976}</math>.
| |
| − |
| |
| − | ===Problem 5 Solutions===
| |
| − | I have not written a solution yet, but the answer is <math>\boxed{198}</math>.
| |
| − |
| |
| − | ===Problem 6 Solutions===
| |
| − | I have not written a solution yet.
| |
...
