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 "2022 AMC 12A Problems/Problem 5"

(→‎Solution 2 (Stars and Bars))
(→‎Solution 2 (Stars and Bars))
Line 12: Line 12:
  
 
==Solution 2 (Stars and Bars)==
 
==Solution 2 (Stars and Bars)==
−
Instead of considering all points with integer coordinates, first consider points with nonnegative coordinates only. Then, we want <math>x + y \le 20</math>. Note that we can introduce a third variable, say <math>z</math>, such that <math>z = 20 - (x + y)</math>. Then, counting the ways to have <math>x + y + z = 20</math> is the same as counting the ways to have <math>x + y \le 20</math>. Therefore, there are <math>\dbinom{20 + 3 - 1}{3 - 1} = 231</math> solutions with nonnegative integer coordinates.
+
Instead of considering all points with integer coordinates, first consider points with nonnegative coordinates only. Then, we want <math>x + y \le 20</math>. Note that we can introduce a third variable, say <math>z</math>, such that <math>z = 20 - (x + y)</math>. Note that counting the ways to have <math>x + y + z = 20</math> is the same as counting the ways to have <math>x + y \le 20</math>. Therefore, by stars and bars, there are <math>\dbinom{20 + 3 - 1}{3 - 1} = 231</math> solutions with nonnegative integer coordinates.
 +
 
 
Then, we can copy our solutions over to the other four quadrants. First, so as not to overcount, we remove all points on the axes. There are <math>20 + 20 + 1 = 41</math> such points. Then we multiply the <math>190</math> remaining points by <math>4</math> to get <math>760</math> points that are not on the axes. Then, we can add the <math>81</math> points on the axes to get <math>760 + 81 = \boxed{\textbf{(C)} \, 841}.</math>
 
Then, we can copy our solutions over to the other four quadrants. First, so as not to overcount, we remove all points on the axes. There are <math>20 + 20 + 1 = 41</math> such points. Then we multiply the <math>190</math> remaining points by <math>4</math> to get <math>760</math> points that are not on the axes. Then, we can add the <math>81</math> points on the axes to get <math>760 + 81 = \boxed{\textbf{(C)} \, 841}.</math>

Revision as of 13:25, 12 November 2022

Problem

The $\textit{taxicab distance}$ between points $(x_1, y_1)$ and $(x_2, y_2)$ in the coordinate plane is given by $|x_1 - x_2| + |y_1 - y_2|$. For how many points $P$ with integer coordinates is the taxicab distance between $P$ and the origin less than or equal to $20$?

$\textbf{(A)} \, 441 \qquad\textbf{(B)} \, 761 \qquad\textbf{(C)} \, 841 \qquad\textbf{(D)} \, 921 \qquad\textbf{(E)} \, 924$

Solution 1 (Pick's Theorem)

Let $P = (x, y)$. Since the problem asks for taxicab distances from the origin, we want $|x| + |y| \le 20$. The graph of all solutions to this equation on the $xy$-plane is a square with vertices at $(0, \pm 20)$ and $(\pm 20, 0)$ (In order to prove this, one can divide the sections of this graph into casework on the four quadrants, and tie together the resulting branches.) We want the number of lattice points on the border of the square and inside the square. Each side of the square goes through an equal number of lattice points, so if we focus on one side going from $(0,20)$ to $(20, 0)$, we can see that it goes through $21$ points in total. In addition, each of the vertices gets counted twice, so the total number of border points is $21\cdot4 - 4 = 80$. Also, the area of the square is $800$, so when we plug this information inside Pick's theorem, we get $800 = i + \frac{80}{2} - 1 \implies i = 761$. Then our answer is $761+80 = \boxed{\textbf{(C)} \, 841}.$

~ Oxymoronic15

Solution 2 (Stars and Bars)

Instead of considering all points with integer coordinates, first consider points with nonnegative coordinates only. Then, we want $x + y \le 20$. Note that we can introduce a third variable, say $z$, such that $z = 20 - (x + y)$. Note that counting the ways to have $x + y + z = 20$ is the same as counting the ways to have $x + y \le 20$. Therefore, by stars and bars, there are $\dbinom{20 + 3 - 1}{3 - 1} = 231$ solutions with nonnegative integer coordinates.

Then, we can copy our solutions over to the other four quadrants. First, so as not to overcount, we remove all points on the axes. There are $20 + 20 + 1 = 41$ such points. Then we multiply the $190$ remaining points by $4$ to get $760$ points that are not on the axes. Then, we can add the $81$ points on the axes to get $760 + 81 = \boxed{\textbf{(C)} \, 841}.$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_12A_Problems/Problem_5&oldid=181032"