Difference between revisions of "2022 AMC 10A Problems/Problem 25"
(→Alternate Solution) |
m (→Solution) |
||
Line 40: | Line 40: | ||
Now notice that by <math>(3)</math> , <math>t\equiv -1 \pmod{13}\implies t^2 \equiv 1 \pmod{13}</math>. | Now notice that by <math>(3)</math> , <math>t\equiv -1 \pmod{13}\implies t^2 \equiv 1 \pmod{13}</math>. | ||
− | However, by <math>(2)</math> , <math>t^2 \equiv k \cdot -1 \pmod{13}</math>. Therefore, <math>-k \equiv 1 \pmod{13} \implies k \equiv 1 \pmod{13}</math> | + | However, by <math>(2)</math> , <math>t^2 \equiv k \cdot -1 \pmod{13}</math>. Therefore, <math>-k \equiv 1 \pmod{13} \implies k \equiv -1 \pmod{13}</math> |
Also, by <math>(2)</math> , we know <math>k</math> must be a perfect square since <math>k</math> is relatively prime to <math>13k-1</math> (Euclids algorithm) and the two must multiply to a perfect square. Hence we know two conditions on <math>k</math>, and we can now guess and check to find the smallest that satisfies both. | Also, by <math>(2)</math> , we know <math>k</math> must be a perfect square since <math>k</math> is relatively prime to <math>13k-1</math> (Euclids algorithm) and the two must multiply to a perfect square. Hence we know two conditions on <math>k</math>, and we can now guess and check to find the smallest that satisfies both. |
Revision as of 08:48, 13 November 2022
Contents
[hide]Problem 25
Let , , and be squares that have vertices at lattice points (i.e., points whose coordinates are both integers) in the coordinate plane, together with their interiors. The bottom edge of each square is on the x-axis. The left edge of and the right edge of are on the -axis, and contains as many lattice points as does . The top two vertices of are in , and contains of the lattice points contained in . See the figure (not drawn to scale).
The fraction of lattice points in that are in is 27 times the fraction of lattice points in that are in . What is the minimum possible value of the edge length of plus the edge length of plus the edge length of ?
Solution
Let be the number of lattice points on the side length of square , be the number of lattice points on the side length of square , and be the number of lattice points on the side length of square . Note that the actual lengths of the side lengths are the number of lattice points minus , so we can work in terms of and subtract to get the actual answer at the end. Furthermore, note that the number of lattice points inside a rectangular region is equal to the number of lattice points in its width times the number of lattice points along its length.
Using this fact, the number of lattice points in is , the number of lattice points in is , and the number of lattice points in is .
Now, by the first condition, we have
The second condition, the number of lattice points contained in is a fourth of the number of lattice points contained in . The number of lattice points in is equal to the sum of the lattice points in their individually bounded regions, but the lattice points along the y-axis for the full length of square is shared by both of them, so we need to subtract that out.
In all, this condition yields us
Note from that is a multiple of . We can write and substitute: . Note that must be divisible by two for the product to be divisible by 4. Thus we make another substitution, :
Finally we look at the last condition; that the fraction of the lattice points inside that are inside is times the fraction of lattice points inside that are inside .
Let be the number of lattice points along the bottom of the rectangle formed by , and be the number of lattice points along the bottom of the the rectangle formed by .
Therefore, the number of lattice points in is and the number of lattice points in is .
Thus by this condition,
Finally, notice that (subtracting overlap), and so we have
Now notice that by , .
However, by , . Therefore,
Also, by , we know must be a perfect square since is relatively prime to (Euclids algorithm) and the two must multiply to a perfect square. Hence we know two conditions on , and we can now guess and check to find the smallest that satisfies both.
We check first since its one less than a multiple of , but this does not work. Next, we have which works because is a perfect square. Thus we have found the smallest , and therefore the smallest .
Now we just work backwards: and . Then . Finally, from , .
Finally, the sum of each square’s side lengths is
~KingRavi
Alternate Solution
Notice that each answer choice has a different residue mod . Therefore, we can just find the residue of mod and find the unique answer choice that fits, without actually finding .
From Solution 1, we have from the second condition. From the third condition, . Substituting, we get . Therefore, . From the first condition, we have , so .
Therefore .
We want to find , so our answer will have a remainder of when divided by .
We divide by and find that the remainder is . Therefore the answer that will give us a remainder of will be
~KingRavi
See Also
2022 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.